Buy Dideo Subscription
Given a set of points in the plane, the algorithm does these steps: 1) Constructs an initial triangulation using a divide-and-conquer method that tends to produce fat polygons, a good starting point for further refinement. 2) An edge-flip algorithm is performed to transform the initial triangulation to the Delaunay triangulation. 3) A two-pass conversion from Delaunay to Voronoi diagram is performed. In the first pass, the Voronoi vertices are found, including the single vertex associated with each triangle, as well as a vertex (at infinity) for each edge lying on the convex hull. 4) In the second pass, the vertices found earlier are connected to form the Voronoi edges.
