logo标签列表

算法：合并矩形并判断是否仍为矩形

algorithmunioncomputational-geometry
10

我有一个问题，需要测试给定的矩形集合的并集是否形成一个矩形。我在解决计算几何问题方面没有太多经验。我的解决方法是，由于我知道所有矩形的坐标，因此可以轻松地对点进行排序，然后推导出可能的最大矩形的角点。然后我可以扫描一条线，看看线上的所有点是否都在矩形内。但是，这种方法是有缺陷的，因为并集可能呈“U”形。如果您能指导我正确的方向，那将是一个很大的帮助。

如果联合操作的结果矩形中间有一个空白区域，那么这个联合矩形是否被视为有效呢？ - WeaselFox
1
这些矩形是否假定为轴对齐或共享相同的方向？ - blubb
哦，如果我能记得那个使用特殊技巧的JavaScript项目的名称...它甚至可以组合任意对象。一些三角形相关的东西。 - Karussell
仍然没有找到该项目，但这可能会有所帮助：https://dev59.com/lEvSa4cB1Zd3GeqPfZGO - Karussell
10个回答
5
你自己的版本没有考虑到矩形的边可以非平行，因此可能没有“最大可能的矩形”。我建议采用以下一般方法：
1）找到凸包。您可以在此处找到凸包计算算法 http://en.wikipedia.org/wiki/Convex_hull_algorithms。
2）检查凸包是否为矩形。您可以通过循环遍历凸包上的所有点并检查它们是否形成180度或90度角来执行此操作。如果不是，则联合不是矩形。
3）遍历凸包上的所有点。对于每个点，请检查该点和下一个点之间的中间点是否位于任何初始给定矩形的边缘上。如果每个中间点都是，则联合是矩形。否则，联合不是矩形。
复杂度将为O（n log h）用于查找凸包，O（h）用于第二部分，O（h * n）用于第三部分，其中h是凸包上的点数。

编辑： 如果目标是检查结果对象是否为填充矩形，而不是仅有边缘和角落的矩形，则添加步骤（4）。

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

对于每个线段，检查其中点是否在

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

如果每个线段至少满足其中一个条件，则结果对象是一个填充矩形。

如果你通过顶点坐标对每个矩形进行索引，那么第三步可以在少于O(h*n)的时间内完成，变成了O(h)。 - UmNyobe
第三步并不保证矩形内部也被覆盖。 - salva
@salva 根据凸包的定义，第一步就做到了。 - UmNyobe
@UmNyobe：不，计算凸包保证您获得一个包含所有给定矩形的矩形“A”，但它并不能保证该矩形完全被这些矩形覆盖。输入矩形的并集的形状可能是带有空洞的矩形。 - salva
1
一个简单的方法浮现在脑海中：如果两个矩形共享一条边[1]，那么它们一起形成一个包含两个矩形的矩形 - 无论这些矩形是相邻的[][ ]还是其中一个包含另一个[[] ]。
因此，如果矩形列表形成一个更大的矩形，那么你只需要重复迭代矩形，并将它们成对地“合并”成一个更大的矩形。如果在一次迭代中你不能合并任何矩形，则使用这些部分创建任何更大的矩形都不可能；否则，你将继续“合并”矩形，直到只剩下一个。
[1] 共享，指它们具有相同的边缘；仅仅拥有一个边缘被包含在另一个边缘中是不够的。
效率
由于效率似乎是一个问题，你可以通过创建两个矩形索引来加快速度，一个具有较大的边缘大小，另一个具有较小的边缘大小。
然后比较相同大小的边缘，如果它们相同，则合并两个矩形，从索引中删除它们，并将新矩形添加到索引中。

你可以通过在统一某些内容时不移动到下一个迭代来加快速度，而是继续到索引的末尾再重新迭代。（当一个迭代没有统一或只剩下一个矩形时停止。）

