finding all possible rectangle placing possibilities

Question

Following Problem:

Let's say we have a rectangular map containing several rectangles. I want to find all possible "maximal" rectangles which can be placed on the map without intersecting any of the other rectangles. With maximal I mean rectangles which can't be enlarged in any direction.

Does someone know an algorithm to perform this task?

enter image description here

Answer 1

I'll suggest a solution that may not be the faster but should do the job.

The idea is to place each of your rectangles one by one. Everytime you add a rectangle in the map, check if it intersects any of the others. If it does, then just break these both rectangles into the correct corresponding new rectangles, depending on the shape of the intersection.

It's easy to see that if a new rectangle (green) covers the whole affected rectangle (red), only the new would be broke apart. Otherwise, both will.

Just by adding one by one and breaking them apart correctly, you will have your full set of rectangles in the end, which you just need to iterate to find your "maximal", if it means the ones with biggest area.

This algorithm should be something around O(n²) where n is the number of rectangles you add.

Answer 2

You can do this with simple interval algebra. For illustration, I'll put some numbers on the example you gave us. I'll use the Cartesian first quadrant, origin in the lower-left corner. The entire field is then (0, 0) to (30, 20); rectangles have corners at (10, 0) to (30, 8); (0, 12) to (13, 20); (20, 15) to (25, 17).

To solve this, group rectangle edges by their orientation with respect to their rectangles; specifically, which direction they face (away from the rectangle's center). Edges of the window face inward. This gives us four sets, one for each "facing" direction. An edge is described with the common coordinate in one direction and a range in the other. I'll keep them in the same x-y notation. For instance, sorted by y-coordinate:

             bottom      low-rt       up-rt
face_up   = (0-10, 0), (10-30, 8), (20-25, 17)

The top edge of the top rectangle coincides with the top of the window; it faces up,. but has no room for a white rectangle.

Similarly, the down-facing edges are

              up-left      up-rt        top
face_down = (0-13, 12), (20-25, 15), (13-30, 20)

Now it's a simple matter to match each rectangle edge with the first one that blocks its open region. For instance, consider the low-rt rectangle's face_up edge, (10-30, 8) We compare to face_down edges in order of y-coordinate, starting with y >= 8.

(0-13, 12) is the first y > 8 edge. Checking x intervals, we see that [0, 13] and [10-30] do overlap; we have a block with corners at (10, 8) and (12, 13) to expand sideways in each direction. This results in your blue rectangle.

Similarly, we will match the (face_up) left side of the window bottom with the same face_down edge. This results in your orange rectangle. Then we match the top of the up-rt (smallest) rectangle with the window top: green rectangle.

Continuing in the opposite direction, we find that two face_down edges match existing rectangles. We also match the bottom of the up-rt rectangle with the top of the low-rt rectangle, yielding the yellow rectangle.

Repeat this process with the face_left and face_right edges to obtain the red and purple rectangles, as well as a second hit of the orange rectangle.

---

Is that enough of an outline for you to implement?

Sorting the edges in order gives us the ability to do a linear search from each edge. If I'm casting this code properly, the result is an O(N) algorithm for N rectangles, although the original edge sorting is O(log N).