如何合并两个纠缠的凸包（例如this https://i.stack.imgur.com/ALM4G.jpg）使用格雷厄姆扫描或任何其他算法在线性时间内形成凸包？
基本上，你使用安德鲁的修改 https://en.wikibooks.org/wiki/Algorithm_Implementation/Geometry/Convex_hull/Monotone_chain格雷厄姆扫描算法。
将点按 xy 顺序排序后，计算上壳和下壳linear时间。由于您已经拥有两个凸包，因此凸包点的 xy 排序也将采用linear时间（例如，反转下部外壳并对四个排序列表进行合并排序）。
由于算法的其余部分将花费线性时间，因此总体运行时间按照您的要求是线性的。
这里有一个参考一些简短的Python代码 https://gist.github.com/arthur-e/5cf52962341310f438e96c1f3c3398b8实施安德鲁对格雷厄姆扫描的修改。另请参阅我的回答here https://stackoverflow.com/a/71725431/9702190.
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
