复杂多边形的凸包有线性时间算法吗?

如果您的点集是这样的一些非比较的排序机制(如基数排序)将快于比较的方法,那么似乎您可以使用格雷厄姆扫描算法( http://www.math.ucsd.edu/~ronspubs/72_10_convex_hull.pdf

我很确定不会。任意点集上的凸包等价于排序。我们可以对任意点集进行排序,并将这些点按顺序连接起来,使之成为一个 ,从而将任意点集的问题简化为您的问题。

这里有一个链接到 proof 这个凸包等价于排序。我他妈的太懒了,打字员太差了,我自己写不出来。

一般来说,不存在O(n)解。有一个像素化版本比O(n logn)更好。然而,它在其他方面是如此的蹒跚,以至于你在实践中使用它是疯狂的。

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

fffffffffffffff
fffffff0fffffff
ffffffeeeffffff
fffffeeeeefffff
ffffeeeeeeeffff
fffeeeeeeeeefff
ff2eeeeeeeee1ff
fffffffffffffff

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

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

除非他们有一个荒谬的,疯狂的,惊人的分数,否则没有人会用它 使几乎每个顶点都立即被拒绝的处理,除非它们能接受一个混叠结果的限制。

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

如果你的点来自一个有限的宇宙(在实践中总是这样),你可以做基数排序,然后运行安德鲁的单调链算法。