Voronoi diagram, Delaunay triangulation - data str

2019-02-20 00:02发布

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条回答
狗以群分
2楼-- · 2019-02-20 00:37

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/

查看更多
登录 后发表回答