31

Is there an effective way to find the overlap between two ranges?

All cases tha possible

Practically, the two ranges marked as (a - c), and (b - d), and I assume (c > a) && (d > b).

(b <= a <= d) which means if ((a >= b) && (d > a))
(b <= c <= d) which means if ((c >= b) && (d >= c))
(a <= b <= c) which means if ((b > a) && (c > b))
(a <= d <= c) which means if ((d > a) && (c > d))

But it never ends, because in this way I can find only one range at the time, and in each if I have to check the other cases as well.

For exemple, if the first condition (1) correct, I know what happening with the start of the range (a) I still need to check the others for the end of the range (c).

Not to mention that all this works in the case that (c > a) && (d > b), and not one of them is equal to another.

david
  • 439
  • 1
  • 4
  • 7
  • Are you just interesting in finding the overlap ? Or you want to merge the overlapping ranges? – Rahul Mar 16 '16 at 12:06
  • You want to check if 2 ranges are overlapping or not ? or you need to find the overlapped range ? – FallAndLearn Mar 16 '16 at 12:06
  • David, does that image describe your problem domain? – Mr. Polywhirl Mar 16 '16 at 12:20
  • `Practically, the two ranges marked as(a-c), and (b-d), and I assume (c>a)&&(d>b)` why not just take `int range = C - B` - if `(c>a)&&(d>b)` is always true this should be enough – messerbill Mar 16 '16 at 12:24
  • unfortunately it doesn't describe it quite well. I have to dealt with situations when a-c (or b-d) is contained in the other range, like 1-5 and 2-3. Or when it's vice versa to the image and the overlap in b-a – david Mar 16 '16 at 12:32
  • You may want to check the data structure called IntervallTree I do not know Java so I can't give showcase – RomainL. Mar 02 '22 at 22:32

8 Answers8

63

Two ranges overlap in one of two basic cases:

  • one range contains the other completely (i.e. both the start and end of one range are between the start and end of the other), or
  • the start or end of one range is contained within the other range

Conversely, they do not overlap only if neither endpoint of each range is contained within the other range (cases 11 and 12 in your diagram). We can check whether the low end of either range is past the high end of the other, to detect both those cases:

if (a > d || c < b) {
    // no overlap
}
else {
    // overlap
}

We can invert the condition and then use DeMorgan's laws to swap the order, if that's preferable:

if (a <= d && c >= b) {
    // overlap
}
else {
    // no overlap
}

To find the actual overlap range, you take the maximum of the two low ends, and the minimum of the two high ends:

int e = Math.max(a,b);
int f = Math.min(c,d);
// overlapping range is [e,f], and overlap exists if e <= f.

All above assumes that the ranges are inclusive, that is, the range defined by a and c includes both the value of a and the value of c. It is fairly trivial to adjust for exclusive ranges, however.

davmac
  • 20,150
  • 1
  • 40
  • 68
4

Use apache commons Range and its subclasses, especially the overlap method.

Boris Pavlović
  • 63,078
  • 28
  • 122
  • 148
3

The check for an overlap (just true/false) is actually quite easy:

Assume the ranges [a,b] and [c,d].

You have an overlap if: a <= d and b => c. This also works for a = b and/or c = d.

If you have an overlap then the overlapping range is [max(a,c),min(b,d)].

Thomas
  • 87,414
  • 12
  • 119
  • 157
3

You can detect the collision of two ranges by using a modified circular collision detection algorithm.

import java.util.Arrays;

public class RangeUtils {
    public static void main(String[] args) {
        int[] rangeA = { 10, 110 };
        int[] rangeB = { 60, 160 };
        int[] rangeC = intersectingRange(rangeA, rangeB);

        System.out.println("Range: " + Arrays.toString(rangeC)); // Range: [60, 110]
    }

