What's the most efficient way to test two integer ranges for overlap?

0 votes
asked Jul 16, 2010 by williamkf

Given two inclusive integer ranges [x1:x2] and [y1:y2], where x1 ≤ x2 and y1 ≤ y2, what is the most efficient way to test whether there is any overlap of the two ranges?

A simple implementation is as follows:

bool testOverlap(int x1, int x2, int y1, int y2) {
  return (x1 >= y1 && x1 <= y2) ||
         (x2 >= y1 && x2 <= y2) ||
         (y1 >= x1 && y1 <= x2) ||
         (y2 >= x1 && y2 <= x2);
}

But I expect there are more efficient ways to compute this.

What method would be the most efficient in terms of fewest operations.

10 Answers

0 votes
answered Jul 16, 2010 by blueraja-danny-pflug
return x2 >= y1 && x1 <= y2;
0 votes
answered Jul 16, 2010 by simon-nickerson

What does it mean for the ranges to overlap? It means there exists some number C which is in both ranges, i.e.

x1 <= C <= x2

and

y1 <= C <= y2

Now, if we are allowed to assume that the ranges are well-formed (so that x1 <= x2 and y1 <= y2) then it is sufficient to test

x1 <= y2 && y1 <= x2
0 votes
answered Jul 16, 2010 by mark-h

You have the most efficient representation already - it's the bare minimum that needs to be checked unless you know for sure that x1 < x2 etc, then use the solutions others have provided.

You should probably note that some compilers will actually optimise this for you - by returning as soon as any of those 4 expressions return true. If one returns true, so will the end result - so the other checks can just be skipped.

0 votes
answered Jul 16, 2010 by haywood-jablomey

Here's my version:

int xmin = min(x1,x2)
  , xmax = max(x1,x2)
  , ymin = min(y1,y2)
  , ymax = max(y1,y2);

for (int i = xmin; i < xmax; ++i)
    if (ymin <= i && i <= ymax)
        return true;

return false;

Unless you're running some high-performance range-checker on billions of widely-spaced integers, our versions should perform similarly. My point is, this is micro-optimization.

0 votes
answered Jul 19, 2010 by ruslik

I suppose the question was about the fastest, not the shortest code. The fastest version have to avoid branches, so we can write something like this:

for simple case:

static inline bool check_ov1(int x1, int x2, int y1, int y2){
    // insetead of x1 < y2 && y1 < x2
    return (bool)(((unsigned int)((y1-x2)&(x1-y2))) >> (sizeof(int)*8-1));
};

or, for this case:

static inline bool check_ov2(int x1, int x2, int y1, int y2){
    // insetead of x1 <= y2 && y1 <= x2
    return (bool)((((unsigned int)((x2-y1)|(y2-x1))) >> (sizeof(int)*8-1))^1);
};
0 votes
answered Jul 15, 2012 by kfl

Given two ranges [x1,x2], [y1,y2]

def is_overlapping(x1,x2,y1,y2):
    return max(x1,y1) <= min(x2,y2)
0 votes
answered Jul 18, 2014 by floatingrock

This can easily warp a normal human brain, so I've found a visual approach to be easier to understand:

Overlap madness

le Explanation

I find it easier to understand when visualized this way. If two ranges are "too fat" to fit in a slot that is exactly the sum of the width of both, then they overlap.

For ranges [x1, x2] and [y1, y2] this would be:

/**
 * we are testing for:
 *     max point - min point < w1 + w2    
 **/
if max(x2, y2) - min(x1, y1) < (x2 - x1) + (y2 - y1) {
  // too fat -- they overlap!
}
0 votes
answered Jul 2, 2016 by damluar

Great answer from Simon, but for me it was easier to think about reverse case.

When do 2 ranges not overlap? They don't overlap when one of them starts after the other one ends:

dont_overlap = x2 < y1 || x1 > y2

Now it easy to express when they do overlap:

overlap = !dont_overlap = !(x2 < y1 || x1 > y2) = (x2 >= y1 && x1 <= y2)
0 votes
answered Jul 12, 2016 by axe-labs

Subtracting the Minimum of the ends of the ranges from the Maximum of the beginning seems to do the trick. If the result is less than or equal to zero, we have an overlap. This visualizes it well:

enter image description here

0 votes
answered Jul 27, 2016 by yankuan-zhang

If you were dealing with, given two ranges [x1:x2] and [y1:y2], natural / anti-natural order ranges at the same time where:

  • natural order: x1 <= x2 && y1 <= y2 or
  • anti-natural order: x1 >= x2 && y1 >= y2

then you may want to use this to check:

they are overlapped <=> (y2 - x1) * (x2 - y1) >= 0

where only four operations are involved:

  • two subtractions
  • one multiplication
  • one comparison
Welcome to Q&A, where you can ask questions and receive answers from other members of the community.
Website Online Counter

...