What's a simple algorithm for orthogonally separating two colliding rectangles using these primitive functions?

74 Views Asked by At

Suppose there are two colliding rectangles $R_0$, and $R_1$, and I'd like to separate them by only moving $R_1$. In the degenerate case that $R_1$'s center is equal to $R_0$'s and that they are concentric (same distances on all opposing sides), then assume that I've arbitrarily shifted $R_1$ slightly to account for that case.

The primitives are:

R.center()
R0.intersected(R1)
minBoundingRect([R0, R1])
R.topLeft(), R.topRight(), .., R.top(), R.bottom(), ..., R.bottomRight(), etc

where R.topLeft() and similar return corner points, while R.top() and similar return the respective coordinate's value. So that R.topRight() == (R.right(), R.top()) as a point.

The meanings of the primitives should be obvious, but ask if you're not sure.

Use whatever language including english, pseudocode, math symbols or python. I will make my answer as well, but you might have a better idea.

Assume all rectangle sides are parallel with the $xy$ axes, and that we're looking for the minimal axis-parallel move (hence orthogonal) to separate $R_1$ from $R_0$ so that it no longer collides. The final move is done by shifting the center point of $R_1$ by a delta.

1

There are 1 best solutions below

0
On BEST ANSWER
def orthogonalRectDelta(r0, r1):
    r0 = from_rect
    r1 = to_rect

    pairs = ((r0.top, r1.bottom()), (r0.bottom(), r1.top()), (r0.left(), r1.right()), (r0.right(), r1.left()))

    min_d = inf
    min_delta = QPointF()

    for k in range(0, len(pairs)):
        p = pairs[k]
        d = abs(p[0] - p[1])
        if d < min_d:
            min_d = d
            min_delta = QPointF(0, d) if k < 2 else QPointF(d, 0)

    return min_delta

Simplicity is best. Haven't tested this code yet, but the idea is conveyed.