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

Question

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

15

使用在该程序中找到的Voronoi/Delaunay图生成库，它基于Fortune原始实现的算法。将随机点集作为输入数据后，我能够得到以下输出数据：

来自Delaunay三角剖分的边列表，这意味着对于每个输入点，我可以看到哪些输入点是其邻居。它们似乎没有特定的顺序。
来自Voronoi图的顶点对列表，我可以使用它们一条接一条地绘制Voronoi图。同样，似乎没有特定的顺序。
一组未命名的点对，它似乎只是与2相同的列表，但顺序不同。
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顶点列表？或者说，这些信息是否在我所获得的数据中某些地方隐含着？

- pdusen

1

这是您从库中获得的全部内容吗？一些Voronoi单元没有用封闭的多边形描述。 - Daniyar

1

这就是库所提供的全部内容。我认为没有被封闭多边形描述的Voronoi单元格是与矩形平面边缘相遇的单元格；例如，此图中的所有边框单元格：http://www-cs-students.stanford.edu/~amitp/game-programming/polygon-map-generation/voronoi-and-delaunay.png - pdusen

5个回答

3

您的边缘列表似乎不完整，您需要添加包含库调用提供的矩形边框上的边缘（这里似乎是642,482）。从技术上讲，Voronoi分割应该使用一些无限边，但这些都是有限的。我假设您也希望在此边界附近添加这些“开放”的多边形，因为在您的示例中它们都是这样的。

添加这些边界边缘似乎不难，只是有点繁琐。可能就像对于主矩形的每条边，找到所有在其上的顶点（忽略角落），进行排序（水平线按x排序，垂直线按y排序）并使用这些值分割该边。这会生成缺失的边缘，但不要直接将它们添加到您的主列表中，因为它们很特殊，因为它们是唯一没有分隔两个单元格的边缘。

因此，对于问题本身，我建议这样做：在您的边缘的主列表中（由库提供），每个边缘都分隔两个单元格，如果我们找到了哪些单元格，则可以将该边缘分配给其中每一个。由于单元格等同于输入点，因此我们将拥有所需的字典，除了顶点列表而不是边缘，但这很容易转换。

现在要获取这两个单元格：计算边缘的中心点，并从此找到两个最近的输入点，方法是简单地遍历列表并保持2个最小距离。由于Voronoi结构的属性，这两个点形成两个单元格。请注意，这两个距离应相等，但浮点不精确可能会引入轻微差异。

最后，添加我们在主矩形上生成的边界边缘，但对于这些边缘，只使用第一个最近的输入点，因为它们仅与一个单元格相邻。

最后，我们可以将每个边缘列表转换为顶点列表（将每个端点转储到集合中）。如果您想以顺时针顺序对它们进行排序，请注意，它是一个带有输入点内部的凸多边形。因此，您只需生成从输入点到每个顶点的向量，计算其从一个轴的角度（使用std :: atan2（x，y）），并将此角度用作比较器值来对其进行排序（参见std :: sort）。

- Alink

1

我使用Triangle软件包来生成Dalaunay三角剖分: http://www.cs.cmu.edu/~quake/triangle.html

它有两种模式：a) 作为triangulate.exe实用程序和b) 作为C库。要将其编译为实用程序，您只需要编译triangle.c并运行：

   triangulate -vZ input.poly 
   #v -voronoy, Z - starting from 0 index

获取 Voronoi 图（请参考 .poly 格式的手册）我已经用您提供的输入数据在这样一个 .poly 文件中进行了实验：

# <# of vertices> <dimension (must be 2)> <# of attributes> <# of boundary markers (0 or 1)> 
5 2 0 0
# Following lines: <vertex #> <x> <y> [attributes] [boundary marker]
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
#One line: <# of segments> <# of boundary markers (0 or 1)>
5 0
#Following lines: <segment #> <endpoint> <endpoint> [boundary marker]
0 0 1
1 1 2
2 2 3
3 3 4
4 4 0

但它只是报告输入数据错误。

使用这个包，我想说它经常不能处理输入数据并报告错误。它只接受输入多边形（而不是随机点），问题在于您的输入多边形存在自相交的情况。
它没有回答你的问题，只报告了一组点，而不是字典

- blackbada_cpp

0

http://svn.osgeo.org/qgis/trunk/qgis/python/plugins/fTools/tools/voronoi.py

这个由Carson Farmer实现的Python程序可以为您提供拓扑信息

- Andy

0

你可以使用Triangle：http://www.cs.cmu.edu/~quake/triangle.html。

- Daniyar

1

除了许可证存在问题和完全缺乏编程参考之外，看了triangle.h以尝试查看可用的API后，我并没有真正看到它如何解决我的问题。请澄清一下？ - pdusen

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Edward Dixon · Accepted Answer

Fortune算法的时间复杂度是O(n log n) - 但是如果您试图像Alink提出的那样以暴力方式重构单元格，那么您的代码将是O(n²)。

我的回答起点是，您用来生成单元格的不是库，而只是一个优雅地封装了Fortune原始代码的类，实际上并不是成熟的库。因此，作者实际上没有预料到您的需求，尽管所需信息已被计算，但却无法访问。

在内部，您的输入点被存储为Site结构的实例，并且该算法继续创建半边, 每个半边都维护一个"vertex"（指向其包围的Site的指针）的引用。沿着半边前进，您自然地绕过了所包含的Site-这正是您需要的。

要访问这些数据，我建议修改或扩展VoronoiDiagramGenerator类；我会通过创建一个哈希表，其中Site指针作为键，单个HalfEdge指针作为值来实现。然后，在调用voronoi之后立即插入您的新代码，修改generateVoroni方法即可。

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图的定义
半边树（见下图）
Fortunes算法的图片

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