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 val…

Accepted Answer

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

How to approach recursive function for overlapping rectangles

Solution

Problem

Related problems