Blogger: Massive Algorithms - Edit post

Blogger: Massive Algorithms - Edit post

An efficient way of computing this area is to use a sweep algorithm. Let us assume that we sweep a vertical line L(x) through the union of rectangles U: first of all, you need to build an event queue Q, which is, in this case, the ordered list of all x-coordinates (left and right) of the rectangles. during the sweep, you should maintain a 1D datastructure, which should give you the total length of the intersection of L(x) and U. The important thing is that this length is constant between two consecutive events q and q' of Q. So, if l(q) denotes the total length of L(q+) (i.e. L just on the rightside of q) intersected with U, the area swept by L between events q and q' is exactly l(q)*(q' - q). you just have to sum up all these swept areas to get the total one. We still have to solve the 1D problem. You want a 1D structure, which computes dynamically a union of (vertical) segments. By dynamically, I mean that you sometimes add a new segment, and sometimes remove one.

Read full article from Blogger: Massive Algorithms - Edit post