是否有线性时间算法来查找复杂多边形的凸包？
我知道有一个最坏情况的 O(n log n) 算法用于查找复杂多边形的凸包，还有一个最坏情况的 O(n) 算法用于查找简单多边形的凸包。是否有最坏情况的 O(n) 算法来查找复杂多边形的凸包？
复杂多边形是线段可以相交的多边形。查找复杂多边形的凸包相当于查找无序列表的凸包。
I know there's a worst-case O(n log n) algorithm for finding the convex hull of a complex polygon and a worst-case O(n) algorithm for finding the convex hull of a simple polygon. Is there a worst-case O(n) algorithm for finding the convex hull of a complex polygon?
A complex polygon is a polygon where the line segments may intersect. Finding the convex hull of a complex polygon is equivalent to finding the convex hull of an unordered list of points.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
如果您的点集使得某些基于非比较的排序机制（如基数排序）比基于比较的方法更快，那么您似乎可以使用格雷厄姆扫描算法（http://www.math.ucsd.edu/~ronspubs/72_10_convex_hull.pdf）来计算它。格雷厄姆扫描的时间复杂度由排序步骤决定。其余的都是线性的。
If your point sets are such that some non-comparison based sorting mechanism (like radix sort) will be faster than comparison based methods, then it seems you can use the Graham scan algorithm (http://www.math.ucsd.edu/~ronspubs/72_10_convex_hull.pdf) to compute it. The time complexity of the Graham scan is dominated by the sorting step. The rest is linear.
我很确定不是。任意点集上的凸包可以证明等价于排序。我们可以对任意点集进行排序，并将这些点按顺序连接起来，使其成为一个复杂多边形，从而减少任意点集上的问题。
这是一个证明的链接，证明凸包是相当于排序。我实在是太懒了，而且打字员太差劲，无法自己把它写出来。
I'm pretty sure not. Convex hull on arbitrary point sets can be shown to be equivalent to sorting. We can order an arbitrary point set and connect the points in sequence making it into a complex polygon, thereby reducing the problem on arbitrary point sets to yours.
Here is a link to a proof that convex hull is equivalent to sorting. I'm too damn lazy and too bad a typist to write it out myself.
一般来说，不存在 O(n) 解。有一个比 O(n log n) 更好的像素化版本。然而，它在其他方面却受到很大的阻碍，以至于你在实践中使用它会很疯狂。
您将第一个多边形（使用顶点 0、1、2）渲染到屏幕空间中，然后使用不同的 ID 重新渲染顶点本身，以便稍后可以识别它们。例如，您可以将帧缓冲区清除为 RGBA ffffffff，并将 fffffffe 用于凸包覆盖的空间。每个顶点将使用其 ID 作为 RGBA 进行渲染； 00000000、00000001 等。
16 位示例：
检查新点是在当前帧缓冲区中进行简单查找。如果它占用的像素被多边形或顶点 ID '着色'，则新顶点将被拒绝。
如果新顶点位于现有多边形之外，您会找到新顶点和凸包内某个点之间的第一个像素（第一个多边形中间的某个点可以正常工作）并沿着包的圆周行进 - 在两个方向上- 直到您发现自己位于船体距离新顶点较远的一侧。 （我将把这个作为练习留给用户。从效率的角度来看，有很多解决方案都很糟糕。）用多边形空间的 ID 填充由这两个点定义的多边形和新顶点 - 小心不擦除任何顶点 ID - 并继续处理下一个像素。
完成后，任何包含未完全被外壳 ID 包围的顶点 ID 的像素都是凸包顶点。
虽然该算法的复杂度为O(n)（随着顶点数量的增加），但其缺陷也是显而易见的。 任何头脑正常的人都不会使用它，除非他们有大量荒谬、疯狂、惊人的点需要处理，这样几乎每个顶点都会立即被拒绝，并且除非他们能够接受别名结果的限制。
朋友不要让朋友实现这个算法。
In general, no there is not a O(n) solution. There is a pixelated version that is better than O(n log n). It is, however, so hobbled in other ways that you'd be crazy to use it in practice.
You render the first polygon (using verts 0, 1, 2) into screen space, then re-render the verts themselves using a distinct ID so they can be identified later. For example, you might clear the frame buffer to RGBA ffffffff and use fffffffe for space that is covered by the convex hull. Each vertex would be rendered using its ID as its RGBA; 00000000, 00000001, etc.
A 16-bit example:
Checking a new point is a simple lookup in the current frame buffer. If the pixel it occupies is 'shaded' with polygon or with a vertex ID, the new vertex is rejected.
If the new vertex is outside the existing polygon, you find the first pixel between the new vertex and some point inside the convex hull (something in the middle of the first poly works fine) and march along the circumference of the hull - in both directions - until you find yourself on the far side of the hull from the new vertex. (I'll leave this as an exercise to the user. There are plenty of solutions that all suck, from an efficiency perspective.) Fill in the poly defined by these two points and the new vertex with the ID for polygon space - being careful not to erase any vertex IDs - and go on to the next pixel.
When you're done, any pixel which contains a vertex ID that is not completely surrounded by hull IDs is a convex hull vertex.
While the algorithm's complexity is O(n) with the number of vertices, it's deficiencies are obvious. Nobody in their right mind would use it unless they had a ridiculous, insane, staggering number of points to process so that nearly every vertex would be immediately rejected, and unless they could accept the limitation of an aliased result.
Friends don't let friends implement this algorithm.
如果您的点来自有限宇宙（实践中总是如此），您可以进行基数排序，然后运行安德鲁单调链算法。
If your points come from a finite universe (which is always the case in practice) you can do radix sort and then run Andrew's monotone chain algorithm.