Given many horizontal and vertical lines, how to find all the rectangles that do have any sub-rectangle inside them?

Question

I have many horizontal and vertical lines which make up rectangle such as in this example.

Is there an algorithm or code which can locate every rectangle which does not contain another rectangle. I mean, the largest rectangle in this image is not a rectangle I am looking for because it contains other rectangles inside of it.

The rectangles I am looking for must be empty. I have a list of the starting points and end points of each line like (a,b) to (c,d). I want as a result a list of rectangles (x,y,w,h) or equivalent.

Note that some lines have lines intersecting them at right angles, for example the top line of the widest rectangle in this image is a single line it has an intersecting vertical line going downwards.

Answer 1

These kind of questions are largely answered by some standard Computational Geometry algorithms. I can think of a vertical sweep line algorithm for this particular problem.

Assuming a rectangle is represented by a pair of points (p1, p2), where p1 is the upper left corner and p2 is the bottom right corner. And a point has two attributes (can be accessed as p.x and p.y).

Here is the algorithm.

1. Sort all the pairs of points - O(n log n)
2. Initialize a list called sweep line status. This will hold all the rectangles that are encountered till now, that are alive. Also initialize another list called event queue that holds upcoming events. This event queue currently holds starting points of all the rectagles.
3. Process the events, start from the first element in the event queue.
   • If the event is a start point, then add that rectangle to sweep line status (in sorted order by y-coordinate) (in O(log n) time) and add its bottom-right point to the event queue at the appropriate position (sorted by the points) (again in O(log n) time). When you add it to sweep line status, you just need to check if this point lies in the rectangle alive just above it in the sweep line status. If it does lie inside, this is not your rectangle, otherwise, add this to your list of required rectangles.
   • If the event is an end point, just remove the correspoinding rectangle from the sweep line status.

Running time (for n rectangles):

• Sorting takes O(n log n).
• Number of events = 2*n = O(n)
• Each event takes O(log n) time (for insertions in event queue as well as sweep line status. So total is O(n log n).

Therefore, O(n log n).

For more details, please refer to Bentley–Ottmann algorithm. The above just a simple modification of this.

EDIT:

Just realized that input is in terms of line segments, but since they always form rectangles (according to question), a linear traversal for a pre-process can convert them into the rectangle (pair of points) form.