Delauney Triangulation and Voronin diagram

From Wikipedia about Delauney Diagram:    https://en.wikipedia.org/wiki/Delaunay_triangulation

Bowyer-Watson algorithm to solve Delauney Triangulation: https://en.wikipedia.org/wiki/Bowyer%E2%80%93Watson_algorithm
Pseudo-code

function BowyerWatson (pointList)
     // pointList is a set of coordinates defining the points to be triangulated
     triangulation := empty triangle mesh data structure
     add super-triangle to triangulation // must be large enough to completely contain all the points in pointList
     for each point in pointList do // add all the points one at a time to the triangulation
        badTriangles := empty set
        for each triangle in triangulation do // first find all the triangles that are no longer valid due to the insertion
           if point is inside circumcircle of triangle
              add triangle to badTriangles
        polygon := empty set
        for each triangle in badTriangles do // find the boundary of the polygonal hole
           for each edge in triangle do
              if edge is not shared by any other triangles in badTriangles
                 add edge to polygon
        for each triangle in badTriangles do // remove them from the data structure
           remove triangle from triangulation
        for each edge in polygon do // re-triangulate the polygonal hole
           newTri := form a triangle from edge to point
           add newTri to triangulation
     for each triangle in triangulation // done inserting points, now clean up
        if triangle contains a vertex from original super-triangle
           remove triangle from triangulation
     return triangulation


------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

An easy algorithm to compute the Delaunay triangulation of a point set is flipping edges. Since a Delaunay triangulation is the dual graph of a Voronoi diagram, you can construct the diagram from the triangulation in linear time.

Unfortunately, the worst case running time of the flipping approach is O(n^2). Better algorithms such as Fortune's line sweep exist, which take O(n log n) time. This is somewhat tricky to implement though. If you're lazy (as I am), I would suggest looking for an existing implementation of a Delaunay triangulation, use it, and then compute the dual graph.

In general, a good book on the topic is Computational Geometry by de Berg et al.

-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

The Bowyer-Watson algorithm is quite easy to understand. Here is an implementation:http://paulbourke.net/papers/triangulate/. It's a delaunay triangulation for a set of points but you can use it to get the dual of the delaunay,i.e. a voronoi-diagram. BTW. the minimum spanning tree is a subset of delaunay triangulation.

-------------------------------------------------------------------------------------------------------------------------------

There is a freely availble voronoi implementation for 2-d graphs in C and in C++ from Stephan Fortune / Shane O'Sullivan:

VoronoiDiagramGenerator.cpp VoronoiDiagramGenerator.h

You'll find it at many places. I.e. at http://www.skynet.ie/~sos/masters/

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

The most effecient algorithm to construct a voronoi diagram is Fortune's algorithm. It runs in O(n log n).

Here is a link to his reference implementation in C.

Personally I really like the python implementation by Bill Simons and Carson Farmer, since I found it easier to extend.

-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

Check brute-force solution presented with pseudo-code by Richard Franks in his answer on the question How do I derive a Voronoi diagram given its point set and its Delaunay triangulation?

-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

The Voronoi diagram is just the dual graph of the Delaunay triangulation.

  • So, the edges of the Voronoi diagram are along the perpendicular bisectors of the edges of the Delaunay triangulation, so compute those lines.

  • Then, compute the vertices of the Voronoi diagram by finding the intersections of adjacent edges.

  • Finally, the edges are then the subsets of the lines you computed which lie between the corresponding vertices.

Note that the exact code depends on the internal representation you're using for the two diagrams.
-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Bowyer-Watson implementation using C++ and Python:    https://github.com/ayron/delaunay
Comments