Find total area of overlapping rectangles

Question

Suppose a set of rectangles, each of them has sides parallel with x and y axis and is given by the coordinates of opposite points. How to effectively calculate the total area they cover?

If two or more share the same piece of area, it is counted only once.

I've read that it is called Klee's measure problem and it should be solved using a sweep line and a segment tree which should track the covered parts of plane currently under the sweep line.

However, I don't know how should the update of this segment tree be done (for example, if you remove a large rectangle overlapping many smaller ones). Does anybody know how to do this?

Thanks for help.

Answer 1

Diego That doesn't quite solve this problem, it's something a bit different

Answer 2

Not sure how to answer your question. Found a similar one on SO. It has a pretty good explanation of the Bentley-Ottmann algorithm.
https://stackoverflow.com/q/10049454