关联 Voronoi 图组件的算法

Question

到目前为止，我有一个程序采用一组随机点、站点，并围绕这些点形成适当的 Voronoi 图，表示为角和边的图形。它还为我提供了 Delaunay 三角剖分作为另一个以所有站点为节点的图形(尽管我不知道这在这里是否有用)。

到目前为止，每个边对象都记录了它入射到哪些角上，每个角对象都记录了哪些边入射到它上面以及它与哪些其他角相邻。我的目标是能够为两个相邻站点向我的 Edge 类添加两个字段，并能够通过添加两个字段来扩展我的 Site 类:一个字段包含它周围的一组角和它周围的一组边。

我在想，使用改进的广度优先搜索可能会生成所有单独的多边形。然而，这将需要遍历所有站点并计算出哪个属于哪个多边形，这将是 O(n^2)，这并不理想。我们那里有更高效的算法可以做同样的事情吗？

Answer 1

我遇到了类似的问题。如果你有所有的边缘，找到线的中点并循环遍历所有站点的列表。对列表进行排序，它会给出最近的 2 个站点。 2 个最近的站点是您想要的，因为除外边缘外，边缘总是划分 2 个站点。然后保留所有边缘和站点的列表并重复该过程，直到没有更多的边缘。线索是对于外部多边形，您只需添加一个站点。最后它给出了所有多边形的列表。