如何获得覆盖另一堆矩形的最小数量的矩形？
假设我有一堆长方形，其中一些相交，一些孤立。 例如，
+--------------- + +-------- +
| | | |
| | | |
| A | | C |
| +---------------- + | |
| | | | +---------+-------- +
| | | | | |
+---------|----- + B | | D |
| | | |
| | +------------------ +
+---------------- +
+------------------ + +-------- +
| | | |
| E | | X |
+-------------------+ | |
| | +-------- +
| | +------------ +
| | | |
| F | | |
| | | Y |
| | | |
+-------------------+ +------------ +
Rect A，B彼此相交，C，D有一个相同的点，E，F有两个相同的点，X，Y是孤立的。
我有两个问题：
+---------+----- + +-------- +
| | | | |
| | | | |
| | | | |
| | +--------- + | |
| | | | +---------+-------- +
| | | | | |
+---------+ | | | |
| | | | |
| | | +-------------------+
+------+----------+
+------------------ + +-------- +
| | | |
| | | |
| | | |
| | +---------+
| | +------------ +
| | | |
| | | |
| | | |
| | | |
+-------------------+ +-------------+
+---------------------------+ +-------------------+
| | | |
| | | |
| | | |
| | | |
| | | |
| | | |
| | | |
| | | |
| | +-------------------+
+---------------------------+
+-------------------+ +---------+
| | | |
| | | |
| | | |
| | +---------+
| | +------------ +
| | | |
| | | |
| | | |
| | | |
+-------------------+ +-------------+
对于Q1，我完全不知道......对于Q2，我用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;
}
}
算法如下：http：//goo.gl/aWDJo
你可以阅读关于寻找凸包算法：http://ralph.cs.cf.ac.uk/papers/Geometry/boxing.pdf
首先，我假设你的矩形都是轴对齐的。
对于第一季度，一种选择是扫描飞机，同时保持位于矩形内部的扫描线上的线段列表。 当您在扫描期间发现每个矩形顶点时，您可以检查它是否修改当前的内部分段，如果需要，可以根据需要开始或结束矩形。
例如，假设您的扫描线从左向右移动：
Current
Interior
|
+-|------------- + +-------- + *
| | | | | |
| | | | | |
| | A | | C | |
| | +---------------- + | | |
| | | | | +---------+-------- + |
| | | | | | | |
+-|-------|----- + B | | D | *
| | | | |
| | | +------------------ +
| +---------------- +
|
+-|---------------- + +-------- + *
| | | | | |
| | E | | X | |
| |-----------------+ | | |
| | | +-------- + |
| | | +------------ + |
| | | | | |
| | F | | | |
| | | | Y | |
| | | | | |
+-|-----------------+ +------------ + *
|
当扫掠线位于上图所示位置时，有两个内部分段。 也就是说，在A内部和EUF内部。 当扫掠线到达B的最左边时，我们为左边的A部分输出一个矩形。 然后我们用（AUB）的内部替换段列表中的A的内部。
Current
Interior
|
+---------+-|--- + +-------- + *
| | | | | | |
| | | | | | |
| | | | | C | |
| | |-------------- + | | |
| | | | | +---------+-------- + |
| | | | | | | |
+---------+ |--- + B | | D | |
| | | | | |
| | | +------------------ + |
+-|-------------- + *
|
+-----------|------ + +-------- + *
| | | | | |
| | | | X | |
| |-------+ | | |
| | | +-------- + |
| | | +------------ + |
| | | | | |
| | | | | |
| | | | Y | |
| | | | | |
+-----------|-------+ +------------ + *
|
对于第二季度，答案可以在同一次扫描期间通过跟踪首先添加到列表中的段的x坐标（例如“A的左侧”）以及最小和最大y坐标来计算它跨越其整个生命周期（例如B的底部到A的顶部）。 当段最后从列表中删除（例如“B的右侧”），然后使用这四个坐标输出一个矩形。
在预处理步骤中按字母顺序排列矩形顶点将为O（n * log n）。 处理它们将是O（log n），因为您可以在已知的内部范围上执行二分搜索。 总运行时间应该是O（n * log n）。
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结构结构，它可以是有效的。
上一篇: How to get minimum count rectangles that covers another pile of rectangle?