寻找一种非“暴力算法”来移除一个矩形集合中相交的区域。

Question

我有一个包含n个Rect的集合，大部分相互交叉。我想要移除这些交叉部分，并将相交的Rect缩小为更小的不相交矩形。

我可以很容易地使用暴力方法解决，但我正在寻找一种高效的算法。

这里是一个示例图：

原始矩形：

处理后的结果：

理想情况下，该方法的签名应如下所示：

public static List<RectF> resolveIntersection(List<RectF> rects);

输出结果将大于或等于输入，其中输出结果解决了上述可视化表示。

- Michael Pardo

---

红色矩形占用了本可以被绿色或橙色矩形占用的空间，这是出于什么考虑？（让它们变长...） - cyber-monk

我随意地将那个矩形分割开来。 - Michael Pardo

原来这正是我想要的：http://google-maps-utility-library-v3.googlecode.com/svn/trunk/routeboxer/docs/examples.html我可能应该寻求实际问题的解决方案，而不是在实现过程中创造问题并寻求解决方案。 - Michael Pardo

Answer 1

扫描线算法在处理2D空间中的交点方面表现良好。我指的是考虑一条水平线从一个矩形边缘向下移动到下一个矩形边缘。该线会碰到多个矩形，形成所谓的活动列表。在每次移动时，都会更新活动列表。

通过研究水平线上的横坐标范围，您可以检测出重叠部分。

对所有配置进行仔细研究，应该可以在单次扫描中按照所需方式拆分矩形，并且比暴力方法具有更低的复杂度（接近于N^1.5而不是N^2）。

- user1196549

---

这可能比在上面的例子中采用暴力方法稍微更有效率些，但我认为这是我能做到最好的。谢谢。 - Michael Pardo

众所周知，矩形交集问题可以在最优时间O(N Log(N) + K)内解决，其中K是实际交点的数量，例如通过使用区间树。除了线扫描，还可以使用分治算法来解决该问题。 - user1196549

Answer 2

这是我过去解决的一个问题。首先，需要使用其中一条边的x或y值对矩形进行排序。假设您按y方向排序并使用顶部边缘，则您示例中最上面的矩形将首先按排序顺序排列。对于每个矩形，您知道它在y方向上的大小。

现在，针对排序后的列表中的每个条目（称其为当前条目，它对应一个矩形），向前搜索列表，直到找到一个大于当前条目+相应的矩形大小的条目（称其为停止条目）。

在当前条目和该停止条目之间的排序列表中的任何条目都将成为潜在的相交点。只需检查矩形的x范围是否相交即可。

在选择按x或y方向排序时，最好选择较大的维度，因为这将平均意味着更少的交点，从而减少检查次数。

以下是一个示例。矩形被定义为R（x1，x2，y1，y2），其中x1为左侧，x2为右侧，y1为顶部，y2为底部。

rectangle 1 (1,5,0,4) 
rectangle 2 (7,9,6,8)
rectangle 3 (2,4,2,3)
rectangle 4 (3,6,3,7)
rectangle 5 (3,6,9,15)

按照y1进行排序。

#              y1  size
rectangle 1     0   4
rectangle 3     2   3
rectangle 4     3   4
rectangle 2     6   2
rectangle 5     9   6

所以，矩形1的y1 + size = 0 + 4 = 4，意味着它可能与矩形3（y1值=3 < 4）和矩形4（y1值=3 < 4）相交，但不会与矩形2（y1值=6 > 4）相交...在第2个矩形之后不需要检查列表中的任何矩形。

矩形3的y2 + size = 2 + 3 = 5，意味着它可能与矩形4（y1值=3 < 5）相交，但不会与矩形2（y1值=6 > 5）相交...在第2个矩形之后不需要检查列表中的任何矩形。

矩形4的y2 + size = 3 + 4 = 7，意味着它可能与矩形2（y1值=6 < 7）相交，但不会与矩形5（y1值=9 > 7）相交。

当然，对于大量的矩形，您通常只需要检查一小部分可能的交叉对。

- martino

---

一种改进方法是：决定使用哪个维度进行排序，可以查看该维度中值的范围除以该维度中矩形平均大小。在上面的示例中，平均y大小为19/5，而平均x大小为15/5，因此您可以预期（没有其他知识）在y方向上有更多的交叉点（矩形y大小平均比x大小大，因此更有可能相交）。如果您正在查看数千个矩形，则此选择可能会产生很大的差异。 - martino

Answer 3

你所描述的是装箱问题，可以看一下wikipedia。

它指的是this文章，描述了一个在矩形内部装填矩形的算法。

以下是文章内容：

本文介绍了一种快速算法，将多个不同宽度和高度的矩形装入一个外接矩形中，且不重叠，并以最小化外接矩形中浪费空间的方式进行装箱。

- yurib

---

你确定吗？你如何使用矩形装箱将重叠的矩形分解为较小的非重叠矩形？在我看来，解决方案可能基于扫描线算法：http://en.wikipedia.org/wiki/Sweep_line_algorithm。 - Timo

@Timo 这是装箱问题的一个变体，我已经添加了引言的前几行。 - yurib

@Timo 尽管我以前从未听说过扫描线算法，但根据我所读的内容，它听起来很有趣，也可能是一个不错的方法。 - yurib

这不在另一个矩形内，包围边界由所有矩形的并集组成。扫描线似乎更接近。 - Michael Pardo