Voronoi diagram, Delaunay triangulation - data str

问题:

I want to compute Voronoi and its dual, Delaunay triangulation. I am using Watson Bowyer algorithm. My goal afterwards is to compute alpha-shapes (concave hulls). So I will need to rapidly access the voronoi cell for a given point, the neighbors...

Which data structures did you use for your Voronoi/Delaunay algorithm? I have thought of using a disjoint set data structure with union-find operations, so that I can 'bind' to one parent, the point p in original data set, the set of point in Vp. However, one point in Voronoi diagram 'belongs' to several Voronoi cells.

What is your advice, or could you hint at some good reference?

Regards.

回答1:

I suggest that you take a look at the half-edge data structure:

http://www.flipcode.com/archives/The_Half-Edge_Data_Structure.shtml

Half-edge data structure is used in many applications and frameworks. One implementation of it is found in the GEL framework:

http://www2.imm.dtu.dk/projects/GEL/