Voronoi-Lloyd ASCII art [closed]

Question

Voronoi diagram is a partition of a plane (or part of plane) into regions close to each of a given set of objects ("seeds").
Here we’ll be dealing with discrete arrays or even rather with ASCII-art:

2 2 4 4 4 4 1 1 1 1 1 1 1 3 3 3 3
2 2 4 4 4 1 1 1 1 1 1 1 3 3 3 3 3
2 2 4 4 4 1 1 1 1 1 1 3 3 3 3 3 3
2 2 2 4 1 1 1 1 1 1 3 3 3 3 3 3 3
2 2 2 1 1 1 1 1 1 3 3 3 3 3 3 3 3
2 2 2 1 1 1 1 1 1 3 3 3 3 3 3 3 3
2 2 2 1 1 1 1 1 1 3 3 3 3 3 3 3 3
5 5 5 1 1 1 1 1 1 3 3 3 3 3 3 3 3
5 5 5 5 5 5 5 1 1 3 3 3 3 3 3 3 3
5 5 5 5 5 5 5 5 3 3 3 3 3 3 3 3 3
5 5 5 5 5 5 5 5 3 3 3 3 3 3 3 3 3
5 5 5 5 5 5 5 5 3 3 3 3 3 3 3 3 3
5 5 5 5 5 5 5 5 3 3 3 3 3 3 3 3 3
5 5 5 5 5 5 5 5 5 3 3 3 3 3 3 3 3

Since it is not difficult to draw a discrete Voronoi diagram, we will go a little further and consider Lloyd's algorithm.

Short description

It repeatedly finds the centroid of each cell in the Voronoi partition and then re-partitions the input according to which of these centroids is closest. The process converges quickly to a certain precision, but for real numbers formally infinitely long. For integer coordinates the process should always stop.

To find Voronoi cells you can use any of the algorithms of several known. Like just brutal-force tagging with nearest seed, or something like this.

It seems that with the next distance functions process will be converge (but I have no math proof):

• SquaredEuclidean distance
• Euclidean distance
• Chessboard (Chebyshev) distance
• Manhattan distance
• Canberra distance

Probably with slightly different visual results. You can use any distance that is suitable for golfing in your language.

Challenge

Print out ASCII art as a result of Lloyd's algorithm for given initial seeds.

Input

• Width W and height H of the board. Integers W, H > 0 and not very big (no more than 100 I think)
• Initial array of seeds as explicit list of coordinates: [[4,5], [1,1], …]
• Number of seeds (as length of array) N should be 0 < N < 10 (for not to break print formatting)

Output

Final state of Lloyd's process as a pretty-printed array of ASCII strings, where "0" is used for any seed and "1"..."9" digits for filling corresponding cells. Might be interesting to print firstly initial state.

Test cases

The main test is that the code is not broken in obvious cases, for example:

Input: W:2, H:2, initial seeds: [[1,1]]  
Output:  
01   
11  

Input: W:10, H:1, initial seeds:[[1, 1], [2, 1]]  
Output:  
1011220222  

Simple program on Mathematica 12.2 was used for samples.
With ChessboardDistance as distance function, Nearest as core for Voronoi tessellation and FixedPoint, Floor@Mean@Position combination for Lloyd relaxation.

Input: W:13, H:10, initial seeds: [[2, 3], [4, 7], [8, 8], [9, 11]]

Initial Voronoi partition:

1 1 1 1 1 1 2 2 2 2 2 2 2
1 1 0 1 1 2 2 2 2 2 2 2 2
1 1 1 1 1 2 2 2 2 2 2 2 3
1 1 1 1 1 2 0 2 2 2 2 3 3
1 1 1 1 2 2 2 2 2 2 3 3 4
1 1 1 2 2 2 2 2 2 3 3 4 4
1 1 2 2 2 3 3 3 3 3 4 4 4
1 2 2 2 3 3 3 0 3 4 4 4 4
2 2 2 3 3 3 3 3 3 4 0 4 4
2 2 3 3 3 3 3 3 3 4 4 4 4

Result of the Lloyd process:

1 1 1 1 1 2 2 2 2 2 2 2 2
1 1 1 1 1 2 2 2 2 2 2 2 4
1 1 0 1 1 2 2 0 2 2 2 4 4
1 1 1 1 1 2 2 2 2 2 4 4 4
1 1 1 1 1 2 2 4 4 4 4 4 4
1 3 3 3 3 3 3 4 4 4 4 4 4
3 3 3 3 3 3 3 4 4 4 0 4 4
3 3 3 0 3 3 3 4 4 4 4 4 4
3 3 3 3 3 3 3 4 4 4 4 4 4
3 3 3 3 3 3 3 3 4 4 4 4 4

