algorithm - JavaScript Merge Intersecting Rectangles - Stack Overflow

admin管理员组

文章数量:1278858

I need a way to merge an array of rectangle objects (objects with x,y,w,h properties) only if they intersect. So for example:

merge([{x:0, y:0, w:5, h:5}, {x:1, y:1, w:5, h:5}])

would return: [{x:0, y:0, w:6, h:6}]

---

merge([{x:0, y:0, w:1, h:1}, {x:5, y:5, w:1, h:1}])

would return: [{x:0, y:0, w:1, h:1}, {x:5, y:5, w:1, h:1}]

---

merge([{x:0, y:0, w:5, h:5}, {x:1, y:1, w:5, h:5}, {x:15, y:15, w:1, h:1}])

would return: [{x:0, y:0, w:6, h:6}, {x:15, y:15, w:1, h:1}]

---

If two rectangles intersect, a minimum bounding rectangle should be replace the two rectangles. The list will need to be checked again after merging in case the new MBR causes intersection with other rectangles. For the life of me I can't figure it out.

I need a way to merge an array of rectangle objects (objects with x,y,w,h properties) only if they intersect. So for example:

merge([{x:0, y:0, w:5, h:5}, {x:1, y:1, w:5, h:5}])

would return: [{x:0, y:0, w:6, h:6}]

---

merge([{x:0, y:0, w:1, h:1}, {x:5, y:5, w:1, h:1}])

would return: [{x:0, y:0, w:1, h:1}, {x:5, y:5, w:1, h:1}]

---

merge([{x:0, y:0, w:5, h:5}, {x:1, y:1, w:5, h:5}, {x:15, y:15, w:1, h:1}])

would return: [{x:0, y:0, w:6, h:6}, {x:15, y:15, w:1, h:1}]

---

If two rectangles intersect, a minimum bounding rectangle should be replace the two rectangles. The list will need to be checked again after merging in case the new MBR causes intersection with other rectangles. For the life of me I can't figure it out.

• javascript
• algorithm
• merge
• intersection

Share Improve this question Follow edited Mar 2, 2011 at 7:23 Louis asked Mar 2, 2011 at 7:02 LouisLouis 4,21055 gold badges4747 silver badges6262 bronze badges 5

• This is not at all clear. You're passing it the same rectangle. What happens if you pass two different rectangles that intersect? e.g. {x:0, y:0, w:2, h:2}, {x:1, y:1, w:2, h:2} Do you want the smallest enclosing rectangle, the largest rectangle contained in the intersection, the first rectangle, the second rectangle? – aaronasterling Commented Mar 2, 2011 at 7:07
• in this example, both objects are identical, hence there is actually no need to merge anything. What is your requirement? Should object b overwrite attributes in object a? vice versa? Or should it be more a binary AND, OR, XOR ? – jAndy Commented Mar 2, 2011 at 7:09
• I'm an idiot. Updated. It should merge it by creating a minimum bounding rectangle. – Louis Commented Mar 2, 2011 at 7:12
• Ok, much better but still some problems. You're taking the smallest enclosing rectangle. Doing this sequentially could create intersections where there were none before. What do you want to happen then? Something like {x:0, y:0, w:10, h:10}, {x:9, y:9, w: 11, h:11}, {x:11, y:0, h:2, w:20}. Should the last one be regarded as intersecting the first two? It doesn't to begin with but after you merge them into the enclosing rectangle, it intersects that. – aaronasterling Commented Mar 2, 2011 at 7:16
• Ok will clear that up. It will need to parse the list again to see if there are any new intersections created and therefore merge those. – Louis Commented Mar 2, 2011 at 7:22

Add a ment  | 

3 Answers 3

Sorted by: Reset to default 7

I'm not sure if this will work but off the top of my head something like...

function mergeAll(array) {
  do {
     var newArr = [], didMerge = false, i = 0;

     while (i < array.length) {
        if (intersects(array[i], array[i+1]) {
          newArr.push(merge(array[i], array[i+1]));
          i++;
          didMerge = true;
        }
        i++;
     }
     array = newArr;
  } while (didMerge);
  return array;
}

function intersects(r1, r2) {
    return !( r2.x > r1.x+r1.w
           || r2.x+r2.w < r1.x
           || r2.y > r1.y+r1.h
           || r2.y+r2.h < r1.y
           );
}

function merge(r1, r2) {
   return { x: Math.min(r1.x, r2.x),
            y: Math.min(r1.y, r2.y),
            w: Math.max(r1.w, r2.w),
            h: Math.max(r1.h, r2.h)
          }
}

This can be solved by modelling the problem as a graph. The nodes are the rectangles, and whenever there is an intersection between any two of them, we consider that those two nodes are connected by an edge.

Our target is to divide the set of rectangles into groups that are connected, either directly or indirectly, with each other. This is basically a connected ponent of the graph. This can be found out using a breadth first search or a depth first search.

After all ponents are found, we just need to find the highest top left corner and the lowest bottom right corner of all the rectangles in each to find their bounding box.

Checking for intersection can be done using the function provided in @Marcus' answer.

The overall plexity of this procedure is O(n^2), where n is the number of rectangles.

In case somebody needs fully working example here is repl to play https://repl.it/@anjmao/merge-rectangles and code:

function mergeAll(array) {
    let newArr, didMerge, i;
    do {
        newArr = [];
        didMerge = false;
        i = 0;
        while (i < array.length) {
            const curr = array[i];
            const next = array[i + 1];
            if (intersects(curr, next)) {
                newArr.push(merge(curr, next));
                i++;
                didMerge = true;
            } else {
                newArr.push(curr);
            }
            i++;
        }
        if (newArr.length > 0) {
          array = newArr; 
        }
    } while (didMerge);
    return array;
}

function sort(array) {
    array.sort((r1, r2) => {
        if (r1.x === r2.x) {
            return r1.y - r2.y;
        }
        return r1.x - r2.x;
    });
}

function intersects(r1, r2) {
    if (!r2) {
        return false;
    }
    return !(r2.x > r1.x + r1.w
        || r2.x + r2.w < r1.x
        || r2.y > r1.y + r1.h
        || r2.y + r2.h < r1.y
    );
}

function merge(r1, r2) {
    const w = r1.w > r2.w ? r1.w : r2.w + (r2.x - r1.x);
    const h = r1.h > r2.h ? r1.h : r2.h + (r2.y - r1.y);
    return {
        x: Math.min(r1.x, r2.x),
        y: Math.min(r1.y, r2.y),
        w: w,
        h: h
    }
}

mergeAll([{x:0, y:0, w:5, h:5}, {x:1, y:1, w:5, h:5}, {x:15, y:15, w:1, h:1}])

本文标签： algorithmJavaScript Merge Intersecting RectanglesStack Overflow