10
\$\begingroup\$

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):

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 and shortest code wins.

\$\endgroup\$
10
  • \$\begingroup\$ I assume we can choose whether the input-coordinates are 1-based or 0-based indexed? Also, I don't really understand the seeds in the test cases, because [[1,1]] in the first test case would be either the top-left if 1-based indexing is used or bottom-right if 0-based indexing is used. But instead, the output has a 0 at index [1,2] (1-based) / [0,1] (0-based). Likewise I also don't get how coordinate [2,1] can result in a 0 at the 6th position of the 1x10 output-block. \$\endgroup\$ Mar 3, 2023 at 9:06
  • \$\begingroup\$ @kevin-cruijssen, I use Mathematica top-left [1,1] notation, and surely possible to use any other. I fix first example. What about second, the output is the result of Lloyd process, not just initial Voronoi partition! \$\endgroup\$
    – lesobrod
    Mar 3, 2023 at 9:49
  • 1
    \$\begingroup\$ @lesobrod, would you mind include the initial seeds you have used for your final sample? Would be interesting to see the deviation between your answer and the applied algorithms in given answers. \$\endgroup\$
    – JvdV
    Mar 3, 2023 at 13:23
  • 2
    \$\begingroup\$ It seems we need to use Lloyd's algorithm but then you say "to find Voronoi cells you can use any of the algorithms of several known". Can you clarify? Also, you say "it is also interesting to play with various distance functions". What distance function/funtions must/can the answer use? Lastly, some more test cases would be convenient. \$\endgroup\$
    – Luis Mendo
    Mar 3, 2023 at 16:12
  • 2
    \$\begingroup\$ My VTC stands as it's still unclear to me what's being asked of us. You're relying heavily on prior knowledge and external sources, which are at risk of link rot, instead of presenting a self-contained challenge. \$\endgroup\$
    – Shaggy
    Mar 3, 2023 at 20:26

3 Answers 3

8
\$\begingroup\$

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))))

enter image description here

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:

enter image description here

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:

enter image description here

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:

enter image description here

enter image description here

enter image description here

enter image description here

enter image description here


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

\$\endgroup\$
2
  • 2
    \$\begingroup\$ I'm 100% sure this can be done using fewer bytes (in any other language/application), but at this point I'm just happy that I could achieve this using Excel functions. \$\endgroup\$
    – JvdV
    Mar 3, 2023 at 12:27
  • \$\begingroup\$ This is a first answer to my first question on CD so many, many thanks and best wishes!! \$\endgroup\$
    – lesobrod
    Mar 3, 2023 at 14:13
1
\$\begingroup\$

Charcoal, 79 bytes

W¬⁼ζυ«≔ζυ≔EθEEηEζ⌈↔Eξ⁻ρ⎇ςμκ⌕μ⌊με≔EζE⟦EεE№μλνEε⌕Aμλ⟧÷ΣΣμLΣμζ»Fζ§≔§ε§ι⁰⊟ι±¹E⊕ε⪫ι 

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

W¬⁼ζυ«

Repeat until the process stabilises.

≔ζυ

Save the previous seeds.

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

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.

≔EζE⟦EεE№μλνEε⌕Aμλ⟧÷ΣΣμLΣμζ

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

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

Set the cells with seeds to -1.

E⊕ε⪫ι 

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

80 bytes to output the diagram at each step:

W¬⁼ζυ«≔ζυ≔EθEEηEζ⌈↔Eξ⁻ρ⎇ςμκ⌕μ⌊με≔EζE⟦EεE№μλνEε⌕Aμλ⟧÷ΣΣμLΣμζFυ§≔§ε§κ⁰§κ¹±¹⟦E⊕ε⪫κ 

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.

\$\endgroup\$
0
\$\begingroup\$

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}
   ];
\$\endgroup\$

Not the answer you're looking for? Browse other questions tagged or ask your own question.