如何计算两个(或更多)矩形的并集多边形

Question

例如,我们有两个矩形,它们重叠.我想得到他们联合的确切范围.计算这个的好方法是什么？

这是两个重叠的矩形.假设顶点的绳索都是已知的:

如何计算其联合多边形顶点的绳索？如果我有两个以上的矩形怎么办？

Answer 1

存在一个Line Sweep Algorithm来计算 n 个矩形的联合面积。有关算法的详细信息，请参阅链接。

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

上述算法也可以扩展到确定顶点。

细节：

修改事件处理如下：

向活动集中添加/删除边时，请注意边的起点和终点。如果任何点位于已存在的活动集中，则它不构成顶点，否则构成顶点。

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

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