此外，由于统一后得到的矩形的边缘始终大于或等于原始矩形的边缘，因此如果按升序排列索引的边缘大小，则新矩形将插入到您正在检查的相同位置或尚未检查的位置中，因此每次统一都不需要额外的迭代周期。（由于新矩形的边缘大于本次迭代中先前检查过的所有边缘，因此它肯定不会与任何先前检查过的矩形统一。）
为了实现这一点，在特定迭代的每个步骤中，您需要尝试从任一索引的下一个较小边缘开始进行统一：

  • 如果您的index1=3且index2=6，则检查index1并推进该索引；
  • 如果该索引上的下一个边缘为5，则下一次迭代步骤将在index1=5和index2=6中进行，因此它将检查index1并推进该索引；
  • 如果该索引上的下一个边缘为7，则下一次迭代步骤将在index1=7和index2=6中进行，因此它将检查index2并推进该索引；
  • 如果该索引上的下一个边缘为10，则下一次迭代步骤将在index1=7和index2=10中进行，因此它将检查index1并推进该索引；
  • 等等。

示例

[A  ][B   ]
[C ][D    ]

可以将A与B统一，C与D统一，然后将AB与CD相统一。最终得到一个剩余的ABCD，因此是可能的。

[A  ][B   ]

[C ][D     ]

可以将A与B统一，C与D统一，但AB不能与CD统一。剩下2个，即AB和CD，因此不可能。

[A  ][B    ]
[C ][D  [E]]

可以将A与B统一，C与D，CD与E，CDE与AB。剩下1个，即ABCDE，因此可能。

[A  ][B    ]
[C ][D     ][E]

A可以与B统一，C可以与D统一，CD可以与AB统一，但E不行。剩下2个，ABCD和E，因此不可能。

陷阱

如果一个矩形被包含在另一个矩形中，但不共享边界，则此方法无法将它们统一。

解决这个问题的方法是，在遇到一个迭代不统一任何东西并且在得出不能统一矩形集之前，获取具有最宽边缘的矩形，并从索引中丢弃所有其他包含在此最大矩形内的矩形。

这仍然没有解决两种情况。

首先，考虑使用此地图的情况：

A  B  C  D
E  F  G  H

我们有矩形ACGE和BDFH。这些矩形没有共享边界，也不相互包含，但它们组成了一个更大的矩形。
其次，考虑以下情况，使用这张地图：
A B C D
E F G H
I J K L

我们有矩形ABIJ、CDHG和EHLI。它们不共享边缘，也不相互包含，而且任何两个矩形都不能合并成一个单独的矩形；但总体上形成了一个矩形。

由于存在这些陷阱，该方法并不完整。但是它可以用来大大减少问题的复杂性并减少需要分析的矩形数量。

矩形可能会重叠并覆盖外部矩形，而不共享任何边缘。 - salva
1

你可以推断出最大矩形的角点，然后遍历所有与最大矩形共享边界的矩形，例如底部，并确保线完全包含在它们的边界内。但是，如果矩形中间有空隙会导致失败。我认为复杂度将为O（n2）。

1

我认为你走在了正确的方向上。当你得到最大可能矩形的坐标后，

如果最大可能矩形是一个有效的矩形，那么它的每一边都必须是原始矩形的边的联合体。你可以扫描原始矩形集，找到那些是我们正在寻找的最大边的一部分的矩形（这可以通过检查X==largestRectangle.Top.X来完成，如果你正在查看顶部边等），让我们称之为S。

对于S中的每条边s，我们可以创建一个区间[from，to]。我们需要检查的所有内容就是所有区间的联合是否与最大矩形的边匹配。这可以通过标准算法以O(nlog(n))的时间复杂度完成，或者通过某些哈希技巧平均O(n)的时间复杂度完成（请参见http://www.careercup.com/question?id=12523672，请看我的最后一条评论（最后一条评论）中的O(n)算法）。

例如，在第一象限中，我们有两个1*1的矩形，它们的左下坐标分别为(0,0)和(1,0)。最大的矩形是2*1，左下坐标为(0,0)。由于[0,1]并[1,2]等于[0,2]，顶部和底部与最大矩形匹配，左侧和右侧同理。
现在假设我们有一个U形。在(0,0)处有3*1的矩形，在(0,1)处有1*1的矩形，在(2,1)处有1*1的矩形，我们得到的最大矩形是3*2，左下坐标为(0,0)。由于对于顶部，我们得到的[0,1]并[1,3]不等于[0,3]，因此算法将输出上述矩形的并不是一个矩形。
因此，您可以平均以O(n)的时间复杂度完成此操作，或者至少以O(nlog(n))的时间复杂度完成，如果您不想使用某些复杂的哈希桶算法。比O(n^4)好多了！
编辑：如果所有矩形中间存在空白区域，则会出现小问题。让我想一想……

