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