如何计算两个（或更多）矩形的联合多边形 [英] How to compute the union polygon of two (or more) rectangles

问题描述

例如，我们有两个矩形，它们重叠。我想知道他们联合的确切范围。什么是计算这个的好方法？

这是两个重叠的矩形。假设顶点的线都是已知的：

我可以计算其联合多边形顶点的帘线吗？如果我有两个以上的矩形？

解决方案

存在

修改事件处理，如下所示：

当您将边缘添加/移除到活动集时，边缘的点和终点。如果任何点位于已经存在的活动集内，那么它不构成顶点，否则它就是。

这样您就可以找到所有的顶点结果多边形。

---

请注意，上面的方法可以扩展到一般的多边形，但涉及更多。 b $ b

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?

解决方案

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.

这篇关于如何计算两个（或更多）矩形的联合多边形的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！