如何解决重叠矩形分散算法中的无限循环问题？

我参考Mike Kling文章「分离行为」章节的重叠矩形分散方法，实现仅垂直移动矩形的逻辑。场景里有两类矩形：真实矩形（可移动） 和 虚拟矩形（不可移动）。当前单个真实矩形（'Cell Vector'）与三个虚拟矩形（'Frame.015'、'Frame.013'、'Frame.012'）重叠，导致程序陷入无限循环，移动量来回摆动。完成其他真实矩形的分散后，界面状态不再变化：

界面状态：单个真实矩形（标注为'Cell Vector'）与三个虚拟矩形重叠，其他真实矩形已完成分散，界面停止更新。

当前实现代码如下：

def rect_overlap_velocity(rect1, vectors):
    vec = Vector((0, 0))
    count = 0

    v1 = vectors[rect1]
    centre = (v1[0] + v1[1]) / 2

    for rect2, v2 in vectors.items():
        if rect1 != rect2 and rectangles_overlap(v1, v2):
            vec += ((v2[0] + v2[1]) / 2) - centre
            count += 1

    if not count:
        return vec

    # vec.x = 0
    vec /= count
    vec.negate()
    vec.normalize()

    return vec


def disperse_rectangles():
    real_rectangles = get_real_rectangles()
    vectors = get_rect_vectors(real_rectangles)

    pairs = [(vectors[r1], vectors[r2])
      for r1, r2 in combinations(vectors, 2)
      if r1 in real_rectangles or r2 in real_rectangles]

    while any(rectangles_overlap(v1, v2) for v1, v2 in pairs):
        for rect in real_rectangles:
            tr, bl = vectors[rect]
            vec = rect_overlap_velocity(rect, vectors)
            tr.y += vec.y
            bl.y += vec.y

补充信息：在rect_overlap_velocity()中，若归一化前设置vec.x=0，每次迭代的移动方向会在1.0和-1.0间来回翻转；若不设置，振荡周期更长，但始终无法解决重叠问题，部分移动量数据如下：

0.9677687883377075
-0.04892580956220627
-0.04962211474776268
-0.0503283366560936
-0.05104447528719902
-0.051770735532045364
-0.05250733345746994
-0.05325426161289215
-0.054011743515729904
-0.05477996915578842
-0.0555589534342289
-0.056349121034145355
-0.05715003237128258
-0.05796253681182861
-0.05878620222210884
-0.059621673077344894
-0.060468729585409164
-0.06132778525352478
-0.06219884753227234
0.9677560329437256 
...  

问题成因 #

1. 方向计算逻辑缺陷：当前代码计算真实矩形到所有重叠虚拟矩形中心的平均偏移向量，取反后归一化。当真实矩形被多个虚拟矩形从上下两侧同时重叠时，垂直方向的合力会在正负间反复切换——移动后仍与部分虚拟矩形重叠，导致下一次计算的方向直接反转，形成振荡。
2. 无阻尼的固定幅度移动：每次移动都使用归一化后的单位向量，移动幅度固定，无法根据重叠程度调整步长。当真实矩形处于多个虚拟矩形的「夹缝」中时，单次移动无法完全脱离重叠，反而触发反向移动，陷入死循环。
3. 未针对虚拟矩形优化逻辑：代码未区分真实/虚拟矩形的属性，虚拟矩形不可移动，但仍被纳入向量计算，真实矩形的移动无法改变与虚拟矩形的相对位置矛盾，进一步放大振荡问题。

修复方案 #

1. 优化分离方向计算，优先选择单一脱离方向 #

不再计算平均偏移向量，改为统计上下方向的重叠权重（结合重叠距离），选择能脱离更多重叠的方向移动，同时根据重叠程度调整步长：

def rect_overlap_velocity(rect1, vectors):
    vec = Vector((0, 0))
    up_weight = 0  # 向上移动的权重（虚拟矩形在下方）
    down_weight = 0  # 向下移动的权重（虚拟矩形在上方）

    v1 = vectors[rect1]
    r1_top = v1[0].y
    r1_bottom = v1[1].y
    r1_centre_y = (r1_top + r1_bottom) / 2

    for rect2, v2 in vectors.items():
        if rect1 != rect2 and rectangles_overlap(v1, v2):
            r2_centre_y = (v2[0].y + v2[1].y) / 2
            # 计算垂直重叠距离，作为权重依据
            overlap_top = min(r1_top, v2[0].y)
            overlap_bottom = max(r1_bottom, v2[1].y)
            overlap_dist = overlap_top - overlap_bottom if overlap_top > overlap_bottom else 1

            if r2_centre_y > r1_centre_y:
                # 虚拟矩形在上方，优先向下移动
                down_weight += overlap_dist
            else:
                # 虚拟矩形在下方，优先向上移动
                up_weight += overlap_dist

    # 选择权重更大的方向
    if up_weight > down_weight:
        vec.y = 1.0
    elif down_weight > up_weight:
        vec.y = -1.0
    else:
        # 上下权重相等时，默认选向上
        vec.y = 1.0

    # 根据总重叠量调整步长，避免固定幅度振荡
    total_overlap = up_weight + down_weight
    if total_overlap > 0:
        vec.y *= min(total_overlap * 0.3, 4.0)  # 限制最大步长，防止过度移动

    vec.x = 0  # 强制仅垂直移动
    return vec

2. 添加阻尼与迭代限制，避免无限循环 #

在主函数中限制最大迭代次数，同时给移动添加阻尼，让振荡逐渐收敛：

def disperse_rectangles():
    real_rectangles = get_real_rectangles()
    vectors = get_rect_vectors(real_rectangles)
    max_iterations = 150  # 限制最大迭代次数
    iteration = 0
    damping_factor = 0.9  # 移动幅度衰减系数

    while iteration < max_iterations:
        iteration += 1
        has_overlap = False

        # 仅检查真实矩形与其他矩形的重叠
        for rect in real_rectangles:
            v1 = vectors[rect]
            is_overlapped = False
            for rect2, v2 in vectors.items():
                if rect != rect2 and rectangles_overlap(v1, v2):
                    is_overlapped = True
                    has_overlap = True
                    break
            if is_overlapped:
                tr, bl = vectors[rect]
                vec = rect_overlap_velocity(rect, vectors)
                vec.y *= damping_factor  # 添加阻尼
                tr.y += vec.y
                bl.y += vec.y

        # 无重叠则提前退出循环
        if not has_overlap:
            break

3. 明确区分真实与虚拟矩形的计算范围 #

在rect_overlap_velocity中，可以单独过滤虚拟矩形（如果有标记的话），仅计算真实矩形与虚拟矩形的重叠，避免不必要的计算干扰。

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