What is a tidy algorithm to find overlapping intervals?

Question

I'm sure this must have been asked before, but I'm not finding it: I'm only finding related, but harder questions.

I've got four points, representing two lines like this:

       A         C      B   D
|------*---|-----+----|-*---+---|----------|
0          10         20        30         40

So in the example, AB = {7, 21} and CD = {16,26}. (The lines could be in any relation to each other, and any size.) I want to find out whether or not they overlap, and by how much if so. (In the example, the answer would be 5.) My current solution involves a bunch of complicated if/then steps, and I can't help but think there's a nice arithmetical solution. Is there?

(P.S. Really, I'm doing bounding-box intersection, but if I can get it in one dimension, the other will be the same, obviously.)

Answer 1

Try this:

intersects = (max(a,b) > min(c,d)) && (min(a,b) < max(c,d))
overlap = min(max(a,b), max(c,d)) - max(min(c,d), min(a,b))

If you can assume a <= b and c <= d:

intersects = (b > c) && (a < d)
overlap = min(b, d) - max(c, a)

You can also calculate intersects as follows:

intersects = (overlap > 0)