Determing whether two ranges overlap

[Ralf Muschall]

Robin Haswell wrote:

> I can think of lots of ways to do this but it's in a tight loop so I need
> it to be as efficient as possible. Any help welcome :-)

There are 24 possibilities of having 4 numbers in a row, and
the following 6 of them describe nonempty intervals (the remaining
18 are obtained by reversing the endpoints of one or both
intervals, thereby making them empty):

# separate
a0 a1 b0 b1
b0 b1 a0 a1

# inside
a0 b0 b1 a1
b0 a0 a1 b1

# cross
a0 b0 a1 b1
b0 a0 b1 a1

The simplest is to exclude the first pair, i.e.

not (a1<b0 or b1<a0)

which simplifies to
a1>=b0 and b1>=a0, given by Fredrik without proof ;-)

You will have to decide whether you want ">" or ">="
(beware of the former when using floats).

If you cannot assume that the pairs are in order, this
will break.

Ralf