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:

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/

Answer 1

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;     
}

Answer 2

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.)