javascript - 如何处理重叠矩形的递归函数

Question

我有一个名为 myRects 的矩形数组，如下所示:

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

这是它们的绘制方式:

我还有一个方便的函数，叫做 doRectanglesIntersect(r1, r2):

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

我想要的是一个名为 recursivelyGetIntersectingRects(rect) 的函数，它将返回一个矩形数组，这些矩形与给定矩形或其相交的矩形无限相交。

因此，如果我将 r1 传递给此函数，我应该将 [r2,r3,r4,r5] 作为返回值，因为它们都已连接。我不介意此函数是否返回对象文字或键，但它应该尽可能高效并且不返回重复值。

我能够提出这个问题，但我想不出一个解决方案。我的头脑不会递归地工作。

这是我制作的 fiddle ，其中包含上面的代码和作为视觉辅助的 Canvas 绘图:http://jsfiddle.net/b3jX6/5/

Answer 1

我认为这样的事情可以做到:

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