3

我有一组 m 个非旋转、整数（像素）对齐的矩形，每个矩形可能重叠也可能不重叠。矩形覆盖数千个像素。我需要找到覆盖 m 个矩形中的 n 个覆盖的所有区域的最小尺寸边界框。

一种（肮脏的）方法是绘制一个覆盖所有目标区域的画布。这是 O(mk)，其中 m 是矩形的数量，k 是每个矩形的像素数。然而，由于 k 比 m 大得多，我认为那里有更好的解决方案。

这感觉像是一个动态编程问题......但我无法弄清楚递归。

更好但仍然不是很好的解决方案：

将所有矩形的起点和终点在X方向排序O(mlogm)，迭代并找到可能有n个矩形以上的x位置，O(m)循环。对于可能有超过 n 个矩形的每个 x 位置，取该位置的矩形并对该位置的开始和停止进行排序 (O(mlogm))。找到重叠区域，以这种方式跟踪边界。总体而言，O(m^2logm)。

4

4 回答 4

1

你好疯狂科学梦想，

只是为了澄清一下，边界框也是不旋转的，对吗？

如果是这种情况，那么只需跟踪四个变量： ——代表minX, maxX, minY, maxY最左边、最右边、最顶部和最底部的像素——定义边界框，循环遍历每个矩形，更新四个变量，并在给定这四个变量的情况下定义新的边界框。

编辑

看起来您是在询问查找某些矩形子集的边界，而不是整个集合。

所以你有 M 个矩形，你从中选择 N 个矩形，然后找到其中的边界。

即使在这种情况下，循环遍历 N 个矩形并跟踪它们的边界也最多为 O(m)，这一点也不错。

我觉得我一定是误解了你的问题，因为这个回答可能不是你想要的；您的问题实际上是想问如何预先计算边界，以便给定任何子集，知道恒定时间内的总边界吗？

于 2013-11-07T22:10:27.607 回答
0

我们如何从一个盒子开始，然后找到离它最近的最远角落的下一个盒子。现在我们有一个带有两个框的区域。递归地找到下一个区域，直到我们有 n 个框。

虽然我们需要从每个盒子开始，但我们只需要积极地在当前最小的区域上工作。效果是我们从最小的盒子簇开始并从那里扩展。

如果 n 比 0 更接近 m，我们可以反转搜索树，以便我们从全封闭框开始，切掉每个边界框以创建下一个搜索级别。假设我们只在最小的剩余区域上积极工作，效果是我们首先切掉最空的区域。

是不是太复杂了？抱歉，我不记得此搜索的名称。我不擅长数学，所以我会跳过 O 表示法。>_<

于 2014-04-25T11:02:41.097 回答
0

我提出以下算法：

prepareData();
if (findBorder('left')) {
     foreach (direction in ['top', 'right', 'bottom']) {
         findBorder(direction)
    }
} else noIntersectionExists

prepareData (O(mlogm))：排序
垂直边界和水平边界
将结果保存为：
- 指向矩形的两个数组（arrX 和 arrY）
- 将索引保存为矩形的属性（rectangle.leftIndex，rectangle.topIndex ， ETC。

findBorder(left): // 其他方向类似最好情况 O(n)，最坏情况 O(2m-n)

arrIntersections = new Array;
//an intersection has a depth (number of rectangles intersected), a top and bottom border and list of rectangles
for(i=0; i < 2*m-n-1; i++){ // or (i = 2*m-1; i > n; i--)
    if(isLeftBorder(arrX[i])){
        addToIntersections(arrX[i].rectangle, direction);
        if(max(intersections.depth) = n) break;
    } else {
        removeFromIntersections(arrX[i].rectangle, direction);
    }
}

addToIntersections(rectangle, direction): // 解释 direction=left
最好的情况：O(n)，最坏的情况：O(m)

hasIntersected = false;
foreach(intersection in intersection){
    if(intersect(intersection, rectangle)){
        hasIntersected = true
        intersections[] = {
            depth: intersection.depth,
            bottom: min(intersection.bottom, rectangle.bottom),
            top: max(...)}
        intersection.depth++
        intersection.bottom = max(intersection.bottom, rectangle.bottom)
        intersection.top = max(...)
    }
}
if(!hasIntersected)
    intersections[]={depth:1, bottom:rectangle.bottom, top:rectangle.top}

这给出了 O(n^2) 和 O(m*(mn/2)) 之间的总体顺序

我希望我的伪代码足够清晰

于 2014-04-25T12:44:15.673 回答
0

这是否定义了您的问题？对于边界框=>#rect_label >= n 边界框

于 2014-04-25T06:16:30.140 回答