Overlapping intervals

[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.


Bob Rogers <rogers@darwin.bu.edu>
Last modified: Sat Jun 25 18:34:06 EDT 2011