4

我知道有一个最坏情况 O(n log n) 算法可以找到复杂多边形的凸包，还有一个最坏情况 O(n) 算法可以找到简单多边形的凸包。是否存在用于查找复杂多边形的凸包的最坏情况 O(n) 算法？

复杂多边形是线段可能相交的多边形。找到一个复杂多边形的凸包相当于找到一个无序列点列表的凸包。

4

4 回答 4

2

我很确定不是。可以证明任意点集上的凸包等价于排序。我们可以对任意点集进行排序，并将这些点按顺序连接成一个复杂的多边形，从而将任意点集的问题减少到您的问题上。

这是一个证明凸包等效于排序的链接。我太懒了，打字员也太糟糕了，不能自己写出来。

于 2010-07-30T21:38:24.223 回答
2

如果您的点集使得某些基于非比较的排序机制（如基数排序）比基于比较的方法更快，那么您似乎可以使用格雷厄姆扫描算法（http://www.math.ucsd.edu/ ~ronspubs/72_10_convex_hull.pdf）来计算它。Graham 扫描的时间复杂度主要由排序步骤决定。其余的是线性的。

于 2013-10-11T13:56:35.120 回答
0

一般来说，没有 O(n) 解决方案。有一个比 O(n log n) 更好的像素化版本。然而，它在其他方面是如此的笨拙，以至于你会疯狂地在实践中使用它。

您将第一个多边形（使用顶点 0、1、2）渲染到屏幕空间中，然后使用不同的 ID 重新渲染顶点本身，以便以后可以识别它们。例如，您可以将帧缓冲区清除为 RGBA ffffffff 并将 fffffffe 用于凸包覆盖的空间。每个顶点将使用其 ID 作为其 RGBA 进行渲染；00000000、00000001 等

一个 16 位示例：

fffffffffffffff
fffffff0fffffff
ffffffeeeffffff
fffffeeeeefffff
ffffeeeeeeeffff
fffeeeeeeeeefff
ff2eeeeeeeee1ff
fffffffffffffff

检查新点是在当前帧缓冲区中的简单查找。如果它占据的像素被多边形或顶点ID“着色”，则新顶点被拒绝。

如果新顶点在现有多边形之外，您会在新顶点和凸包内的某个点之间找到第一个像素（第一个多边形中间的东西可以正常工作）并沿着包的圆周行进 - 在两个方向上- 直到你发现自己在新顶点的船体远端。（我将把这个作为练习留给用户。从效率的角度来看，有很多解决方案都很糟糕。）填充由这两个点定义的多边形和带有多边形空间 ID 的新顶点 - 小心不要擦除任何顶点 ID - 并继续下一个像素。

完成后，包含未完全被外壳 ID 包围的顶点 ID 的任何像素都是凸外壳顶点。

虽然该算法的复杂度是 O(n) 与顶点的数量，但它的缺陷是显而易见的。 除非他们有一个荒谬、疯狂、惊人数量的点要处理，以至于几乎每个顶点都会立即被拒绝，并且除非他们能够接受别名结果的限制，否则他们头脑正常的人不会使用它。

朋友不要让朋友实现这个算法。

于 2010-07-30T23:03:29.107 回答
0

如果您的点来自有限宇宙（实践中总是如此），您可以进行基数排序，然后运行 ​​Andrew 的单调链算法。

于 2017-05-23T19:58:06.687 回答