7

假设我有一堆矩形，其中一些相交，一些孤立。例如。

    +--------------- + +-------- +
    | | | |
    | | | |
    | 一个 | | C |
    | +---------------- + | |
    | | | | +---------+-------- +
    | | | | | |
    +---------|----- + B | | D |
              | | | |
              | | +------------------ +
              +---------------- +

    +-------- + +-------- +
    | | | |
    | E | | X |
    +-------------------+ | |
    | | +-------- +
    | | +------------ +
    | | | |
    | F | | |
    | | | 是 |
    | | | |
    +--------------------+ +------------ +

矩形 A、B 相交，C、D 有一个相同点，E、F 有两个相同点，X、Y 是孤立的。

我有两个问题：

  1. 如何将这些矩形划分为覆盖 A、B、C、D、E、F、X、Y 的矩形也具有这样的最小计数：
    +---------+----- + +-------- +
    | | | | |
    | | | | |
    | | | | |
    | | +--------- + | |
    | | | | +---------+-------- +
    | | | | | |
    +---------+ | | | |
              | | | | |
              | | | +-------------------+
              +--------+----------+

    +-------- + +-------- +
    | | | |
    | | | |
    | | | |
    | | +----------+
    | | +------------ +
    | | | |
    | | | |
    | | | |
    | | | |
    +--------------------+ +-------------+
  1. 如何用大矩形覆盖相交的矩形？像这样：
    +---------------------------+ +------------------------+
    | | | |
    | | | |
    | | | |
    | | | |
    | | | |
    | | | |
    | | | |
    | | | |
    | | +-------------------+
    +---------------+


    +--------------------+ +---------+
    | | | |
    | | | |
    | | | |
    | | +----------+
    | | +------------ +
    | | | |
    | | | |
    | | | |
    | | | |
    +--------------------+ +-------------+

对于第一季度，我完全不知道......对于第二季度，我用 C++ 编写了一些代码，但效率很差。我相信有更好的方法/算法。

 bool intersectRect(const Rect& rect1, const Rect& rect2) {
    /* if rect1 and rect2 intersect return true
       else return false
    */
}
Rect mergeIntersectRects(const set<Rect>& rects) {
    // suppose rects are all intersected. This function only return a smallest Rect that cover all rects.
}
set<Rect> mergeRectToRects(const set<Rect>& rectset, const Rect& rect) {
    set<Rect> _intersect_rects;
    set<Rect> _unintersect_rects;
    for(set<Rect>::const_iterator it = rectset.begin();
        it != rectset.end();
        ++it) {
        if(intersectRect(*it, rect))
            _intersect_rects.insert(*it);
        else 
            _unintersect_rects.insert(*it);
    }
    if(!_intersect_rects.empty()) {
        _intersect_rects.insert(rect);
        return mergeRectToRects(_unintersect_rects,
                                mergeIntersectRects(_intersect_rects));
    }
    else {
        _unintersect_rects.insert(rect);
        return _unintersect_rects;
    }
}
4

4 回答 4

3

首先，我假设您的矩形都是轴对齐的。

对于 Q1，一种选择是扫描平面，同时保持沿扫描线位于矩形内部的线段列表。当您在扫描期间发现每个矩形顶点时，您可以检查它是否修改了当前的内部段，如果是，则根据需要开始或结束一个矩形。

例如，假设您的扫描线从左向右移动：

                                                                     当前的
                                                                     内部的
      |                                                                  
    +-|------------- + +-------- + *
    | | | | | |
    | | | | | |
    | | 一个 | | C | |
    | | +---------------- + | | |
    | | | | | +---------+-------- + |
    | | | | | | | |
    +-|-------|----- + B | | D | *
      | | | | |
      | | | +------------------ +
      | +---------------- +
      |
    +-|---------------- + +-------- + *
    | | | | | |
    | | E | | X | |
    | |-----------------+ | | |
    | | | +-------- + |
    | | | +------------ + |
    | | | | | |
    | | F | | | |
    | | | | 是 | |
    | | | | | |
    +-|-----------------+ +------------ + *
      |

当扫描线位于上图所示位置时，有两个内部段。即A里面那个和那个里面(EUF)。当扫描线到达 B 的最左边缘时，我们为 A 位于左侧的部分输出一个矩形。然后我们用（AUB）的内部替换段列表中A的内部。

                                                                     当前的
                                                                     内部的
                |                                                        
    +---------+-|--- + +-------- + *
    | | | | | | |
    | | | | | | |
    | | | | | C | |
    | | |-------------- + | | |
    | | | | | +---------+-------- + |
    | | | | | | | |
    +---------+ |--- + B | | D | |
              | | | | | |
              | | | +------------------ + |
              +-|-------------- + *
                |
    +-----------|------ + +-------- + *
    | | | | | |
    | | | | X | |
    | |-------+ | | |
    | | | +-------- + |
    | | | +------------ + |
    | | | | | |
    | | | | | |
    | | | | 是 | |
    | | | | | |
    +-----------|--------+ +------------ + *
                |

对于 Q2，可以通过跟踪第一次将片段添加到列表的 x 坐标（例如“A 的左侧”）以及最小和最大 y 坐标，在同一扫描期间计算答案它在其生命周期内跨越（例如 B 的底部到 A 的顶部）。当段最终从列表中移除时（例如“B 的右侧”），然后使用这四个坐标输出一个矩形。

在预处理步骤中按字典顺序对矩形顶点进行排序将是 O(n * log n)。处理它们将是 O(log n)，因为您可以对已知的内部范围进行二进制搜索。总运行时间应该是 O(n * log n)。

于 2012-07-26T12:34:45.607 回答
1

Q1：这称为直线多边形的划分。Rob评论的回答有很好的描述。我发现答案中提到的论文很有用。

Q2：我想你不希望两个不相交区域的覆盖相交。就像 3 个矩形的覆盖，2 个矩形产生 L 和 L 的矩形交叉覆盖，但不是任何 L 矩形。

如果是这样，则可以逐步创建封面。这是一个简单的算法。

covers = {A}
for each rectangle R
  while there is a cover that intersects R, say C
    remove C from covers and set R = cover of R and C
  add R to covers

此代码在标准形式下效率不高。结构良好的covers结构，它可以是高效的。

于 2012-07-26T15:05:35.990 回答
0

我会使用@Damon 建议的方法，但会使用一些空间索引结构（例如四叉树或网格）加速相邻矩形搜索。您需要其中两个，首先构建在输入矩形集上，以搜索要拆分的相交矩形，第二个构建在第一步获得的拆分矩形集上，以搜索要合并的相邻矩形。与天真的方法相比，这应该会大大加快速度。

于 2012-07-26T11:58:04.490 回答
0

这是算法：http: //goo.gl/aWDJo

您可以阅读有关查找凸包算法的信息：http ://ralph.cs.cf.ac.uk/papers/Geometry/boxing.pdf

于 2012-07-26T14:10:34.667 回答