    // Based on circular collision detection.
    public static boolean collisionDetected(int[] rangeA, int[] rangeB) {
        int distA = Math.abs(rangeA[1] - rangeA[0]) / 2;
        int distB = Math.abs(rangeB[1] - rangeB[0]) / 2;
        int midA = (rangeA[0] + rangeA[1]) / 2;
        int midB = (rangeB[0] + rangeB[1]) / 2;

        return Math.sqrt((midB - midA) * (midB - midA)) < (distA + distB);
    }

    public static int[] intersectingRange(int[] rangeA, int[] rangeB) {
        if (collisionDetected(rangeA, rangeB)) {
            return new int[] {
                Math.max(rangeA[0], rangeB[0]),
                Math.min(rangeA[1], rangeB[1])
            };
        }

        return null;
    }
}

Here is a visual example of the code; ported to JavaScript.

var palette = ['#393A3F', '#E82863', '#F6A329', '#34B1E7', '#81C683'];
var canvas = document.getElementById('draw');
var ctx = canvas.getContext('2d');

var rangeA = [10, 110];
var rangeB = [60, 160];
var rangeC = intersectingRange(rangeA, rangeB);

var collisionText = 'Range: [' + rangeC + ']';

var leftOffset = 18;
var topOffset = 24;

drawLines(ctx, [rangeA, rangeB], topOffset);
drawText(ctx, collisionText, leftOffset, topOffset);
drawBoundry(ctx, rangeC, topOffset);

// Based on circular collision detection.
function collisionDetected(rangeA, rangeB) {
  var distA = Math.abs(rangeA[1] - rangeA[0]) / 2;
  var distB = Math.abs(rangeB[1] - rangeB[0]) / 2;
  var midA = (rangeA[0] + rangeA[1]) / 2;
  var midB = (rangeB[0] + rangeB[1]) / 2;

  return Math.sqrt((midB - midA) * (midB - midA)) < (distA + distB);
}

function intersectingRange(rangeA, rangeB) {
  if (collisionDetected(rangeA, rangeB)) {
    return [Math.max(rangeA[0], rangeB[0]), Math.min(rangeA[1], rangeB[1])];
  }

  return null;
}

function drawText(ctx, text, x, y) {
  ctx.save();
  ctx.font = '18px Arial';
  ctx.fillText(text, x, y);
  ctx.restore();
}

function drawLines(ctx, lines, topOffset) {
  topOffset = topOffset || 0;
  var sizeWidth = ctx.canvas.clientWidth;
  var sizeHeight = ctx.canvas.clientHeight - topOffset;
  var yOffset = sizeHeight / (lines.length + 1);

  for (var i = 0; i < lines.length; i++) {
    var color = palette[i % palette.length];
    var yPos = (i + 1) * yOffset + topOffset;
    drawLine(ctx, lines[i], yPos, color)
  }
}

function drawLine(ctx, range, index, color) {
  ctx.save();
  ctx.beginPath();
  ctx.moveTo(range[0], index);
  ctx.lineTo(range[1], index);
  ctx.strokeStyle = color;
  ctx.lineWidth = 4;
  ctx.stroke();
  ctx.restore();
}

function drawBoundry(ctx, bounds, topOffset) {
  var sizeHeight = ctx.canvas.clientHeight - topOffset;
  var padding = sizeHeight * 0.25;
  var y1 = topOffset + padding;
  var y2 = sizeHeight + topOffset - padding;
  ctx.save();
  ctx.beginPath();
  ctx.strokeStyle = palette[4];
  ctx.setLineDash([5, 5]);
  ctx.lineWidth = 2;
  ctx.rect(bounds[0], y1, bounds[1] - bounds[0], sizeHeight * 0.5);
  ctx.stroke();
  ctx.restore();
}
canvas#draw {
  background: #FFFFFF;
  border: thin solid #7F7F7F;
}
<canvas id="draw" width="180" height="160"></canvas>
Mr. Polywhirl
  • 42,981
  • 12
  • 84
  • 132
2

Let's make the ranges clearer:

(start1, end1) and (start2, end2)

Double totalRange = Math.max(end1, end2) - Math.min(start1, start2);
Double sumOfRanges = (end1 - start1) + (end2 - start2);
Double overlappingInterval = 0D;

