如何从这个Voronoi Diagram数据中获取单元格字典？

Question

使用此程序中的voronoi/delaunay图生成库,该库基于Fortune 其算法的原始实现,使用随机点集作为输入数据,我能够获得以下输出数据:

1. Delaunay三角剖分的边缘列表,意味着对于每个输入点,我可以看到哪些输入点是它的邻居.它们似乎没有任何特定的顺序.
2. 来自Voronoi图的顶点对列表,我可以用它一次绘制一行Voronoi图.再次,显然没有特别的顺序.
3. 一个未命名的点对列表,它们似乎与2的列表相同,但顺序不同.
4. Voronoi图中形成的顶点列表,也显然没有特定的顺序.

以下是使用此库的程序测试运行的数据示例:

Input points:
0   (426.484, 175.16)
1   (282.004, 231.388)
2   (487.891, 353.996)
3   (50.8574, 5.02996)
4   (602.252, 288.418)

Vertex Pairs: 
0   (387.425, 288.533)  (277.142, 5.15565)
1   (387.425, 288.533)  (503.484, 248.682)
2   (277.142, 5.15565)  (0, 288.161)
3   (387.425, 288.533)  (272.213, 482)
4   (503.484, 248.682)  (637.275, 482)
5   (503.484, 248.682)  (642, 33.7153)
6   (277.142, 5.15565)  (279.477, 0)

Voronoi lines?: 
0   (279.477, 0)    (277.142, 5.15565)
1   (642, 33.7153)  (503.484, 248.682)
2   (503.484, 248.682)  (637.275, 482)
3   (387.425, 288.533)  (272.213, 482)
4   (277.142, 5.15565)  (0, 288.161)
5   (387.425, 288.533)  (503.484, 248.682)
6   (277.142, 5.15565)  (387.425, 288.533)

Delaunay Edges: 
0   (282.004, 231.388)  (487.891, 353.996)
1   (602.252, 288.418)  (487.891, 353.996)
2   (426.484, 175.16)   (487.891, 353.996)
3   (426.484, 175.16)   (602.252, 288.418)
4   (50.8574, 5.02996)  (282.004, 231.388)
5   (426.484, 175.16)   (282.004, 231.388)
6   (50.8574, 5.02996)  (426.484, 175.16)

Vertices: 
0   (277.142, 5.15565)
1   (503.484, 248.682)
2   (387.425, 288.533)
3   (0, 288.161)
4   (272.213, 482)
5   (637.275, 482)
6   (642, 33.7153)
7   (279.477, 0)

虽然如果我只需要绘制Voronoi和Delaunay图表,上述数据就足够了,但对于我试图用这些图表进行的实际工作来说,这些信息还不够.我需要的是由Voronoi顶点形成的多边形字典,由每个多边形形成的输入点索引.优选地,对于每个多边形,这些点将按顺时针顺序排序.

根据上述信息,我可以隐式地为每个区域分配数据,在必要时将数据分配给角点,告诉哪些区域共享边缘(使用Delaunay边缘),并相应地进行分析.

简而言之,我怎样才能使用我可用的数据来组合一个字典,其中键是输入点之一,而该键索引的数据是形成周围多边形的Voronoi顶点的列表？或者,我给出的数据中隐含的信息是什么？

Answer 1

Fortune的算法是O(n log n) - 但是你的代码将是O(n ^ 2),如果你试图重建Alink提出的细胞暴力方式.

我的答案的出发点是,你用来生成单元格的不是一个库,而只是一个编写的类,整齐地包装了Fortune自己最初提供的代码,而不是一个成熟的库.因此,作者实际上没有预料到您的需求,虽然您想要的信息已经计算出来,但却无法访问.

在内部,您的输入点存储为"站点"结构的实例,并且算法继续创建半边,每个半边保持一个引用"顶点" ,它是指向它所包含的站点的指针.沿着半边走,你自然环绕着封闭的网站 - 正是你需要的.

为了访问这些数据,我建议修改或扩展VoronoiDiagramGenerator类; 我会通过创建一个散列表来实现它,其中Site指针作为键,单个HalfEdge指针作为值.然后,修改generateVoroni方法,在调用voronoi之后立即插入新代码:

For each HalfEdge in ELHash
         Get table entry for current half edge's Site
         If site in table has null HalfEdge reference
            set current HalfEdge reference
         End If
End For each

......还有你的字典.单个半边将允许您"走"围绕相关站点的多边形的周长,我认为这就是您所要求的.您的下一个问题是有效地发现哪个多边形包含一些新的数据点 - 但这是另一个问题:-).我希望你会考虑分享你完成的课程 - 它应该比基础课程更有用.

编辑:这是一个很好的演示文稿,描述了上面所有的图片:http://ima.udg.es/~sellares/ComGeo/Vor2D_1.ppt :

• Voronoy图的定义
• 半边树(见下图)
• 图片中的财富算法

这里有一个C#实现可以帮助您检索字典,如上所述:http://www.codeproject.com/Articles/11275/Fortune-s-Voronoi-algorithm-implemented-in-C