JavaScript объединить пересекающиеся прямоугольники

Question

Мне нужен способ объединения массива прямоугольных объектов (объектов со свойствами x,y,w,h), только если они пересекаются. Так, например:

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

вернется: [{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}])

вернется: [{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}])

вернется: [{x:0, y:0, w:6, h:6}, {x:15, y:15, w:1, h:1}]

---

Если два прямоугольника пересекаются, минимальный ограничивающий прямоугольник должен заменить два прямоугольника. Список должен быть проверен снова после объединения в случае, если новая MBR вызывает пересечение с другими прямоугольниками. Что касается моей жизни, я не могу понять это.

Answer 1

Я не уверен, что это сработает, но с моей головы что-то вроде ...

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

Answer 2

Это можно решить, смоделировав задачу в виде графика. Узлы являются прямоугольниками, и всякий раз, когда между двумя любыми из них есть пересечение, мы считаем, что эти два узла соединены ребром.

Наша цель - разделить набор прямоугольников на группы, которые прямо или косвенно связаны друг с другом. Это в основном связанный компонент графика. Это можно выяснить, используя поиск в ширину или поиск в глубину .

После того, как все компоненты найдены, нам просто нужно найти верхний левый верхний угол и нижний правый нижний угол всех прямоугольников в каждом, чтобы найти их ограничивающую рамку.

Проверка пересечения может быть выполнена с помощью функции, представленной в ответе @Marcus.

Общая сложность этой процедуры - O (n ^ 2), где n - количество прямоугольников.

Answer 3

В случае, если кому-то нужен полностью рабочий пример, используйте repl для воспроизведения https://repl.it/@anjmao/merge-rectangles и код:

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}])