*[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 ifs2 < e1 and s1 < e2This 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 *non*overlap becomes

e1 <= s2 or e2 <= s1and 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.

Bob Rogers