長方形の山があり、そのうちのいくつかは交差し、いくつかは孤立しているとします。例）
+-------------------- + +-------- +
| | | | | | | |
| | | | | | | |
| | あ | | | シー |
| | +---------------- + | | |
| | | | | | | | +---------+-------- +
| | | | | | | | | | | |
+--------|----- + B | | | D |
| | | | | | | |
| | | | +------------------ +
+---------------- +
+-------------------- + +-------- +
| | | | | | | |
| | え | | | X |
+--------------------+ | | |
| | | | +-------- +
| | | | +------------ +
| | | | | | | |
| | ふ | | | | |
| | | | | | よ |
| | | | | | | |
+---------------------+ +------------ +
Rect A、B は互いに交差し、C、D は 1 つの同じ点を持ち、E、F は 2 つの同じ点を持ち、X、Y は孤立しています。
2 つの質問があります。
- これらの長方形を、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;
}
}