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

Question

例如，我们有两个矩形，它们重叠。我想得到它们并集的确切范围。计算这个的好方法是什么？

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

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

Answer 1

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

如文章所述，存在 O(N^2) 时间的 bool 数组实现。使用正确的数据结构(平衡二叉搜索树)，它可以减少到 O(NlogN) 时间。

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

详细信息:

修改事件处理如下:

当您向事件集添加/删除边时，请注意边的起点和终点。如果任何点位于已经存在的事件集内，则它不构成顶点，否则构成顶点。

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

---

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