if (sumOfRanges > totalRange) { // means they overlap
   overlappingInterval = Math.min(end1, end2) - Math.max(start1, start2);
}

return overlappingInterval;

Based on this answer

Community
  • 1
  • 1
Daniel
  • 6,194
  • 7
  • 33
  • 59
  • This is over complicated and it would miss edge case when 2 sets have 1 common member (consider 2 ranges 1..2 and 2..3, they both have length=1, so totalRange == 2, sumOfRanges == 2, thus your "if" would miss the overlapping value "2". It would work if you change ">" to ">=". But the whole thing can be simplified: leave only 1 line, where you calculate overlappingInterval and then add only +1 line with "if (overlappingInterval>=0) then there is overlap; else there is no overlapping. – Dmitry Shevkoplyas Jan 06 '23 at 04:39
1

Set x=max(a,b), y=min(c,d). If x < y (or x≤y) then (x-y) is a common part of the two ranges (degenerate in case x=y), otherwise they don't overlap.

CiaPan
  • 9,381
  • 2
  • 21
  • 35
0

Based on some other answers to this question I composed the following two code samples:

The first will only return a Boolean indicating whether two ranges overlap:

//  If just a boolean is needed
    public static boolean overlap(int[] arr1, int[] arr2) {
      if((arr1[0] <= arr2[arr2.length - 1]) && (arr2[arr1.length - 1] >= arr2[0])) {
        return true;
      } else {
        return false;
      }
    }

The second will return an Integer array of the overlapping values in cases where an overlap exists. Otherwise it will return an empty array.

//  To get overlapping values
public static int[] overlap(int[] arr1, int[] arr2) {
  int[] overlappingValues = {};
  if((arr1[0] <= arr2[arr2.length - 1]) && (arr2[arr1.length - 1] >= arr2[0])) {
    int z = 0;
    for(int a : arr1) {
      for(int b : arr2) {
        if(a == b) {
          overlappingValues[z] = a;
          z = z + 1;
        }
      }
    }
  } else {
    return {};
  }
}

Hope this helps.

Marco N.
  • 185
  • 2
  • 8
  • `arr2[arr2.length]` - that would be an out-of-bounds array index, right there. – davmac Mar 16 '16 at 13:08
  • Also your "overlap" method seems to be treating the input arrays as if they are _sets_ containing discrete values. It's finding the _union_ of two sets, not the _overlap_ of two ranges. – davmac Mar 16 '16 at 13:10
  • Thanks for the remark with the length. Just forgot that -1 there. :/ Well it cannot be the union, can it? That would mean that if we have arrays [1,2,3], [2,3,4] we would get the return [1,2,3,4]. But what the method should return is [2,3] as only these values will be equal. I guess what you mean is the intersection. And yes, but it has never been specified how the ranges are represented. So I just assumed that they would be given in array representation. But if they are continous you are right that my solution will not find an answer. – Marco N. Mar 16 '16 at 13:17
  • yes, intersection, sorry. I think the question makes it clear that the ranges are represented as two endpoints. – davmac Mar 16 '16 at 13:28
  • Yes, right know I also get that point. I also used this feedback to adjust my second answer to this question to not only consider the discrete (unlikely) case but also the (more likely) continuous case. But thanks for the feedback. Always good to learn and to be reminded to read more thoroughfully first. – Marco N. Mar 16 '16 at 13:35
0

Based on the updated question I did some research via Google and could find this posting:

Java, find intersection of two arrays

To what I understand at the moment it should match the given requirements. And the code snippet used is quite short and from what I know also looks quite well.

And to account for the remarks in terms of discrete and continuous values I wanted to add another potential solution I could find for continuous ranges:

https://community.oracle.com/thread/2088552?start=0&tstart=0

This solution does not directly return the overlapped ranges but provides an interesting class implementation to do range comparison.

Community
  • 1
  • 1
Marco N.
  • 185
  • 2
  • 8