Voronoi site points from Delaunay triangulation

3
votes

How can one determine the exact Voronoi sites (cells/regions) from a Delaunay triangulation?

If one has an already constructed delaunay triangulation it is easy to calculate the edges of a voronoi by simply connecting adjacent circum-circle centers of every triangle.

It is also easy to determine the Voronoi points/sites because they are represented by every point of every triangle in the Delaunay triangulation.

However how do you determine that a specific voronoi site goes with a specific list of edges from a delaunay triangulation?

It seems it is simple to get one and the other as separate entities but putting them together is another challenge?

Looking at the diagram below, you can see the Delaunay triangulation along with the dual Voronoi diagram. All that I described can be pictured below for an easy reference. Ignore the green circle as that is just an artifact of this particular reference i took from the web.

voronoi/delaunay triangulation

2
algorithmmathcomputational-geometryvoronoi
Possible duplicate of How do I derive a Voronoi diagram given its point set and its Delaunay triangulation? – andand
It is not quite a duplicate. That discusses how to find the edges. I want to find the regions. I want to find the voronoi site point and map them to the edges which that question does not answer. – efel
Question andand linked answers enough to cover your problem. For each Delaunay vertex create Voronoi point, for each Delaunay edges connected to that vertex create Voronoi edge, and connect these edges to produce Voronoi cell. To make connecting simple, first sort Delaunay edges by angle, since edges are connected in that order. If Delauney edge is adjacent only to one triangle, than Voronoi edge corresponding to it goes to infinity. – Ante
How exactly is your triangulation represented ? – Yves Daoust
Currently my triangulation is an array of triangles (3 points). – efel

2 Answers

0
votes

If you want polygons from edges pick the midpoint of each edge and the distance to each site then sort the result and pick the first and second (when they are equal) and save them into polygons. For the borders there is of course only 1 edge. Maybe a dupe:Getting polygons from voronoi edges.

It's a bit tricky and hard to visualize. I am little stuck with the borders. Here is the original answer from Alink:How can I get a dictionary of cells from this Voronoi Diagram data?.

0
votes

Each vertex in the Delaunay triangulation represents a Voronoi site. So to create the cell of a site you take one such triangle t and a vertex v in t. Now compute the Voronoi edges between v and the two remaining vertices of t. Repeat this process by traversing the triangles around v one by one. Assuming you can store the neighbourhood relation between the triangles this should at most take O(k) time, k being the number of adjacent triangles of v.

This converts the Delaunay triangulation into the Voronoi Diagram in O(n) time/space, for n sites. No sorting is required, otherwise what is the point in having the Delaunay triangulation in the first place.