如何以最高效方式求解两个凸多边形并集的凸包？

针对两个已按顺时针排序的凸多边形，最高效的解法是线性时间的双指针合并法，时间复杂度仅为O(α+β)，比把所有点混在一起跑通用凸包算法（O((α+β)log(α+β))）快得多，完全适配你的需求。

具体步骤 #

1. 确定凸包起始点
   直接从p₁和q₁里挑出并集的最北端西侧点——也就是y坐标最大，若y相同则x坐标最小的点，这就是要求的r₁。

2. 双指针遍历构建凸包

   • 给两个多边形分别设指针i和j：如果r₁是p₁，则i初始指向p₁，j初始指向q₁；反之则交换初始指向。
   • 每次循环中，比较当前指针指向的点的下一个点（注意多边形是环形的，比如P的最后一个点的下一个是p₁），用叉积判断哪个点应该加入凸包：
     假设当前凸包最后一个点是curr，P的下一个点是next_p，Q的下一个点是next_q，计算叉积cross(next_p - curr, next_q - curr)：
     • 若叉积≤0：说明从curr→next_p→next_q是顺时针转向（或共线），此时next_p更贴合凸包的外部，把next_p加入凸包，移动指针i到下一个位置。
     • 若叉积>0：说明next_q更靠外，把next_q加入凸包，移动指针j到下一个位置。
   • 重复上述步骤，直到i和j都回到初始位置，遍历结束。

3. 收尾处理

   • 遍历过程中如果遇到共线点，只保留距离当前curr最远的那个，避免凸包出现冗余顶点。
   • 如果其中一个多边形完全被另一个包含，遍历会自动跳过内部多边形的所有点，最终得到的凸包就是外部多边形本身。

关键原理 #

因为两个输入都是已排序的凸多边形，它们的顶点沿顺时针方向严格按凸包顺序排列，双指针法利用这个有序性，每次都能直接选出当前最外侧的点，不需要排序或额外的点筛选，全程线性遍历，是理论上的最优时间复杂度方案。

内容的提问来源于stack exchange，提问作者Hammerite