15

使用这个程序中找到的voronoi/delaunay图生成库，它基于Fortune的算法的原始实现，以一组随机点作为输入数据，我能够得到以下输出数据：

  1. 来自Delaunay Triangulation的边列表，这意味着对于每个输入点，我可以看到哪些输入点是它的邻居。它们似乎没有任何特定的顺序。
  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 顶点的列表？或者，这些信息是否隐含在我获得的数据中？

4

5 回答 5

12

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

我回答的出发点是，您用来生成单元格的不是库，而只是一个类，它是为了整齐地包装 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

幻灯片 31 幻灯片 32 幻灯片 33 幻灯片 34

于 2012-02-28T14:54:42.763 回答
3

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

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

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

现在获取这 2 个单元格：计算边缘的中点，然后通过简单地遍历列表找到两个最近的输入点，同时保持 2 个最小距离。根据 Voronoi 结构的性质，这两个是形成两个单元的结构。请注意，这两个距离应该相等，但浮点不精确可能会引入细微的差异。

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

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

于 2012-02-27T20:13:06.037 回答
1

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

它以 2 种模式工作 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

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

  • 使用这个包我会说它通常不适用于报告错误的输入数据。它只接受输入多边形（不是随机点），这里的问题是你有自相交的输入多边形。
  • 它不回答你的问题，只报告一组点，而不是字典
于 2012-02-29T19:29:12.283 回答
0

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

Carson Farmer 的这个 python 实现为你提供了拓扑信息

于 2013-10-09T21:13:03.683 回答
0

你可以只使用三角形：http ://www.cs.cmu.edu/~quake/triangle.html

于 2012-02-27T13:51:06.223 回答