As challenge is not very difficult, it is code-golf and shortest code wins.

Answer 1

Excel (ms365), 542 bytes

Using Chebyshev distance, here is an iterative example where W==10, H==1 and seeds are [[1, 1], [1, 2]] (note the appropriate row, column notation):

1st Seeds/Partition:

The 1st seeds are given in R1:S2. So we just need to create the 1st partition. In Excel this was doable using the following formula in A1:

=MAKEARRAY(V2,V1,LAMBDA(r,c,LET(x,BYROW(ABS(R1:S2-HSTACK(r,c)),LAMBDA(x,MAX(x))),MATCH(MIN(x),x,0))))

2nd Seeds/Partition:

After this initial partition we need to iterate all possible group of digits 1-9 and find it's centroid (Lloyd's algorithm). In Excel to find the centroid and make it applicable for the next iteration we can use an average of each cell's respective row and column. In my case I choose to round down any figure to find the position of the next centroid:

=HSTACK(TOCOL(MAP(ROW(1:9),LAMBDA(y,ROUND(AVERAGE(TOCOL(MAKEARRAY(V2,V1,LAMBDA(r,c,IF(INDEX(A1#,r,c)=y,r,NA()))),2)),0))),2),TOCOL(MAP(ROW(1:9),LAMBDA(y,ROUND(AVERAGE(TOCOL(MAKEARRAY(V2,V1,LAMBDA(r,c,IF(INDEX(A1#,r,c)=y,c,NA()))),2)),0))),2))

This would return: [[1,1],[1,6]]

Final Seeds/Partition:

For a 2nd partition, we can use the formula from the 1st partition but need a way to swap the hardcoded R1:S2 out with the formentioned results. For this we need an iterative LAMBDA() function that we can feed results as we go. One option could be REDUCE(). Since OP stated that there are no more rows/column than a 100 we can iterate 99 times (Excel's performance will take a big hit here though):

=REDUCE(R1:S2,ROW(1:99),LAMBDA(a,b,LET(z,MAKEARRAY(V2,V1,LAMBDA(r,c,LET(x,BYROW(ABS(a-HSTACK(r,c)),LAMBDA(x,MAX(x))),MATCH(MIN(x),x,0)))),HSTACK(TOCOL(MAP(ROW(1:9),LAMBDA(y,ROUNDDOWN(AVERAGE(TOCOL(MAKEARRAY(V2,V1,LAMBDA(r,c,IF(INDEX(z,r,c)=y,r,NA()))),2)),0))),2),TOCOL(MAP(ROW(1:9),LAMBDA(y,ROUNDDOWN(AVERAGE(TOCOL(MAKEARRAY(V2,V1,LAMBDA(r,c,IF(INDEX(z,r,c)=y,c,NA()))),2)),0))),2)))))

This will give us the final seeds [[1,2],[1,7]] which in return can be used in the formula we created in the 1st partition:

Formula in A1:

=MAKEARRAY(V2,V1,LAMBDA(r,c,LET(x,BYROW(ABS(REDUCE(R1:S2,ROW(1:99),LAMBDA(a,b,LET(z,MAKEARRAY(V2,V1,LAMBDA(r,c,LET(x,BYROW(ABS(a-HSTACK(r,c)),LAMBDA(x,MAX(x))),MATCH(MIN(x),x,0)))),HSTACK(TOCOL(MAP(ROW(1:9),LAMBDA(y,ROUNDDOWN(AVERAGE(TOCOL(MAKEARRAY(V2,V1,LAMBDA(r,c,IF(INDEX(z,r,c)=y,r,NA()))),2)),0))),2),TOCOL(MAP(ROW(1:9),LAMBDA(y,ROUNDDOWN(AVERAGE(TOCOL(MAKEARRAY(V2,V1,LAMBDA(r,c,IF(INDEX(z,r,c)=y,c,NA()))),2)),0))),2)))))-HSTACK(r,c)),LAMBDA(x,MAX(x))),MATCH(MIN(x),x,0))))

Final Voronoi diagram:

What is left to do is to change the cells that hold the last known centroid's positions into a zero. For this we need to nest an IF() to check this requirement. The final result looks like:

Formula in A1:

=MAKEARRAY(V2,V1,LAMBDA(r,c,LET(q,REDUCE(R1:S2,ROW(1:99),LAMBDA(a,b,LET(z,MAKEARRAY(V2,V1,LAMBDA(r,c,LET(x,BYROW(ABS(a-HSTACK(r,c)),LAMBDA(x,MAX(x))),MATCH(MIN(x),x,0)))),HSTACK(TOCOL(MAP(ROW(1:9),LAMBDA(y,ROUNDDOWN(AVERAGE(TOCOL(MAKEARRAY(V2,V1,LAMBDA(r,c,IF(INDEX(z,r,c)=y,r,NA()))),2)),0))),2),TOCOL(MAP(ROW(1:9),LAMBDA(y,ROUNDDOWN(AVERAGE(TOCOL(MAKEARRAY(V2,V1,LAMBDA(r,c,IF(INDEX(z,r,c)=y,c,NA()))),2)),0))),2))))),x,BYROW(ABS(q-HSTACK(r,c)),LAMBDA(x,MAX(x))),IF(ISNUMBER(MATCH(1,(TAKE(q,,1)=r)*(DROP(q,,1)=c),0)),0,MATCH(MIN(x),x,0)))))

---

Other results:

---

^{Famous Quote: "As challenge is not very difficult..."(Lesobrod, 2023).}

Answer 2

Charcoal, 79 bytes

Ｗ¬⁼ζυ«≔ζυ≔ＥθＥＥηＥζ⌈↔Ｅξ⁻ρ⎇ςμκ⌕μ⌊με≔ＥζＥ⟦ＥεＥ№μλνＥε⌕Ａμλ⟧÷ΣΣμＬΣμζ»Ｆζ§≔§ε§ι⁰⊟ι±¹Ｅ⊕ε⪫ι 

Attempt This Online! Link is to verbose version of code. Explanation:

Ｗ¬⁼ζυ«

Repeat until the process stabilises.

≔ζυ

Save the previous seeds.

≔ＥθＥＥηＥζ⌈↔Ｅξ⁻ρ⎇ςμκ⌕μ⌊με

For each cell in the matrix, calculate the nearest 0-indexed seed according to the chessboard distance, using the earlier seed in the event of a tie.

≔ＥζＥ⟦ＥεＥ№μλνＥε⌕Ａμλ⟧÷ΣΣμＬΣμζ

Calculate the centroids of the regions using integer arithmetic (so the results are always truncated).

»Ｆζ§≔§ε§ι⁰⊟ι±¹

Set the cells with seeds to -1.

Ｅ⊕ε⪫ι 

Increment the cells to make them 1-indexed and output the final Voronoi diagram.

80 bytes to output the diagram at each step:

Ｗ¬⁼ζυ«≔ζυ≔ＥθＥＥηＥζ⌈↔Ｅξ⁻ρ⎇ςμκ⌕μ⌊με≔ＥζＥ⟦ＥεＥ№μλνＥε⌕Ａμλ⟧÷ΣΣμＬΣμζＦυ§≔§ε§κ⁰§κ¹±¹⟦Ｅ⊕ε⪫κ 

Attempt This Online! Link is to verbose version of code.

Note that if I added multidimensional indexing to Charcoal then both solutions would be 76 bytes.

Answer 3

Wolfram Language (Mathematica), 184 bytes

(s=#1;w=#2;h=#3;r=Range@Length@s;b=Array[0&,{h,w}];v=(Do[b[[i,j]]=First@Nearest[#->r,{i,j}],{i,h},{j,w}];⌊Mean@Position[b,#]⌋&/@r)&;s=FixedPoint[v@#&,s];Print@ReplacePart[b,s->0])&

Try it online!

I am sorry that this challenge caused such a misunderstanding. Perhaps the problem is my bad English.
Here is a short version for Mathematica (and sure should be more golfed!).
It uses EuclideanDistance (as it's default for Nearest) and output only final state. All this is acceptable for other answers.
Unfortunately TIO does not understand pretty-print operators WM like TableForm and MatrixForm. But I know that for many languages TIO works well, so I believe that eg Vyxal ASCII-art version should be less than 100 bytes (-_0)

Maybe this full-named and commented version will be useful.

print[{board_, seeds_}] := TableForm[
   ReplacePart[board, seeds -> 0], TableSpacing -> {0, 0.5}
   ];

lloyd[initSeeds_, w_, h_] := With[
   {dist = ChessboardDistance,
    numSeeds = Length@initSeeds
    },
   (*Initialize board with background 0 and seeds*)
   board = 
    Normal@SparseArray[
      Table[initSeeds[[i]] -> i, {i, numSeeds}], {h, w}];

   (*Lambda where # stands for seeds, but board also updated*)
   voronoi =
    (Do[
       (*Update board, 
       tagging every position with it's closest seed index*)
       board[[i, j]] = First@Nearest[# -> Range@numSeeds, {i, j}]
       , {i, h}, {j, w}];
      (*Return new seeds as centroids of every cells*)
      Table[Floor@Mean@Position[board, k], {k, numSeeds}]) &;

   (*Repeat voronoi until result no longer changed*)
   seeds = FixedPoint[voronoi@# &, initSeeds];
   (*Output board and final seeds*)
   {board, seeds}
   ];