重叠矩形凸包及外边界提取高效算法求解咨询

你要实现的是轴对齐矩形并集的外轮廓生成，常规凸包算法只能输出凸多边形，满足不了你要非凸结果的需求，目前最高效的实现方案是扫描线算法，时间复杂度为O(n log n)，可支持无数量上限的矩形输入，具体实现步骤如下：

• 预处理所有矩形，提取每个矩形的左右两条垂直边，每条边记录三个属性：x轴坐标、对应的y轴覆盖区间（矩形的y_min、y_max）、边类型（左边界/右边界）
• 对所有提取到的垂直边按x坐标升序排序，若x坐标相同，左边界排序优先级高于右边界
• 初始化一个激活y区间列表，用于记录当前扫描线位置被矩形覆盖的y轴范围
• 从左到右依次扫描每一条垂直边：
  1. 对比当前激活y区间和上一个扫描位置的激活y区间的差异，记录两个x坐标之间的水平和垂直边界线段
  2. 如果当前处理的是左边界，将其对应的y区间加入激活列表；如果是右边界，将对应的y区间从激活列表中移除
• 最后将所有记录的边界线段的端点按顺序拼接，即可得到完整的非凸外轮廓多边形

如果你的输入包含非轴对齐的旋转矩形，可改用Vatti多边形裁剪算法先计算所有矩形的并集，再提取并集的边界即可。

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