二维平面多边形：计算消除重叠所需的精确位移向量

不需要用循环试探的低效方法，直接通过几何分析和顺序处理就能得到每个多边形的最小Y轴上移量，步骤如下：

1. 提取多边形关键几何参数 #

对每个多边形，先计算三个核心参数：

• X投影区间：[x_min, x_max]，即所有顶点X坐标的最小值和最大值
• 底部Y坐标：y_bot，所有顶点Y坐标的最小值
• 顶部Y坐标：y_top，所有顶点Y坐标的最大值

X轴可以视为一个特殊的“多边形”，其X投影是(-∞, +∞)，顶部Y坐标为0。

2. 确定处理顺序 #

必须从下到上处理：按多边形初始的y_bot从小到大排序，先处理最靠近X轴的多边形，处理完成后固定其最终位置，再依次处理上方的多边形。这样能保证计算上方多边形的上移量时，下方所有可能的碰撞对象位置都是确定的。

3. 计算单个多边形的最小上移量 #

对当前待处理的多边形P：

1. 筛选所有已固定位置的对象（包括X轴和已处理完的多边形），满足：
   • 对象的X投影与P的X投影存在重叠（即obj.x_min < P.x_max 且 P.x_min < obj.x_max）
   • 对象的顶部Y坐标 > P当前的y_bot（说明P当前位置与该对象有垂直重叠）
2. 对每个符合条件的对象，计算P需要上移的距离：required_delta = obj.y_top - P.y_bot
3. 所有required_delta中取最大值，如果没有符合条件的对象，required_delta取0。这个值就是P的最小精确上移量。

示例 #

假设P当前y_bot=3，同时和X轴（y_top=0）以及已固定的多边形Q（y_top=5）重叠：

• 针对X轴的required_delta = 0 - 3 = -3（负数表示不需要上移）
• 针对Q的required_delta = 5 - 3 = 2
• 取最大值2，将P上移2单位后，P的y_bot变为5，刚好贴在Q顶部，无任何重叠。

4. 应用平移 #

得到delta_y后，直接将P的所有顶点Y坐标加上delta_y即可，这就是线性的平移操作，和你提到的线性插值逻辑一致——本质是对Y坐标做线性偏移。

效率对比 #

• 循环试探：每次上移后都要做全局重叠检测，时间复杂度高，且步长设置不当会导致结果不精确。
• 精确计算：仅需一次排序+每个多边形的候选碰撞检测，时间复杂度为O(n²)（n为多边形数量），如果用空间划分（比如区间树）优化碰撞候选筛选，还能降到O(n log n)，效率远高于试探法。

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