我有许多可能重叠矩形随机大小和位置，一个固定平面内。由于这些矩形是随机的，有些人可能不重叠的：

I have a number of possibly overlapping rectangles, of random size and position within a fixed plane. Since these rectangles are random, some may not overlap:

|-----
|    |    |----|
|----|    |    |
          |----|

有些人可能只用一个角落重叠的：

Some may overlap by just one corner:

|-----|
|  |--|--|
|--|--|  |
   |-----|

有些人可能会被包含在另一个矩形内：

Some may be contained inside another rectangle:

|----------------|
|                |
|   |-----|      |
|   |     |      |
|   |-----|      |
|----------------|

有些人可能会通过一个矩形：

Some may pass through another rectangle:

   |----------------|
   |                |
|--|-------------------|
|  |                |  |
|--|-------------------|
   |----------------|

等。

我试图找到一种算法，给了我一组重新present相同的区域作为输入组矩形，但没有重叠。某些情况下是明显的 - 含有一个较大的矩形内的矩形可被丢弃，并且在一个角落重叠矩形可以分成三个矩形，作为罐矩形穿过另一个矩形。我正在寻找的，是一个通用的算法，所有这些案件处理。我不在乎多，如果它不是精辟效率 - 输入集是相当小（25长方形最多）

I'm trying to find an algorithm that gives me a set of rectangles that represent the same area as the input set, but without overlapping. Some cases are obvious - rectangles contained within a larger rectangle can be discarded, and rectangles that overlap on a corner can be split into three rectangles, as can rectangles that pass through another rectangle. What I'm looking for, is a generic algorithm that deals with all these cases. I don't care much if it's not brilliantly efficient - the input set is rather small (25 rectangles at most)

查找重叠是很容易的矩形，但很快愈来愈难，尤其是当你考虑一个矩形可能与其他多个矩形重叠。

Finding rectangles that overlap is easy, but it quickly gets harder from there, especially when you consider that one rectangle may overlap with multiple other rectangles.

这是做我的头，任何建议？

This is doing my head in. Any suggestions?

更新：

我才意识到一件事：

我可以运行该算法在该矩形被添加托特他设定，一个接一个，或者所有的矩形已经被添加后的时间。它可能会更容易做到这一点作为矩形被添加，因为你只能有一个长方形的考虑，但你仍然需要考虑在一个单一的矩形重叠其他多个矩形的情况。

I can either run this algorithm at the time that the rectangles are added tot he set, one by one, or after all the rectangles have been added. It may be easier to do it as the rectangles are being added, since you only have one rectangle to consider, but you still need to account for the situation where a single rectangle overlaps multiple other rectangles.

推荐答案

是矩形平行于x＆放大器; Y轴？我想他们是。

Are the rectangles parallel to the x&y axes? I suppose they are.

您可以尝试使用 KD树。

或者，如果你想要的东西自产自销，而不一定有效，你可以'rectangulate，然后如果需要合并矩形回来​​了。

Or if you want something homegrown and not necessarily efficient you could 'rectangulate' and then if needed merge rectangles back.

通过rectangulation我的意思是，你先找到一个更大的矩形，其中所有的矩形适合（基本上是由至少左侧边缘形成的矩形，greated右边缘，至少底部边缘，最大的顶边）。

By 'rectangulation' I mean you first find a bigger rectangle in which all rectangles fit (basically the rectangle formed by least left edge, greated right edge, least bottom edge, greatest top edge).

现在伸出矩形的所有边缘穿过大矩形切割。您现在有一个'rectangulation。基本上所有这意味着你排序的垂直边缘和水平边缘和接相邻对，形成一个小矩形。对于每一个小矩形，您现在可以检查，如果这是有趣的区域一部分，从而拒绝它，如果它不是（这可以是全内或完全外）。

Now extend out all the edges of the rectangles to cut across the big rectangle. You now have a 'rectangulation'. Basically all this means is that you sort the vertical edges and the horizontal edges and pick adjacent pairs to form a small rectangle. For each small rectangle, you can now check if this is part of the interesting area or not and reject it if it is not (It is either full within or fully outside).

现在你（你的情况可能是〜2500可能为O（n ^ 2）），从而弥补了您感兴趣的区域的小矩形列表。如果数量足够足够小，以备将来处理，你可以只使用这些，或者你可以把它们合并起来以减少矩形的数量。

Now you have a list of small rectangles (possibly O(n^2), in your case perhaps ~2500) which make up the area of your interest. If the number is sufficiently small enough for your future processing, you could just use these, or you could merge them together to reduce the number of rectangles.

要合并，你可以考虑一个矩形，并考虑4 possiblitlies的合并（同一高度的相邻矩形向左或向右，或者相同的宽度到顶部或底部的相邻矩形）。

To merge you could consider a rectangle and consider 4 possiblitlies for a merge (adjacent rectangle of same height to right or left, or adjacent rectangle of same width to top or bottom).

您可以通过维护边缘（水平和平行），也许有些哈希表的排序列表加快一些处理（不只是合并过程中）。

You could speed up some processing (not just during merge) by maintaining a sorted list of edges (both horizontal and parallel) and maybe some hashtables.