Menu
Assume I have a pile of rectangles, some of which intersect, some isolate. E. g.
+--------------- + +-------- +
| | | |
| | | |
| A | | C |
| +---------------- + | |
| | | | +---------+-------- +
| | | | | |
+---------|----- + B | | D |
| | | |
| | +------------------ +
+---------------- +
+------------------ + +-------- +
| | | |
| E | | X |
+-------------------+ | |
| | +-------- +
| | +------------ +
| | | |
| F | | |
| | | Y |
| | | |
+-------------------+ +------------ +
Rect A, B intersect with each other, C, D have one same point, E, F have two same points, X, Y are isolated.
I have two questions:
+---------+----- + +-------- +
| | | | |
| | | | |
| | | | |
| | +--------- + | |
| | | | +---------+-------- +
| | | | | |
+---------+ | | | |
| | | | |
| | | +-------------------+
+------+----------+
+------------------ + +-------- +
| | | |
| | | |
| | | |
| | +---------+
| | +------------ +
| | | |
| | | |
| | | |
| | | |
+-------------------+ +-------------+
+---------------------------+ +-------------------+
| | | |
| | | |
| | | |
| | | |
| | | |
| | | |
| | | |
| | | |
| | +-------------------+
+---------------------------+
+-------------------+ +---------+
| | | |
| | | |
| | | |
| | +---------+
| | +------------ +
| | | |
| | | |
| | | |
| | | |
+-------------------+ +-------------+
For Q1, I've no idea at all.... For Q2, I wrote some code in C++ but have poor efficiency. I believe there're better methods/algorithm.
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;
}
}
519
We need to find the number of rectangles which are not squares, for that we will subtract the number of squares from the number of rectangles to get the required number of rectangles. is the number of columns. Number of squares in a grid =m×n+(m−1)(n−1)+(m−2)(n−2)+(m−3)(n−3.
Number of rectangles are =m(m+1)n(n+1)/4=2×4×3×5/4=30.
If the grid is 1×1, there is 1 rectangle. If it grid is 3×1, there will be 3 + 2 + 1 = 6 rectangles. If we add one more column to N×1, firstly we will have as many rectangles in the 2nd column as the first, and then we have that same number of 2×M rectangles.
First, I'm assuming that your rectangles are all axis-aligned.
For Q1, one option would be to sweep the plane while maintaining a list of line segments along the sweep line that lie in the interior of the rectangles. As you discover each rectangle vertex during the sweep you can check to see if it modifies the current interior segments and if so, start or end a rectangle as necessary.
For example, let's say your sweep line moves left to right:
Current
Interior
|
+-|------------- + +-------- + *
| | | | | |
| | | | | |
| | A | | C | |
| | +---------------- + | | |
| | | | | +---------+-------- + |
| | | | | | | |
+-|-------|----- + B | | D | *
| | | | |
| | | +------------------ +
| +---------------- +
|
+-|---------------- + +-------- + *
| | | | | |
| | E | | X | |
| |-----------------+ | | |
| | | +-------- + |
| | | +------------ + |
| | | | | |
| | F | | | |
| | | | Y | |
| | | | | |
+-|-----------------+ +------------ + *
|
When the sweep line is in the position shown above, there are two interior segments. Namely, that inside A and that inside (E U F). When the sweep line reaches the leftmost edge of B, we output a rectangle for the portion of A lying to the left. We then replace the interior of A in the segment list with the interior of (A U B).
Current
Interior
|
+---------+-|--- + +-------- + *
| | | | | | |
| | | | | | |
| | | | | C | |
| | |-------------- + | | |
| | | | | +---------+-------- + |
| | | | | | | |
+---------+ |--- + B | | D | |
| | | | | |
| | | +------------------ + |
+-|-------------- + *
|
+-----------|------ + +-------- + *
| | | | | |
| | | | X | |
| |-------+ | | |
| | | +-------- + |
| | | +------------ + |
| | | | | |
| | | | | |
| | | | Y | |
| | | | | |
+-----------|-------+ +------------ + *
|
For Q2, the answer could be computed during the same sweep by keeping track of the x-coordinate at which a segment was first added to the list (e.g. "left side of A") as well as the min and max y-coordinates that it spans during its lifetime (e.g. bottom of B to top of A). When the segment is finally removed from the list (e.g. "right side of B"), then output a rectangle using these four coordinates.
Sorting the rectangle vertices lexicographically in a preprocessing step would be O(n * log n). Processing them would be O(log n) since you can do a binary search on the known interior ranges. The total runtime should be O(n * log n).
62
Q1: this is called partition of rectilinear polygon. Answer from Rob's comment has very good description. I found paper mentioned in the answer useful.
Q2: I suppose that you don't want two covers of non-intersecting regions to intersect. Like cover for 3 rectangle, 2 rectangle producing L and rectangle intersection cover of L but not any L rectangle.
If it is like that, than it is possible to incrementally create covers. Here is a simple algorithm for it.
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
This code is not efficient in standard form. With good structure for covers structure, it can be efficient.
31
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
