| I also consider Voronoi diagrams fun, and in my life I've implemented three different algorithms for generating 2D Voronoi diagrams (or Delaunay triangulations, which are the duals of Voronoi diagrams): 1. Fortune's algorithm [0] 2. The Bowyer-Watson algorithm for generating the Delaunay triangulation incrementally [1] 3. Quickhull (which generates the 3D convex hull of points, which is the 2D delaunay triangulation of points). [2] Of these, Quickhull is the simplest, and Bowyer-Watson is by far the hardest. Bowyer-Watson seems very simple, but there are demons hiding in that algorithm, and almost every implementation you can find online is incorrect (for instance, this one [3]). You can tell that these implementations of Bowyer-Watson are incorrect, because every Delaunay triangulation contains the convex hull of the points, and it's easy to tell when they don't. In fact, even the description in Computational Geometry: Algorithms and Applications (a standard textbook) is subtly wrong. The reason Bowyer-Watson is hard is this: it's an incremental algorithm where you add the points one-by-one to an already constructed Delaunay triangulation, you make sure all edges are flipped right, and at the end you have the full triangulation. However: you have to have a triangle to start with. In order for the algorithm to work, this initial "super-triangle", has to contain all the points in the set, and also be made up of points that are not contained in any circumcircle of any combination of three points in the set. However: if three points are colinear (or very close, which it is almost guaranteed some points are going to be), the circumcircle of those three points is MASSIVE (essentially "infinite", covering the entire half-plane). But the super-triangle points still have to be outside of it. This means that the super-triangle points have to be essentially "symbolic" points (not normal points with coordinates, but special magic points), and you have to hard-code special rules for them. It is extremely difficult to implement these rules correctly. Fortune's algorithm is on the surface more complex, but there's less goblins hiding in that algorithm. There's some tricky data-structure stuff, but it's not too bad. Quickhull is fairly straight-forward, and is the algorithm I would recommend if you want to give this whole Voronoi adventure a go (also has the benefit of giving you a 3D convex hull algorithm, which you can have all sorts of fun with!). [0]: https://en.wikipedia.org/wiki/Fortune%27s_algorithm [1]: https://en.wikipedia.org/wiki/Bowyer%E2%80%93Watson_algorith... [2]: https://en.wikipedia.org/wiki/Quickhull (this description is for the 2D version, but the 3D version is similar) [3]: https://cdn.rawgit.com/axelboc/voronoi-delaunay/v2.1/index.h... |
I couldn't get past the point of creating a seemingly random mass of intersecting lines. My math knowledge is lacking (I'm not good at groking geometry for some reason), so I wasn't sure what was wrong or how to approach fixing it.
Maybe I should give Quickhull a go. I think I understand what it's doing.