采用矩形并集并查看并集是否仍然是矩形的算法

Question

我有一个问题，我必须测试给定的一组矩形的并集是否形成一个矩形与否。我没有太多解决计算几何问题的经验。我解决这个问题的方法是，因为我知道所有矩形的坐标，所以我可以轻松地对这些点进行排序，然后推断出可能的最大矩形的角点。然后我可以扫一条线，看看线上的所有点是否都落在矩形内。但是，这种方法是有缺陷的，并且会失败，因为并集可能是“U”的形式。如果您能将我推向正确的方向，我会很有帮助。

Answer 1

您自己的版本没有考虑到矩形的边可以彼此不平行。因此，可能没有“可能的最大矩形”。

我会尝试这种通用方法:

1) 找到凸包。您可以在这里找到凸包计算算法 http://en.wikipedia.org/wiki/Convex_hull_algorithms .

2) 检查凸包是否为矩形。您可以通过遍历凸包上的所有点并检查它们是否都形成 180 度或 90 度角来完成此操作。如果他们不这样做，联合就不是矩形。

3) 遍历凸包上的所有点。对于每个点，检查 ThisPoint 和 NextPoint 之间的中点是否位于任何初始给定矩形的边缘。如果每个中间点都这样做，则并集是一个矩形。如果不是，则 union 不是矩形。

寻找凸包的复杂度为 O(n log h)，第二部分为 O(h)，第三部分为 O(h*n)，其中 h 是凸包上的点数。

编辑:如果目标是检查生成的对象是否是填充矩形，而不是只有边角矩形，则添加步骤 (4)。

4) 找到所有由相交或接触的矩形组成的线段。注意 - 根据定义，所有这些线段都是给定矩形的边线段。如果一个矩形不与其他矩形接触/相交，则线段就是它的边。

对于每个线段检查它的中点是否是

• 在凸包的边缘
• 在给定矩形之一内
• 在两个不重叠的给定矩形的边缘。

如果每条线段至少有一个为真，则生成的对象是一个填充的矩形。