获取矩形并集并查看并集是否仍为矩形的算法

Question

我有一个问题,我必须测试给定的矩形组的并集是否形成矩形.我没有太多解决计算几何问题的经验.我对问题的处理方法是,因为我知道所有矩形的坐标,所以我可以轻松地对点进行排序,然后推导出最大矩形的角点.然后我可以扫描一条线,看看线上的所有点是否落在矩形内.但是,这种方法是有缺陷的,这会失败,因为联合可能是'U'的形式.如果你能把我推向正确的方向,那将是一个很大的帮助.

Answer 1

您自己的版本没有考虑到矩形的边缘可能彼此不平行.因此,可能没有"可能的最大矩形".

我会尝试这种一般方法:

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

2)检查凸包是否是矩形.您可以通过循环凸包上的所有点并检查它们是否都形成180度或90度角来完成此操作.如果他们不这样做,联合不是一个矩形.

3)穿过凸壳上的所有点.对于每个点,检查ThisPoint和NextPoint之间的中间点是否位于任何最初给定的矩形的边缘.如果每个中间点都有,那么union就是一个矩形.如果没有,union不是矩形.

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

编辑: 如果目标是检查生成的对象是否是填充矩形,而不仅是边和矩形矩形,则添加步骤(4).

4)找到通过交叉或触摸矩形形成的所有线段.注 - 根据定义,所有这些线段都是给定矩形的边缘段.如果矩形不接触/交叉其他矩形,则线段是它的边缘.

对于每个线段,检查它是否为中间点

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

如果每个线段中至少有一个为真,则生成的对象是填充矩形.

Answer 2

或许...

收集列表中的所有 x 坐标，并对它们进行排序。从此列表中创建一系列相邻间隔。对 y 坐标执行相同的操作。现在您有两个间隔列表。对于每对间隔（A=[x1,x2]来自 x 列表，B=[y1,y2]来自 y 列表），制作它们的乘积矩形A x B = (x1,y1)-(x2,y2)

如果每个单个产品矩形至少包含在一个初始矩形中，则并集必须是一个矩形。

使其高效（我想我已经提供了O (n ⁴ ) 算法）完全是一个不同的问题。