Checking for range overlap

Question

I am trying to implement a function which, when given two objects that represent lines, returns whether they overlap or not.

Here is how it should look like visually.

Example 1:

checkOverlap({start: 0, end: 10}, {start: 8, end: 15})

Which visually, would be:

0--------10
     8-------15
       ^ overlap

returns true.

Example 2:

checkOverlap({start: 12, end: 15}, {start: 0, end: 10})

Which visually, would be:

             12-------15   
0--------10

              no overlap

returns false.

Here is my function which works for some but not all:

function checkOverlap(lineA, lineB) {
    var result;
    for(var a in lineA) {
        for(var b in lineB) {
            if(a.end > b.start) {
                result = true;
            } else {
                result = true;
            }
        }
    }
    return result;
}

*"which works for some but not all"* For what input doesn't it work? From what I can tell is that it shouldn't work at all. Do a `console.log(a, b)` and see what the values of `a` and `b` actually are. Also, why are you assigning the same value to `result` in the `if` and `else` block? That means `result` will *always* be `true`. What do you think `for (var a in lineA)` does exactly? Why are you using a loop? — Felix Kling, Nov 12 '16 at 21:19
yea sorry it doesnt work, it was just outputing true and the rest of the code was not working — afkvision, Nov 12 '16 at 21:22
It was answered already: https://stackoverflow.com/questions/3269434/whats-the-most-efficient-way-to-test-two-integer-ranges-for-overlap/3269471 — Phil B, Nov 21 '18 at 16:19

pato · Accepted Answer · 2016-11-12T21:50:31.010

3

Nina Scholz answer won't work, eg. a = {start: 1, end: 2}, b = {start: 0, end: 10}.

If lines {start: 0, end: 10} and {start: 10, end: 15} are count as overlapping:

 function checkOverlap(lineA, lineB) {
        return lineA.start >= lineB.start && lineA.start <= lineB.end || 
               lineA.end >= lineB.start && lineA.end <= lineB.end ||
               lineB.start >= lineA.start && lineB.start <= lineA.end || 
               lineB.end >= lineA.start && lineB.end <= lineA.end;
    }

If not:

 function checkOverlap(lineA, lineB) {
        return lineA.start > lineB.start && lineA.start < lineB.end || 
               lineA.end > lineB.start && lineA.end < lineB.end ||
               lineB.start > lineA.start && lineB.start < lineA.end || 
               lineB.end > lineA.start && lineB.end < lineA.end;
    }

edited Nov 12 '16 at 21:50

answered Nov 12 '16 at 21:35

pato

868
5
10

this wont work on this var lineA = {start: 0, end: 10}; var lineB = {start: 10, end: 20}; – afkvision Nov 12 '16 at 21:43
In your case should it be count as overlapping or not? If not remove = sign in all cases – pato Nov 12 '16 at 21:48
not in all cases, some should equal true and some false – afkvision Nov 12 '16 at 21:49
Could you specify? I mean those cases when they only 'touch' – pato Nov 12 '16 at 21:51

score 3 · Answer 2 · 2016-11-16T18:50:01.940

The overlap must follow two conditions:

o1.end - o2.start > 0 // >= 0 if 0-10 10-20 means overlapping
o2.end - o1.start > 0 // >= 0 if 10-20 0-10 means overlapping

function checkOverlap(o1, o2) {
  return ((o1.end - o2.start) > 0 && (o2.end - o1.start) > 0) ? true : false;
}

console.log(checkOverlap({start: -10, end: 0}, {start: 0, end: 10}));   // false
console.log(checkOverlap({start: -20, end: -10}, {start: -5, end: 5})); // false
console.log(checkOverlap({start: 5, end: 10}, {start: 10, end: 20}));   // false
console.log(checkOverlap({start: -10, end: 0}, {start: -5, end: 5}));   // true
console.log(checkOverlap({start: -5, end: 5}, {start: -10, end: 0}));   // true
console.log(checkOverlap({start: 0, end: 10}, {start: 5, end: 15}));    // true
console.log(checkOverlap({start: 5, end: 15}, {start: 0, end: 10}));    // true

.as-console-wrapper { max-height: 100% !important; top: 0; }

Hard to see the graphic on the black background. – kojow7 Nov 19 '20 at 22:03 — kojow7, Nov 19 '20 at 22:03
Just click on the graphic or open it in a new tab. – Nov 21 '20 at 12:25 — , Nov 21 '20 at 12:25

Nina Scholz · Answer 3 · 2016-11-12T21:51:27.603

You could check against the borders of an object.

function checkOverlap(o1, o2) {
    return (
       o1.start >= o2.start && o1.start <= o2.end ||
       o1.end >= o2.start && o1.end <= o2.end ||
       o2.start >= o1.start && o2.start <= o1.end ||
       o2.end >= o1.start && o2.end <= o1.end
    );
}

console.log(checkOverlap({start: 0, end: 10}, {start: 8, end: 15}));   // true
console.log(checkOverlap({start: 8, end: 15}, {start: 0, end: 10}));   // true
console.log(checkOverlap({start: 12, end: 15}, {start: 0, end: 10}));  // false
console.log(checkOverlap({start: 0, end: 10}, {start: 12, end: 15}));  // false
console.log(checkOverlap({start: 12, end: 15}, {start: 16, end: 17})); // false
console.log(checkOverlap({start: 16, end: 17}, {start: 12, end: 15})); // false
console.log(checkOverlap({start: 1, end: 2}, {start: 0, end: 10}));    // true
console.log(checkOverlap({start: 0, end: 10}, {start: 1, end: 2}));    // true

console.log(checkOverlap({start: 0, end: 10}, {start: 10, end: 20}));  // true
console.log(checkOverlap({start: 10, end: 20}, {start: 0, end: 10}));  // true

.as-console-wrapper { max-height: 100% !important; top: 0; }

it wont work on this var lineA = {start: 0, end: 10}; var lineB = {start: 10, end: 20}; or this var lineA = {start: 10, end: 20}; var lineB = {start: 0, end: 10}; — afkvision, Nov 12 '16 at 21:48

Checking for range overlap

3 Answers3

Linked