是否有线性时间算法来查找复杂多边形的凸包?
我知道有一个最坏情况的 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)
一般来说,不存在 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)(随着顶点数量的增加),但其缺陷也是显而易见的。 任何头脑正常的人都不会使用它,除非他们有大量荒谬、疯狂、惊人的点需要处理,这样几乎每个顶点都会立即被拒绝,并且除非他们能够接受别名结果的限制。
朋友不要让朋友实现这个算法。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱,如果其他用户或者作者回复了您的评论,将不能在第一时间通知您!
如果您的点集使得某些基于非比较的排序机制(如基数排序)比基于比较的方法更快,那么您似乎可以使用格雷厄姆扫描算法(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.