编辑2：检测空白区域的简单方法是对于不是最大矩形上的点的每个角落，我们向四个方向（对角线）稍微向外移动一点，并检查是否仍在任何矩形内。这是O(n^2)。（这破坏了我美丽的O(nlog(n))！有人能想出更好的主意吗？

1
假设您的矩形与坐标轴对齐：
给定两个矩形 A、B，您可以创建一个函数，将 B 从 A 中减去，返回 A 的一组子矩形（可能为空集）：Set = subtract_rectangle(A, B)。
然后，给定一组矩形 R，您想知道它们的并集是否是一个矩形：

  1. 计算一个最大的矩形 Big，它覆盖了所有矩形，表示为 ((min_x,min_y)-(max_x,max_y))

  2. 使集合 S 包含矩形 Big：S = (Big)

  3. 对于每个矩形 B 在 R 中：

    1. S1 = ()

    2. 对于集合 S 中的每个矩形 A：

      1. S1 = S1 + subtract_rectangle(A, B)

    3. S = S1

    4. 如果 S 为空，则矩形的并集是一个矩形。

  4. 结束，S 包含未被 R 中任何矩形覆盖的 Big 的部分

如果矩形没有与坐标轴对齐，您可以使用类似的算法，但是使用三角形代替矩形。唯一的问题是减去三角形不那么容易实现，并且处理数字误差可能会很困难。

1

我以前没有看过类似的问题，所以可能有更有效的解决方法。关键问题在于你不能孤立地看待一个矩形是否包含另一个矩形，因为它们可能是相邻的但仍然形成一个矩形，或者一个矩形可能被多个矩形包含。

除非问题允许你在矩形中间留下空洞，否则你不能只看每个矩形在边界矩形上的投影，尽管这可能是一个快速的初始检查，可以在以下详尽的方法之前执行：

  1. 遍历列表一次，计算每个矩形的最小和最大x和y坐标以及面积
  2. 创建一个按大小降序排列的输入矩形列表。
  3. 最初创建一个包围矩形的工作列表
  4. 当工作列表中有矩形时
    1. 从输入列表中取出最大的矩形R
    2. 创建一个空的片段列表
    3. 对于工作列表中的每个矩形r，将其与R相交，将r分成一个包含在R内的矩形部分（如果有）和零个或多个不在R内的矩形。如果r被分割，则丢弃包含在R内的部分，并将剩余的矩形添加到片段列表中。
    4. 将片段列表的内容添加到工作列表中
0
也许...
将所有x坐标收集到一个列表中并进行排序。从此列表创建一系列相邻的间隔。对于y坐标，做同样的事情。现在你有两个间隔列表。对于每对间隔（来自x-list的A=[x1,x2]，来自y-list的B=[y1,y2]），制作它们的乘积矩形A x B = (x1,y1)-(x2,y2)。
如果每个乘积矩形都至少包含在一个初始矩形中，则联合必须是矩形。
使这变得有效（我认为我提供了一个O（n ^ 4）算法）是另一个问题。
效率是一个问题，因为我有大约10000个点，其坐标值位于-2^32和2^32之间。 - praveen
0

正如jva所说，“您自己的版本没有考虑到矩形的边缘可以彼此不平行。” 这个答案还假设了“平行”的矩形。

如果您有一个网格而不是需要无限精度，取决于矩形的数量和大小以及网格的粒度，可能可以使用暴力方法。

只需取出“最大可能的矩形”，并测试所有点，以查看每个点是否至少在一个较小的矩形中。

0
0

一般情况下，以图像思考：

  1. | 外部矩形 - 合并（内部矩形）|
  2. 检查结果是否为零
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接