合并两个缠绕的凸壳

Question

如何在线性时间内将两个缠绕的凸壳(如这)合并成凸壳，使用格雷厄姆扫描或任何其他算法？

Answer 1

基本上，您使用格雷厄姆扫描算法的安德鲁修改。

将点按xy阶排序后，用线性时间计算上、下船体.由于已经有两个凸壳，凸壳点的xy排序也将花费线性时间(例如，反转较低的外壳和合并排序四个排序列表)。

由于算法的其余部分将花费线性时间，所以整个运行时是线性的，这是您所要求的。

以下是对一些简短的python代码实现安德鲁对格雷厄姆扫描的修改的参考。也见我的答案，这里。