[Originally referenced from an item posted on 7-Oct-99 to the "Hint on testing intervals for overlap" thread of "Problem Set 2", formerly one of the the www.photo.net Discussion Forums. -- rgr, 30-Apr-04.]
Home : Overlapping intervals
Although the second bullet item in Excercise 3b of Problem Set 2 refers to the SQL between operator, this is something of a red herring. It is much simpler to use the following equation for overlap testing:
Two intervals i1 = (s1, e1) and i2 = (s2, e2) overlap if and only if
s2 < e1 and s1 < e2
This is for "open intervals," where the endpoints are not part of the
interval, so "touching" is not considered an overlap.
Is it really this simple? Consider the following informal proof. Although there are four ways for two intervals to overlap, they can only fail to overlap in two ways: either i1 comes before i2, or i2 comes before i1. If i1 is before i2, then e1 (the endpoint of i1) must be less than s2 (the start of i2), and similarly for the other nonoverlap case. The "touching" cases involve equalities, which don't count for open intervals, so we must use "<=" to compare endpoints. So the test for nonoverlap becomes
e1 <= s2 or e2 <= s1
and the test for overlap is simply the negation of that.
As a further point, consider that intervals are already internally ordered, so we already know that
s1 < e1, and
s2 < e2.
(We assume the intervals are non-empty, since an empty open interval is
pretty trivial.) This means that if either of the nonoverlap test
clauses is true, we have complete knowledge of the ordering of all four
values:
e1 <= s2 implies s1 < e1 <= s2 < e2;
e2 <= s1 implies s2 < e2 <= s1 < e1.
This shows why we don't need to perform any more comparisons, if we are
only interested in nonoverlap (or its negation).
To test for rectangle overlap, computer graphics programmers use this interval test twice, once for the X coordinates and again for the Y coordinates. This is where I learned the trick.