多个重叠矩形的边界框

Question

如何获取多个重叠矩形的边界框？如果存在不重叠的矩形，则可能存在多个边界框。

我有一个包含 n 个代表矩形的对象的数组。每个对象都以下列方式表示一个矩形：{left: 178, top: 67, width: 20, height: 14} 它们也可以用其他方式表示，例如 leftX, topY, rightX, bottomY;它可以很容易地转换。

我不是在寻找非最大抑制算法。文献中是否有特定的算法可以实现这一点？我会在 JavaScript.

之后尝试转换它

编辑：只要矩形一个接一个重叠就可以工作；如果您按照下图所示的指定顺序绘制矩形，您将获得 3 个边界区域。

Edit2：也许一个有趣的案例如下：

矩形1和2重叠，它们的边界框与矩形3重叠；但是我对这种特殊情况不感兴趣，可以将 3 视为一个单独的矩形。

Answer 1

我不知道具体算法的名称，但这可以归结为二维碰撞检测：

function combineRects (rect1, rect2) {
  return a rectangle object representing the bounding box of the union of rect1 and rect2;
}
function doRectsCollide (rect1, rect2) {
  return true if rect1 and rect2 intersect;
}

const rectangles = [ your rectangle objects ];
const boundingBoxes = rectangles.reduce((boxes, rect) => {
  // Start with an empty array of bounding boxes.
  // For each rectangle, find the bounding box it intersects.
  const boundingBoxIndex = boxes.findIndex(doRectsCollide.bind(null, rect));
  if (boundingBoxIndex === -1) {
    // If there is none, push the rectangle into the bounding box array.
    boxes.push(rect);
    return boxes;
  } else {
    // Otherwise,
    // replace the intersected bounding box with a new box that includes the rectangle.
    boxes[boundingBoxIndex] = combineRects(boxes[boundingBoxIndex], rect);
    return boxes;
  }
}, []);

这在您的示例中非常有效（每个矩形与最多 3 个其他矩形进行比较），但在最坏的情况下会减慢到 O(n^2)，没有重叠的矩形。它可以通过使用比原始数组更好的东西来存储边界框来改进。

Answer 2

所以我提出了一种方法，应该适合您。方法总结如下

从一个空的碰撞数组开始
碰撞数组中的每个元素将存储与任何矩形发生碰撞的矩形数组
运行通过矩形列表我们有
如果矩形不与任何元素发生碰撞，则将其追加到碰撞中
如果矩形恰好与一个元素发生碰撞，则将其附加到碰撞数组的该元素中
如果矩形与数组中的多个元素发生冲突，那么我们将所有此类元素合并为一个，然后删除其余元素
最后碰撞数组只有碰撞数组的元素
然后您可以为这些碰撞中的每一个计算边界矩形，这只是一个 min/max 问题

现在进入代码

function doRectsCollide(a, b) {
    return !(
        ((a.top + a.height) < (b.top)) ||
        (a.top > (b.top + b.height)) ||
        ((a.left + a.width) < b.left) ||
        (a.left > (b.left + b.width))
    );
}

var collisions = [];

var rectangles = [
    {left: 74, top: 66.89999389648438, width: 80.5, height: 71},
    {left: 111.5, top: 95.89999389648438, width: 125, height: 84},
    {left: 177, top: 120.89999389648438, width: 168.5, height: 90},
    {left: 93, top: 258.8999938964844, width: 81.5, height: 81},
    {left: 265.5, top: 320.8999938964844, width: 92, height: 83},
    {left: 393, top: 210.89999389648438, width: 88.5, height: 95}
];

for (rectangle of rectangles) {
    var collisions_indexes = [];

    index = 0;
    for (currentColission of collisions) {
        for (rect of currentColission) {
            if (doRectsCollide(rect, rectangle) === true) {
                collisions_indexes.push(index)
                break
            }
        }
        index++;
    }

    if (collisions_indexes.length == 0) {
        // this rectangle collides with none and should be appened to collisions array
        collisions.push([rectangle])
    } else if (collisions_indexes.length >= 1) {
        // there is just one collision, we can merge the same
        collisions[collisions_indexes[0]].push(rectangle)

        // now we have got multiple collisions, so we need to merge all the collisions with the first one
        // and remove the colission ones
        for (var i = 1; i < collisions_indexes.length; i++) {
            // we use - (i - 1) because we will remove the collision once we merge it
            // so after each merge the collision index actually shift by -1

            var new_index = collisions_indexes[i] - (i - 1);
            // extend the first colliding array with the new collision match
            collisions[collisions_indexes[0]].push(...collisions[new_index])

            // now we remove the element from our collision since it is merged with some other
            collisions.splice(new_index, 1);
        }

    }
}

console.log(JSON.stringify(collisions, null, 2));
//now we have a array of collision which will have all colliding ones
for (collision of collisions) {
    // compute bounding rectangle from rectangles array in collision
}

现在相同的输出是

[
    [
        {"left":74,"top":66.89999389648438,"width":80.5,"height":71},
        {"left":111.5,"top":95.89999389648438,"width":125,"height":84},
        {"left":177,"top":120.89999389648438,"width":168.5,"height":90}
    ],
    [{"left":93,"top":258.8999938964844,"width":81.5,"height":81}],
    [{"left":265.5,"top":320.8999938964844,"width":92,"height":83}],
    [{"left":393,"top":210.89999389648438,"width":88.5,"height":95}]
]

多个重叠矩形的边界框

Bounding box of multiple overlapping rectangles

javascript

rectangles

bounding-box