合并平面凸包得到最小周长结果的可用算法咨询

是存在成熟可落地的算法实现该需求的，以下是具体的方案说明：

首先明确：包含所有给定凸包的最小周长凸图形，本质就是所有输入凸包的并集的凸包，凸包的定义本身就保证了它是包含目标集合的最小凸集，对应周长也是最小的。

常用实现方案 #

• 中小规模输入通用方案
  直接提取所有输入凸包的全部顶点，将其作为一个整体点集，调用通用凸包算法计算即可，目前主流的通用凸包算法时间复杂度均为O(n log n)（n为所有顶点的总数量），足够应对绝大多数普通场景：

  • Andrew单调链算法：数值稳定性高，实现逻辑简单，是工业界最常用的凸包实现方案
  • Graham扫描法：原理易懂，适合学习场景使用

• 大规模输入优化方案
  因为输入本身已经是有序的凸包（顶点默认按顺时针/逆时针排列），可以用专门的多凸包合并优化算法，通过寻找凸包之间的公共切线、归并有序顶点序列的方式直接合并，时间复杂度可以优化到O(n)，适合总顶点数量极大、或者需要高频执行合并操作的场景。

注意：如果你的需求不是严格要求合并后的图形是凸包，只是要包含所有输入凸包的最小周长简单多边形，那对应的是另外一类凹包合并算法，但从你描述的需求来看，凸包合并就可以满足要求。

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