如何修复重叠矩形的无限循环？

Question

我正在使用这篇文章（“分离行为”部分）中的方法来分散重叠的矩形。它“以一定的速度同时迭代地移动所有矩形，该速度由它们与其他矩形的重叠方式决定。” （请注意，我仅垂直移动矩形。）

我有两种类型的矩形：真实的和虚拟的。虚拟矩形不允许移动（并且在下图中是透明的）。我的问题是，对于矩形的某种排列，我的实现无限循环。只有一个真实矩形（“Cell Vector”）与三个虚拟矩形（“Frame.015”、“Frame.013”、“Frame.012”）相交，并且在移动量之间进行触发器。

在分散所有其他真实矩形之后，这就是它无限期地保持原样，没有任何移动：

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()

中，如果我在标准化之前将向量的 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 
...  

为什么会出现这种情况？我该如何解决它？

Answer 1

在我看来，只有在没有固定矩形的情况下才能保证分离行为。正如您所发现的，矩形可以无限循环地推送。

当一块位于许多虚拟矩形中时，您希望发生什么？总是往上走？一旦你决定了你想要什么，我想解决方案就会水到渠成。