How to compute the union polygon of two (or more) rectangles

Question

For example we have two rectangles and they overlap. I want to get the exact range of the union of them. What is a good way to compute this?

These are the two overlapping rectangles. Suppose the cords of vertices are all known:

How can I compute the cords of the vertices of their union polygon? And what if I have more than two rectangles?

Answer 1

There exists a Line Sweep Algorithm to calculate area of union of n rectangles. Refer the link for details of the algorithm.

As said in article, there exist a boolean array implementation in O(N^2) time. Using the right data structure (balanced binary search tree), it can be reduced to O(NlogN) time.

Above algorithm can be extended to determine vertices as well.

Details:

Modify the event handling as follows:

When you add/remove the edge to the active set, note the starting point and ending point of the edge. If any point lies inside the already existing active set, then it doesn't constitute a vertex, otherwise it does.

This way you are able to find all the vertices of resultant polygon.

---

Note that above method can be extended to general polygon but it is more involved.