How to approach recursive function for overlapping rectangles

Question

I have an array of rectangles called myRects like so:

const 
    r1 = {x1: 10, x2: 80, y1: 10, y2: 80},
    r2 = {x1: 60, x2: 100, y1: 60, y2: 100},
    r3 = {x1: 90, x2: 180, y1: 90, y2: 140},
    r4 = {x1: 120, x2: 140, y1: 130, y2: 160},
    r5 = {x1: 160, x2: 210, y1: 80, y2: 110},
    myRects = {r1: r1, r2: r2, r3: r3, r4: r4, r5: r5};

Here's how they look drawn:

enter image description here

I also have a handy function called doRectanglesIntersect(r1, r2):

function doRectanglesIntersect(r1, r2) {
  return (r1.x1 <= r2.x2 &&
          r2.x1 <= r1.x2 &&
          r1.y1  <= r2.y2 &&
          r2.y1  <= r1.y2)
}

What I want is a function called recursivelyGetIntersectingRects(rect) which will return an array of rectangles which intersect the given rectangle or its intersected rectangles ad infinitum.

So if I pass r1 into this function I should get [r2,r3,r4,r5] as a return value as they're all connected. I don't mind if this function returns the object literals or the keys, but it should be as efficient as possible and not return duplicate values.

I am able to formulate this problem but a solution escapes me. My mind does not work recursively.

Here's a fiddle I've made which contains the code above and a canvas drawing as a visual aid: http://jsfiddle.net/b3jX6/5/

What are your attempts to solve this? Also, why do you want to solve this? Smells like homework to me. — Casey Falk, Jul 14 '14 at 16:43
Also: see this related post that uses c# (but the idea is the same). http://stackoverflow.com/questions/12260491/find-rectangles-recursively — Casey Falk, Jul 14 '14 at 16:45
It is not homework, I wish I was young enough to be still in school! I'm trying to make a canvas library more efficient by dirty rectangle checking. However with overlapping objects things get drawn out of order. Hence my need for a suitable algorithm for this. — Matt Harrison, Jul 14 '14 at 16:45
Fair enough! I had to ask. ;) If you are trying to make a JavaScript library "more efficient," I'd recommend you iterate rather than recurse. Iteration is faster in JS and you won't max out your recursion depth: http://stackoverflow.com/questions/9474465/is-iteration-faster-than-recursion-or-just-less-prone-to-stack-overflows . — Casey Falk, Jul 14 '14 at 16:48
I was aware I might be able to escape recursion. I will look into making this iterative instead. Thanks for the advice :) and no probs, it does look like homework! — Matt Harrison, Jul 14 '14 at 16:50
No problem. :) Check out this post for more... http://stackoverflow.com/questions/2752349/fast-rectangle-to-rectangle-intersection — Casey Falk, Jul 14 '14 at 16:52

score 4 · Accepted Answer · answered Jul 14 '14 at 17:10

I think something like this could do:

iterativelyGetIntersectingRects(r, rects) {
 var inter = [];  // resulting intersecting rects
 var found = [r]; // found intersecting rects in last round (to be checked for subseq intersections)
 while(found.length) {   // while new ones found
  var a = found.shift(); // check this
  inter.push(a);         // also store to results
  var remain = [];
  while(rects.length) {      // while remaining for check
   var test = rects.shift(); // check next
   if( doIntersect(a, test))
    found.push(test);        // gotcha!
   else
    remain.push(test);       // not yet
  }
  rects = remain;            // remaining for check with next found
 }
 return inter;     
}

Thank you, you really helped out. I added another answer with the finished function I've used but I'll mark this one as accepted. — Matt Harrison, Jul 14 '14 at 18:22

score 1 · Answer 2 · edited May 23 '17 at 12:11

1

Edit: abstracted from comments into a full answer.

Since you are trying to "make a canvas library more efficient," I would recommend you iterate rather than recurse; iteration is faster in JS and you won't have to worry about your recursion depth. More

The question then becomes, "How can I quickly check for rectangle intersection?" See this SO post for more, but the top-rated answer currently describes Daniel Vassalo's function below:

function intersectRect(r1, r2) {
  return !(r2.left > r1.right || 
           r2.right < r1.left || 
           r2.top > r1.bottom ||
           r2.bottom < r1.top);
}

... when given a rectangle of the form:

var sampleRectangle = {
  left:   10,
  top:    10,
  right:  30,
  bottom: 30
};

(For those seeking recursive rectangle overlap, see this related C# SO question.)

edited May 23 '17 at 12:11

Community

1
1

answered Jul 14 '14 at 17:01

Casey Falk

2,617
1
18
29

Would my function above `doRectanglesIntersect()` not be faster as it would return as soon as one of the comparisons fails whereas this would check all comparisons? – Matt Harrison Jul 14 '14 at 17:06
1

I believe AND (&&) and OR (||) statements both short-circuit; OR short-circuits on `true` statements while AND short-circuits on `false` statements. In that regard, the only difference is the negation. I would vote to use yours since avoiding negations generally helps clear up code. Source: http://stackoverflow.com/questions/5891754/javascript-conditional-order-evaluation – Casey Falk Jul 14 '14 at 17:13

score 0 · Answer 3 · answered Jul 14 '14 at 18:21

I settled on the following function which is heavily inspired by fast's answer.

I made a couple of modifications so the underlying collection was not modified, rather I cloned the array of rects.

function iterativelyGetIntersectingRects(r) {
    var intersectingRects = [],
        allRects = myRects.slice(0)
        foundStack = [r],
        foundRect, 
        i, 
        rectToTest, 
        remainingRectsToTest;

    while (foundStack.length > 0) {
        foundRect = foundStack.shift();
        intersectingRects.push(foundRect);
        remainingRectsToTest = [];
        for (i = 0; i < allRects.length; i++) {
            rectToTest = allRects[i];
            if (doRectanglesIntersect(foundRect, rectToTest)) {
                foundStack.push(rectToTest);
            } else {
                remainingRectsToTest.push(rectToTest)
            }
        }
        allRects = remainingRectsToTest;
    }

    intersectingRects.shift(); // This is our original rectangle

    return intersectingRects;
}

How to approach recursive function for overlapping rectangles

3 Answers3