如何从 Voronoi 图中提取一组点的凸包
我需要一种算法来计算 O(n) 中点的 Voronoi 图中的一组点的凸包。 Voronoi 图包含在边界框中，并存储为双连接边列表。输入是原点位于边界框上的半边。
我知道两个点在凸包上相邻，当且仅当它们共享无限长的 voronoi 边。
I need an algorithm for calculating the convex hull of a set of points from the Voronoi Diagram of the points in O(n). The Voronoi diagram is contained in a bounding box and is stored as a doubly connected edge list. The input is a half edge whose origin is on the bounding box.
I know that two points are adjacent on the convex hull iff they share an infinitely long voronoi edge.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
如果您有一个足够大的边界框，以便只有无限的单元格具有边界边缘，那么这项任务似乎并不困难。迭代边界边，对于每个边界边，向前和向后遍历以找到第一个非边界边
F和B。将遍历期间找到的当前边界边和所有边界边标记为已使用。如果盒子不存在，边F和B将是无限的。因此，它们接触面（fF和fB），其“中心”是凸包的一部分（当前面是C），并且交叉-edgeC-to-F是凸包的一部分。取面fF并从F的孪生向前迭代以查找下一个非边界边，例如F1。如果它等于“B”-twin（或者它的边界被使用），我们就完成了。如果不是，则遍历下一个邻居（'fF1'）。If you have a bounding box large enough so that only infinite cells have bounding edges, the task doesn't seem tough. Iterate through the bounding edges, for each of them, traverse it forward and backward to find first non-bounding edges
FandB. Mark current and all bounding edges found during traverse asused. EdgesFandBwould be infinite if the box won't exist. Thus, they touch faces (fFandfB) who's 'centers' are part of the convex hull (current face isC), and cross-edgeC-to-Fis the part of a convex hull. Take facefFand iterate from theF's twin forward to find next non-bounding edge, say,F1. If it's equal to 'B'-twin (or it's bounding edges wereused), we are finished. If not, traverse the next neighbour ('fF1').我相信可以在 O(n) 时间内计算出 Voronoi 图的凸包。
对于给定的 Voronoi 图和应驻留在 CH 中的顶点，您可以迭代 Voronoi 图的单元并扩展凸包，就像在 Grahm 扫描算法中所做的那样，但方式不同。
这里只缺少一个理论，接下来看...
根据 Springer 的计算几何 M4 书，定理 7.4：点 q 是 Vor(P) 的顶点当且仅当其最大空圆 C_p(q) 包含其边界上有三个或更多地点。
这意味着每次迭代需要检查的站点都是在 O(1) 内完成的，这意味着您只需迭代 O(n) 个站点。
根据定理7.3，平面上n个点的ste的Voronoi图中的顶点数最多为2n-5（线性阶）。
因此可以在 O(n) 时间内计算出 Voronoi 图的 CH。
I believe it's possible to compute the convex hull of Voronoi Diagram in O(n) time.
In case of a given Voronoi diagram and a vertex that shall reside in the CH, you may able to iterate through the Voronoi Diagram's cells and expend the convex hull just like been done in Grahm scan algorithm but with different manner.
There is only one theory missing here, watch next...
According to Computational Geometry by Springer the M4 book, Theorem 7.4: A point q is a vertex of Vor(P) if and only if its largest empty circle C_p(q) contains three or more sites on it's boundary.
Which means that the sites that need to be check every iteration is a done in O(1), which mean that you only have to iterate through O(n) sites.
According the theorem 7.3, the number of vertices in the Voronoi diagram of a ste of n points sites in a plain it at most 2n-5 (linear order).
Therefor it's possible to compute the CH of Voronoi diagram in O(n) time.