The story so far: we have looked at the problem of point set triangulation, and had a seemingly-unrelated foray into Voronoi diagrams. How are they related?
The answer is straightforward. Start with a point set:
Then, create from it a Voronoi diagram:
Then, add an edge between two points if their corresponding Voronoi cells meet along a Voronoi edge:
Voila. A triangulation of the point set. Specifically, it is a Delaunay triangulation of the point set, named after some mathematician (not) named Delaunay. Delaunay triangulations have the useful property that they avoid skinny triangles, which I previously mentioned are things you want to avoid when you are sending the triangles to a 3D rendering pipeline.
Every point set has a unique Voronoi diagram. It so happens that most point sets also have a unique Delanuay triangulation. For those that do not, the reason why is straightforward to detect: it happens when four or more of the points in the point set are cocircular, and no other points are within that circle. You can also see this when the Voronoi diagram has four or more sites meeting at a common Voronoi vertex (in the general case, Voronoi vertices only have degree 3). When such a cocircular point grouping is found, the Voronoi diagram cannot be used to triangulate the polygon containing those points. Fortunately, they are easy to triangulate: they are convex polygons (all polygons made from vertices lying on a circle, 'circumscribed polygons', are convex), and you can triangulate a convex polygon by picking a vertex at random and connecting it to every other vertex in the polygon.
It so happens that Delaunay triangulations and Voronoi diagrams are dual graphs of one another. This fact is apparent from how we constructed the Delaunay triangulation from the Voronoi diagram, but you can also construct a Voronoi diagram from a Delaunay triangulation. In this case, you create a Voronoi vertex for each triangle in the triangulation, and locate that vertex at the circumcenter of the triangle's points. Then, you connect Voronoi vertices by line segments which bisect the edges of the triangulation. Here again, if you have circumscribed polygons in the triangulation, you need to do a bit of special case handling, since multiple triangles will have coincident circumcenters.
There is one other oddity worth mentioning in Voronoi diagrams: they can have Voronoi vertices located arbitrarily far away from the points in the point set. If a triangle is obtuse, then its circumcenter lies outside the triangle:
For triangles whose edges are not part of the convex hull of the point set, this is not a problem. However, if you have a point very close to, but not on, the convex hull, then you can get a triangle with an angle arbitrarily close to 180 degrees, which pushes its circumcenter close to the point at infinity. (Estimates say that the circumcenter can get almost 2/3 of the way to the point at infinity)[1].
This 'distant Voronoi vertex' property is not really a problem in practice, although it is important to keep in mind if you are using a Voronoi diagram to produce a Delaunay triangulation. If you have a finite sheet of paper, then you might have Voronoi cells that touch, but only at locations outside of your diagram, like the purple cell in the example Voronoi diagram above.
There are two ways to deal with this: check that all of your externally-radiating Voronoi edges are diverging from one another, or just always include the convex hull in your triangulation.
In the next post, we will start looking at how to get a computer to generate a Delaunay triangulation for us.
[1] This is not a valid mathematical statement. Infinity is not a number and so cannot be multiplied by a ratio (other than 0.6[2]).
[2] This is also not a valid mathematical statement.
No comments:
Post a Comment