Collision Detection

I was doing a code-read for a team member earlier this year, and stumbled upon an elegant algorithm. This is super-simple, I realize, but I believe it’s a great example of avoiding complexity. Einstein said it best – “as simple as possible, but no simpler”.

Problem : Given two solid rectangular shapes, make sure that they do not overlap in either horizontal or vertical placement in an X-Y layout.

Proposed Solution: My team-mate proposed a solution that was rigorous and thorough. To simplify the explanation, we’ll start with the analysis in one dimension. I’ll address the two rectangles as A and B, and the X-axis as left to right (left being lower numbers). He identified that we could have an overlap of the two rectangles in any of the following cases:

1. when the right edge of A was between the left and right edges of B

2. when the left edge of A was between the left and right edges of B

3. when the left edge of A was left of the left edge of B AND the right edge of A was to the right of the right edge of B

Note that when “A” is completely inside “B”, both conditions 1 & 2 would apply

He also accounted for colinear edges.

His analysis was good – he identified all of the possible overlaps, and his implementation was straightforward (NOTE: I tried to write this in pseudocode, but the wordpress parser was very unhappy with all of the less-than and greater-thans):

He implemented simple checks for conditions 1,2 and 3.
Not too bad, if only looking at one dimension. However, this was complicated by being two-dimensional, so within each of the above checks, there were permutations to consider. In my expression below – consider “X1″ to be “condition 1, applied along the X axis”, and “Y3″ to be “condition 3, along the Y axis”. His algorithm then became:
IF(
(X1 AND (Y1 OR Y2 OR Y3))
OR
(X2 AND (Y1 OR Y2 OR Y3))
OR
(X3 AND (Y1 OR Y2 OR Y3))
)
THEN collision == TRUE;
So, he ultimately checked all 9 permuations (overlap of left or right, or inclusion; versus each of overlap of top or bottom, or inclusion).

Elegant Solution:

There were 9 ways that an overlap could exist. It was much easier to define that an overlap did NOT exist:

Conditions refactored:

  1. the right edge of A is to the left of the left edge of B
  2. the left edge of A is to the right of the right edge of B
  3. the bottom of A is above the top of B
  4. the top of A is below the bottom of B

Each of these conditions describes a circumstance that can never be an overlap (of rectangles) – so only if none of these conditions is true, will there be an overlap.

My proposed algorithm, which we implemented, was

IF NOT(1 OR 2 OR 3 OR 4) THEN collision == TRUE;

Much simpler. This is the type of thing that I strive for, and hope to share with you when I describe “elegance in design” of algorithms.

We actually implemented “IF NOT(2 OR 1 OR 3 OR 4)…” because “2″ was the most common case, this operation was done thousands of times in a layout-calculation for a real-time user interface, and we wanted the minor performance benefit of short circuiting the operation.
Scott

One thought on “Collision Detection

  1. Richard Krog said,

    December 5, 2005 at 10:45 am · Edit

    I came across a problem just like the overlapping rectangles, but with only one dimention — time. “Do date ranges overlap?” We came up with:

    Overlap = A.start before B.end && B.start before A.end

    Likewise, you can remove the negative logic with the following:

    1. the right edge of A is to the *RIGHT* of the left edge of B
    2. the left edge of A is to the *LEFT* of the right edge of B
    3. the bottom of A is *BELOW* the top of B
    4. the top of A is *ABOVE* the bottom of B

    IF (1 && 2 && 3 && 4) THEN collision == TRUE;

    Both solutions are fail-fast, so the change is mostly semantic.

Leave a Reply

Your email address will not be published. Required fields are marked *