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

问题:

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?

回答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.

回答2:

Look into binary space partitioning (BSP).

https://en.wikipedia.org/wiki/Binary_space_partitioning

If you had just two rectangles then a bit of hacking could yield some result, but for finding intersections and unions of multiple polygons you'll want to implement BSP.

Chapter 13 of Geometric Tools for Computer Graphics by Schneider and Eberly covers BSP. Be sure to download the errata for the book!

Eberly, one of the co-authors, has a wonderful website with PDFs and code samples for individual topics:

https://www.geometrictools.com/

http://www.geometrictools.com/Books/Books.html

回答3:

For a relatively simple and reliable way, you can work as follows:

• sort all abscissas (of the vertical sides) and ordinates (of the horizontal sides) independently, and discard any duplicate.

• this establishes mappings between the coordinates and integer indexes.

• create a binary image of size NxN, filled with black.

• for every rectangle, fill the image in white between the corresponding indexes.

• then scan the image to find the corners, by contour tracing, and revert to the original coordinates.

This process isn't efficient as it takes time proportional to N² plus the sum of the (logical) areas of the rectangles, but it can be useful for a moderate amount of rectangles. It easily deals with coincidences.

---

In the case of two rectangles, there aren't so many different configurations possible and you can precompute all vertex sequences for the possible configuration (a small subset of the 2^9 possible images).

There is no need to explicitly create the image, just associate vertex sequences to the possible permutations of the input X and Y.

回答4:

Personally I believe this problem should be solved just as all other geometry problems are solved in engineering programs/languages, meshing. So first convert your vertices into rectangular grids of fixed size, using for example: MatLab meshgrid Then go through all of your grid elements and remove any with duplicate edge elements. Now sum the number of remaining meshes and times it by the area of the mesh you have chosen.