VD shapes


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.


Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.