Voronoi图的凸壳

我需要一个算法来计算O（n）中点的Voronoi图的一组点的凸包。 Voronoi图包含在边界框中并存储为双向连接的边界列表。输入是原点位于边界框上的半边。Voronoi图的凸壳

我知道这两点是相邻的上凸包当且仅当它们共享一个无限长维诺边缘......

2010-11-23 wallacer

为什么你不能从一个无限边缘绕到凸包？我想你可能想更多地谈一谈这个问题是如何表现出来的，以便我们能够理解这个难题。 – 2010-11-25 14:09:04

我想这个问题的难度更大的部分是测试voronoi图上的特定边是否确实会持续无穷大，如果它没有在边界框中定界。此外，由于voronoi图和边界框存储为双向连接的边列表，另一个具有挑战性的部分是确定如何正确地遍历DCEL。无论哪种方式，我想出了一个有效的解决方案。也许我会很快在这里写下它。 – wallacer 2010-11-26 00:19:50

如果你有一个边界框足够大，这样只有无限的细胞具有界限边缘，任务没有按看起来很难。遍历边界边界，对于它们中的每一个，向前和向后遍历它以找到第一个非边界边界F和B。将遍历期间发现的当前和所有边界标记为used。如果该框不存在，则边线F和B将是无限的。因此，他们接触面（fF和fB），他们的“中心”是凸包的一部分（当前面是C），而横向C-to-F是凸包的一部分。采取面子fF并从F的双胞胎向前迭代找到下一个非边界边缘，比如F1。如果它等于'B'-twin（或者它的边界是used），我们就完成了。如果不是，遍历下一个邻居（'fF1'）。

来源

2011-01-27 22:28:27 mbaitoff

-1

我相信可以在O（n）时间内计算Voronoi图的凸包。

如果给定的Voronoi图和一个顶点应该位于CH中，那么您可以遍历Voronoi图的单元格，并像Graham扫描算法中那样使用不同的方式来扩展凸包。

只有一个理论缺少在这里，看接下来...

根据计算几何由Springer的M4书，定理7.4：Q点是涡（P）的顶点当且仅当其最大的空圆C_p（q）在其边界上包含三个或更多个位置。这意味着每次迭代需要检查的站点都在O（1）中完成，这意味着您只需要遍历O（n）个站点。

根据定理7.3，n的点的Voronoi图中顶点的数目指向最多2n-5（线性次序）的平面上的点。

因此，可以计算O（n）时间内Voronoi图的CH。

来源

2014-07-13 18:57:35 TripleS

Voronoi图的凸壳

回答

相关问题