假设我有一堆矩形,其中一些是相交的,有些是孤立的. E. g.
+--------------- + +-------- +
| | | |
| | | |
| A | | C |
| +---------------- + | |
| | | | +---------+-------- +
| | | | | |
+---------|----- + B | | D |
| | | |
| | +------------------ +
+---------------- +
+------------------ + +-------- +
| | | |
| E | | X |
+-------------------+ | |
| | +-------- +
| | +------------ +
| | | |
| F | | |
| | | Y |
| | | |
+-------------------+ +------------ +
矩形A,B相互交叉,C,D有一个相同的点,E,F有两个相同的点,X,Y是孤立的.
我有两个问题：
>如何将这些矩形分成矩形,覆盖A,B,D,F,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
