When reading the Wikipedia article on Voronoi diagrams I was fascinated by this animation:
https://en.wikipedia.org/wiki/Voronoi_diagram#/media/File:Voronoi_growth_euclidean.gif
I noticed that to create a Voronoi diagram we just need to pick a locally interacting system with suitable properties such that a ball expands with constant speed around each of the initial points, but when the two balls meet they "annihilate" each other and stop expanding at that point.
However, I haven't seen any implementation of Voronoi diagrams without at least some distance checks. The dirtiest one just checks distance for every point to each of the initial points and picks the color of the nearest one.
As far as I can see even for approximate Voronoi diagrams on a grid distance checks are involved. See this wonderful question for example: Animating a Voronoi Diagram.
I have tried a quick implementation using cellular automaton on a square grid, however this way I don't get an Euclidean distance diagram, since each point expands as a square.
The question is: can we make a cellular automata or another kind of algorithm to create an approximation to Euclidean Voronoi diagram for a random set of points without doing any distance checks?
(Ideally, the approximation should approach the exact diagram for the infinite grid).
Here's the code I used:
Xm = 100;
Ym = 100;
Tm = 50;
Sm = 19;
F0 = Table[0, {j, 1, Xm}, {k, 1, Ym}];
Sx = Table[RandomInteger[{1, Xm}], {s, 1, Sm}];
Sy = Table[RandomInteger[{1, Ym}], {s, 1, Sm}];
Cs = Table[RandomInteger[{1, Sm^2}], {s, 1, Sm}];
Do[F0[[Sx[[s]], Sy[[s]]]] = -1, {s, 1, Sm}];
Do[l = If[Sx[[s]] == 1, Xm, Sx[[s]] - 1];
r = If[Sx[[s]] == Xm, 1, Sx[[s]] + 1];
t = If[Sy[[s]] == 1, Ym, Sy[[s]] - 1];
b = If[Sy[[s]] == Ym, 1, Sy[[s]] + 1];
F0[[l, Sy[[s]]]] =
F0[[r, Sy[[s]]]] =
F0[[Sx[[s]], t]] = F0[[Sx[[s]], b]] = Cs[[s]], {s, 1, Sm}];
F1 = F0;
ArrayPlot[F1, ColorFunction -> "ThermometerColors"]
Do[F0 = F1;
Do[l = If[j == 1, Xm, j - 1];
r = If[j == Xm, 1, j + 1];
t = If[k == 1, Ym, k - 1];
b = If[k == Ym, 1, k + 1];
If[F0[[j, k]] == 0,
F1[[j, k]] =
Max[F0[[l, k]], F0[[r, k]], F0[[j, t]], F0[[j, b]]]], {j, 1, Xm}, {k, 1, Ym}],
{n, 1, Tm}];
ArrayPlot[F1, ColorFunction -> "ThermometerColors"]
As a reaction to the comments: here is the relevant part of the code without using
Max[]
:
Do[l = If[j == 1, Xm, j - 1];
r = If[j == Xm, 1, j + 1];
t = If[k == 1, Ym, k - 1];
b = If[k == Ym, 1, k + 1];
If[F0[[j, k]] == 0 &&
F0[[l, k]]^2 + F0[[r, k]]^2 + F0[[j, t]]^2 + F0[[j, b]]^2 > 0,
F1[[j, k]] =
RandomChoice[
Cases[{F0[[l, k]], F0[[r, k]], F0[[j, t]], F0[[j, b]]},
Except[0 | 0.]]]], {j, 1, Xm}, {k, 1, Ym}]
The only difference: we get a fuzzy boundary because of the uncertainty for the interacting colors. However, in the limit of grid size approaching infinity the fuzziness would disappear. No distance checks are involved.
I have redone the algorithm with a quasi hexagonal neighborhood (still using a square grid), but hexagons are not circles either, so I guess the main question is: how to make a cellular automaton which expands roughly as a circle (as the grid size and time tend to infinity)? If I can manage that, then I get an appoximation to a real Voronoi diagram.
Update
Using a method suggested by @aardvark2012 and some other tricks, I have been able to create expanding dodecagons (12-gons) which are very close to circles.
I need to iron my code a little before posting it here, but the basic idea is: I change the rule each 3 steps, so the direction of growth changes as well, on average I get this:
I haven't been able to draw the real Voronoi mesh over the diagram, so here's a crude juxtaposition (of the mesh created by Mathematica's procedure and the result of my code) made by hand. The disrepancy at the boundary is caused by the cyclic boundary conditions I use, not by the method itself.
Max[]
in your code is effectively the metric being used in your fake diagram, so I'm unclear about your "without doing any distance checks" requirement. $\endgroup$Max[]
is only needed when two expanding areas contact each other. It is not in any way a distance check. I could replace it with picking a color at random from the ones present. I can redo my code withoutMax[]
if it's not clear. $\endgroup$Max[]
to act as a (Chebyshev) metric. Try doing it if you're not at the first quadrant (say, centered at the origin) so that you have negative coordinates. $\endgroup$Max[]
$\endgroup$