algorithm - 计算顶点数的算法

Question

令 CH1 和 CH2 为两个凸多边形。给出一个算法，计算与顶点数成线性关系的并集的凸包，证明它适用于两个多边形之间相互关系的所有不同可能情况。

有什么办法吗？

Answer 1

Rotating calipers是解决此类问题的有力工具。

查看 this article 的第 2.6 部分两个凸多边形的凸包

评论:我确信这是非常简单的算法。

• 从垂直线开始。
• 找到两个多边形最左边的点。选择其中最左边的一个。它属于船体。
• 在这一点上固定线。
• 围绕这一点旋转线直到它接触下一个点(从两个多边形)(注意您只需要向前搜索，所以总时间是 O(m+n))
• 将此点添加到船体，固定线。
• 重复。

有关详细信息，请查看文章(和其他 rot.cal. 描述)。

请注意，此算法类似于 gift wrapping