如何计算两个（或更多）矩形的并集多边形

Question

7

例如，我们有两个矩形，它们重叠在一起。我想获得它们并集的精确范围。有什么好的方法可以计算这个吗？

这是两个重叠的矩形。假设所有顶点的坐标都已知：

我该如何计算它们的并集多边形顶点的坐标？如果有超过两个矩形怎么办？

- daydayup

4个回答

4

对于一个相对简单可靠的方法，您可以按照以下步骤进行操作：

这个过程并不高效，因为它需要与N²成比例的时间加上矩形（逻辑）面积的总和，但对于适量的矩形来说是有用的。它可以轻松处理重叠的情况。

对于两个矩形的情况，可能的不同配置并不多，您可以预先计算可能配置的所有顶点序列（2^9个可能图像的一个小子集）。

无需显式创建图像，只需将顶点序列与输入X和Y的可能排列关联即可。

- user1196549

1

了解二叉空间分割（BSP）。

如果你只有两个矩形，那么一些技巧可以产生一些结果，但是要找到多边形的交集和并集，您需要实现BSP。

Schneider和Eberly的《计算机图形学几何工具》第13章涵盖了BSP。请务必下载该书的勘误表！

其中一位合著者Eberly拥有一个精美的网站，提供单个主题的PDF和代码示例：

- Rethunk

0

个人认为这个问题应该像工程程序/语言中解决所有其他几何问题一样，使用网格化方法。首先，使用例如MatLab meshgrid将您的顶点转换为固定大小的矩形网格。然后遍历所有网格元素并删除任何具有重复边缘元素的元素。现在将剩余网格的数量相加，并乘以您选择的网格的面积。

- bmbigbang

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Rishit Sanmukhani · Accepted Answer

存在一种线性扫描算法来计算n个矩形并集的面积。详情请参考链接。

如文章所述，存在一个O(N^2)时间的布尔数组实现。使用正确的数据结构（平衡二叉搜索树），可以将其降低到O(NlogN)时间。

上述算法也可扩展用于确定顶点。

细节：

将事件处理方式修改如下：

当您将边添加/删除到活动集时，请注意边的起点和终点。如果任何点位于已存在的活动集内，则它不构成一个顶点，否则它是一个顶点。

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

请注意，上述方法可以扩展到一般的多边形，但需要更多的涉及。