algorithm - 一种计算顶点数的算法

Question

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

有什么办法吗？

Answer 1

旋转卡尺是解决此类问题的有力工具。

看这篇文章The Convex Hull of Two Convex Polygons的2.6部分

评论：我相信这是非常简单的算法。

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

查看文章（和其他 rot.cal. 描述）了解详细信息。

请注意，此算法类似于礼品包装