予有Rects，其中大部分相互交叉的n大小的集合。我想删除的交点，减少交叉Rects成更小的非相交rects。

I have an n-sized collection of Rects, most of which intersect each other. I'd like to remove the intersections and reduce the intersecting Rects into smaller non-intersecting rects.

我可以很容易蛮力解决办法，但我正在寻找一个高效的算法。

I could easily brute force a solution, but I'm looking for an efficient algorithm.

下面是一个可视化的：

原文：

加工：

在理想情况下的方法签名是这样的：

Ideally the method signature would look like this:

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

的输出将是大于或等于输入，其中输出解决了上述视觉重新presentation

the output would be greater or equal to the input, where the output resolves the above visual representation.

推荐答案

这是一个问题，我解决了过去。的第一件事它使用x或边缘之一的y值的矩形排序。比方说，你在y方向的订购和使用上边缘。在你的例子最顶端的矩形是第一个排序顺序。为每个矩形你知道其在y方向上的尺寸。

this is a problem I solved in the past. The first thing it to sort the rectangles using the x or y value of one of the edges. Lets say you order in the y-direction and use the top edge. The topmost rectangle in your example is first in sorted order. For each rectangle you know its size in the y-direction.

现在，每个条目（称之为当前条​​目，它对应于一个矩形）的排序列表，你向前搜索列表直至到达一个条目大于当前的入门+相应的矩形大小。 （叫它停止输入）

Now, for each entry (call it the the current entry, it corresponds to a rectangle)in the sorted list you search forward through the list until you reach an entry greater than the current entry + the corresponding rectangle size. (call it the stopping entry)

在目前的入门和该停止条目之间的排序列表中的任何条目将是潜在的交叉点。简单地检查是否矩形的x-区域相交。

Any entries in the sorted list between the current entry and this stopping entry will be potential intersections. Simply check if the rectangles x-ranges intersect.

当选择在x或y方向进行排序​​，这将是更好的选择是大尺寸，因为这将意味着在较少​​的交叉点平均所以较少检查

When choosing to sort in the x or y direction, it will be better to choose the dimension that is larger as this will imply fewer intersection on average so less checking.

下面是一个例子。矩形被定义为R（X1，X2，Y1，Y2），其中x1为左侧，X 2是右侧，Y1是顶部和y2是底

Here is an example. Rectangles are defined as R(x1,x2,y1,y2) where x1 is the left side, x2 is right side, y1 is top and y2 is bottom

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给

sort according to y1 to give

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

这样，矩形1具有Y1 +尺寸= 0 + 4 = 4暗示它将可能相交矩形3体（y1值= 3'; 4）和矩形4体（y1值= 3 4;），但不矩形2（ Y1值= 6> 4）......没必要2后办理入住手续的任何rectangels列表中的

so, rectangle 1 has y1 + size = 0 + 4 = 4 implying it will potentially intersect rectangle 3 (y1 value = 3 < 4) and rectangle 4 (y1 value = 3 < 4) but not rectangle 2 (y1 value = 6 > 4)...no need to check any rectangels in the list after 2

矩形3具有Y2 +尺寸= 2 + 3 = 5意味着它将可能相交矩形4体（y1值= 3'; 5），但不recatngle 2体（y1值= 6> 5）不需要检查任何rectangels在2后，名单

Rectangle 3 has y2 + size = 2 + 3 = 5 implying it will potentially intersect rectangle 4 (y1 value = 3 < 5) but not recatngle 2 (y1 value = 6 > 5) no need to check any rectangels in the list after 2

矩形4具有Y2 +尺寸= 3 + 4 = 7暗示它将可能相交矩形2体（y1值= 6 7;），但不recatngle 5体（y1值= 9> 7）

Rectangle 4 has y2 + size = 3 + 4 = 7 implying it will potentially intersect rectangle 2 (y1 value = 6 < 7) but not recatngle 5 (y1 value = 9 > 7)

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

Of course, with large numbers of rectangles you will generally only have to check a fraction of the possible pairs for intersection.