One of my favorite renderings of this is in this article [1], that shows the relationship between the Delaunay triangulation, Voronoi diagram, a relative neighborhood graph (RNG) and the euclidean minimum spanning tree (EMSP) of a set of 2d points.<p>I have a theory that the union of the edges of the RNG and EMSP could be used for automatic navigation between widgets in a GUI: combining the two, there's always between 1 and 4 edges coming out of every point, and so each of them could correspond to a direction key up/down/left/right according to some simple heuristic.<p>--<p>1: <a href="https://axltnnr.io/2018/Triangulation/" rel="nofollow noreferrer">https://axltnnr.io/2018/Triangulation/</a>
In case anyone wonders how a voronoi diagram looks on a wall, here's my living room <a href="https://tomk32.de/assets/voronoi-wall.jpg" rel="nofollow noreferrer">https://tomk32.de/assets/voronoi-wall.jpg</a><p>The process to create it is as simple as you might think, select points, draw the center lines for all pairs of close neighbour points and the corners will appear naturally. Tape all edges and paint the wall starting with almost white, mix more of the three base colours into for each of the cells.
I wrote a moderately popular Delaunay/Voronoi library for Unity a few years back [1] with a neat little demo video [2]. I implemented the incremental Bowyer-Watson algorithm for generating the triangulations, and then took the dual to generate the Voronoi tesselation (I also added a "clipper" that clips the voronoi diagram to a convex outline, which was fun, I haven't seen that anywhere else before and had to figure out how to do it myself).<p>Bowyer-Watson (which is described in this article) seems very simple to implement when you start: just start with a "big triangle" and then add points iteratively to it, and perform the flips you need to do. To do it performant, you have to build up a tree structure as you go, but it's not very tricky.<p>However: almost every description (including on Wikipedia) and implementation of Bowyer-Watson I could find was wrong. There's an incredibly subtle and hard to deal with issue with the algorithm, which is the initial "big triangle". Most people who implement it (and indeed I did the same initally) just make the triangle big enough to contain all the points, but that's not enough: it needs to be big enough to contain all the points in all the circumcircles of the triangles. These circumcircles can get ENORMOUS: in the limit of three points on a line, it's an infinite half-plane. Even if they aren't literally collinear, just close, the triangle becomes way to huge to deal with.<p>The answer is that you have to put the points "at infinity", which is a very weird concept. Basically, you have to have special rules for these points when doing comparisons, it's really tricky and very hard to get right.<p>If I were doing this again, I wouldn't use Bowyer-Watson, this subtlety is too tricky and hard to get right. Fortune's sweep-line is more complex on the surface, but that's the one I would go with. Or the 3D convex hull technique (which I also wrote a library for, by the way [3]).<p>[1]: <a href="https://github.com/OskarSigvardsson/unity-delaunay">https://github.com/OskarSigvardsson/unity-delaunay</a><p>[2]: <a href="https://www.youtube.com/watch?v=f3T5jtsokz8">https://www.youtube.com/watch?v=f3T5jtsokz8</a><p>[3]: <a href="https://github.com/OskarSigvardsson/unity-quickhull">https://github.com/OskarSigvardsson/unity-quickhull</a>
My favorite algorithm for generating Voronoi diagrams is the Jumping flood algorithm:<p><a href="https://en.wikipedia.org/wiki/Jump_flooding_algorithm" rel="nofollow noreferrer">https://en.wikipedia.org/wiki/Jump_flooding_algorithm</a><p>This is an approximate algorithm that only works in pixel space, but it's lots of fun to implement (simpler to implement than Fortune's algorithm).
The numerical robustness thing gave me a chuckle (rotate 1 radian and pray to the geometry gods), especially as I've been spending a good fraction of my time dealing with that in fancy path rendering and stroking.<p>One of the things I really want to work on in the next few months is a path intersection implementation that's robust by construction, backed up both by a convincing (if not formal) argument and tests crafted to shake out robustness issues. I have a bunch of ideas, largely motivated by the need to generalize well to curves - Shewchuk's work, cited elsethread, is impressive but I'm not smart enough to figure out how to make it work for arbitrary Béziers.<p>There's an issue[277] to track the work, and that has pointers to some of the ideas. If anyone is interested in working with me on this, please get in touch. If successful, I think it'll result in a nice code base and also likely a publishable paper.<p>[277]: <a href="https://github.com/linebender/kurbo/issues/277">https://github.com/linebender/kurbo/issues/277</a>
Unfortunately, as you move into higher dimensions, these algorithms typically bog down.<p>Suppose that you have a point that is inside of the convex hull of the mesh that you want to use for triangulation (we‘re talking hyper-triangles here). What are the best points to choose for your triangulation? Since there are a lot of candidates for hyper-triangles you cannot possibly store the set of triangles beforehand.<p>I approached this problem using linear programming using the distance to the mesh points to find the best triangle. Not sure if this is the best approach though.<p>Happy to hear if someone knows of a better approach.
A new weather model NCAR is working on uses Voronoi meshes to divide the planet into cells. The Voronoi meshes allow nice transitions of higher resolution to lower resolution cells so you can model at higher resolutions in areas of interest and dont have the same problems the WRF and GFS have trying to divide a sphere into square cells<p><a href="https://ncar.ucar.edu/what-we-offer/models/model-prediction-across-scales-mpas" rel="nofollow noreferrer">https://ncar.ucar.edu/what-we-offer/models/model-prediction-...</a>
<a href="https://mpas-dev.github.io/" rel="nofollow noreferrer">https://mpas-dev.github.io/</a>
I would be interested in an explanation why it's O(nlog(n)).<p>It requires sorting the points along one axis which already gives O(nlog(n)) as a lower bound, but I'd be interested in how the line-sweeping would need to be done to not go over that.<p>The number of points in the beach front should roughly scale with the square root of points, so a naive search/replace per point insertion would take sqrt(n) operations and a O(n*sqrt(n)) overall runtime.