Calculate the perimeter and area of intersecting rectangles?

Question

I searched a lot, but I didn't find a good answer that works for this case. We have some rectangles that are horizontal or vertical. They can be placed on the page randomly. They can overlap or have a common edge or be separate from each other. I want to find an algorithm with O(nlogn) that can find perimeter and area of these rectangles. These pictures may make the problem clear.

I think that interval trees might help, but I'm not sure how.

Answer 1

It can be done by a sweep-line algorithm.

We'll sweep an imaginary line from left to right. We'll notice the way the intersection between the line and the set of rectangles represents a set of intervals, and that it changes when we encounter a left or right edge of a rectangle.

Let's say that the intersection doesn't change between x coordinates x1 and x2. Then, if the length of the intersection after x1 was L, the line would have swept an area equal to (x2 - x1) * L, by sweeping from x1 to x2.

For example, you can look at x1 as the left blue line, and x1 as the right blue line on the following picture (that I stole from you and modified a bit :)):

It should be clear that the intersection of our sweep-line doesn't change between those points. However, the blue intersection is quite different from the red one.

We'll need a data structure with these operations:

insert_interval(y1, y2); 
get_total_length(); 

Those are easily implemented with a segment tree, so I won't go into details now.

Now, the algorithm would go like this:

1. Take all the vertical segments and sort them by their x coordinates.
2. For each relevant x coordinate (only the ones appearing as edges of rectangles are important):
   • Let x1 be the previous relevant x coordinate.
   • Let x2 be the current relevant x coordinate.
   • Let L be the length given by our data structure.
   • Add (x2 - x1) * L to the total area sum.
   • Remove all the right edges with x = x2 segments from the data structure.
   • Add all the left edges with x = x2 segments to the data structure.

By left and right I mean the sides of a rectangle.

This idea was given only for computing the area, however, you may modify it to compute the perimeter. Basically you'll want to know the difference between the lengths of the intersection before and after it changes at some x coordinate.

The complexity of the algorithm is O(N log N) (although it depends on the range of values you might get as input, this is easily dealt with).

You can find more information on the broad topic of sweep-line algorithms on TopCoder.

You can read about various ways to use the segment tree on the PEG judge wiki.

Here's my (really old) implementation of the algorithm as a solution to the SPOJ problem NKMARS: implementation.