anderswallin.net

Note how the Delaunay triangulation (in red) is not correct. The outside of true Delaunay triangulation should form the convex hull of the input points, which is clearly not the case here(see how the red lines around the ellipse-shape are not tangents). What's going wrong? It has to do with how the algorithm avoids infinite or unbounded voronoi-edges. Before any real input generator points are inserted we start with three special generator vertices and the corresponding vd. A zoomed out view is shown below. If the cyan vd edges extending outward from the ellipse would stretch out to infinity then we would indeed recover the true Delaunay triangulation. The Voronoi diagram should however be correct inside the orange circle. I'm not sure how the true Delaunay triangulation could constructed with this algorithm.

Some progress on the voronoi-diagram algorithm. It doesn't crash easily now with random or regular input points. Not crashing is good, but whether the output converges towards the correct diagram or not remains to be seen...

Playing around with the vd-code has highlighted some problems. Using double-precision floating point numbers for coordinates, strange things start to appear when the coordinates are around 1E-6 or so. It's not possible to accurately compute the sign of the in-circle predicate (a 4x4 determinant) and the diagram update should instead be based on topological reasoning.