c++ - 如何从此 Voronoi 图数据中获取单元格字典？

Question

使用发现的 voronoi/delaunay 图生成库 in this program ，它基于 Fortune 的 his algorithm 的原始实现，以一组随机点作为输入数据，我能够得到以下输出数据:

1. Delaunay Triangulation 中的边列表，这意味着对于每个输入点，我可以看到哪些输入点是它的邻居。它们似乎没有任何特定的顺序。
2. Voronoi Diagram 中的顶点对列表，我可以用它一次绘制一条线的 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 顶点形成的多边形字典，由每个多边形围绕的输入点索引。最好，对于每个多边形，这些点将按顺时针顺序排序。 p>

有了以上信息，我可以隐式地为每个区域分配数据，必要时将数据分配给角，判断哪些区域共享边(使用 Delaunay 边)，并进行相应的分析。

简而言之，我如何使用可用的数据来组合一个字典，其中键是输入点之一，由该键索引的数据是 Voronoi 顶点的列表形成周围的多边形？ 或者，该信息是否隐含在我提供的数据中？

Answer 1

Fortune 的算法为 O(n log n) - 但如果您尝试按照 Alink 建议的蛮力方式重建细胞，您的代码将为 O(n^2)。

我的回答的出发点是您用来生成单元格的不是库，而只是 a class written to neatly wrap up the code originally presented by Fortune himself ，实际上并不是一个成熟的库。所以，作者其实并没有预料到你的需求，虽然你想要的信息已经计算出来了，但是却无法访问。

在内部，您的输入点存储为“站点”结构的实例，算法继续创建 half-edges ，每个都维护一个引用“顶点”它是指向它所包含的站点的指针。沿着半边行走，您自然会绕过封闭的站点——这正是您所需要的。

要访问这些数据，我建议修改或扩展 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

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

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

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

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