我有许多可能重叠的矩形，它们的大小和位置在固定平面内是随机的。由于这些矩形是随机的，有些可能不会重叠：
|-----
| | |----|
|----| | |
|----|
有些可能只重叠一个角：
|-----|
| |--|--|
|--|--| |
|-----|
有些可能包含在另一个矩形内：
|----------------|
| |
| |-----| |
| | | |
| |-----| |
|----------------|
有些可能会穿过另一个矩形：
|----------------|
| |
|--|-------------------|
| | | |
|--|-------------------|
|----------------|
etc.
我试图找到一种算法，为我提供一组矩形，这些矩形代表与输入集相同的区域，但不重叠。有些情况是显而易见的 - 包含在较大矩形内的矩形可以被丢弃，并且在角上重叠的矩形可以分成三个矩形，穿过另一个矩形的矩形也可以。我正在寻找的是一种处理所有这些情况的通用算法。我不太关心它是否效率不高——输入集相当小（最多 25 个矩形）
查找重叠的矩形很容易，但很快就会变得困难，特别是当您考虑到一个矩形可能与多个其他矩形重叠时。
这让我很头疼。有什么建议吗？
Update:
我刚刚又意识到一件事：
我可以在将矩形逐一添加到集合中时运行此算法，也可以在添加所有矩形后运行此算法。在添加矩形时，这样做可能会更容易，因为您只需要考虑一个矩形，但您仍然需要考虑单个矩形与多个其他矩形重叠的情况。
矩形与 x 轴和 y 轴平行吗？我想他们是。
您可以尝试使用KD-Trees http://en.wikipedia.org/wiki/Kd-tree.
或者，如果您想要一些自制的东西，但不一定高效，您可以“矩形化”，然后根据需要将矩形合并回来。
我所说的“矩形”是指您首先找到一个更大的矩形，其中所有矩形都适合（基本上是由最小左边缘、最大右边缘、最小底部边缘、最大顶部边缘形成的矩形）。
现在伸出矩形的所有边缘以切过大矩形。现在你有了一个“矩形”。基本上，这意味着您对垂直边缘和水平边缘进行排序，并选择相邻的对以形成一个小矩形。对于每个小矩形，您现在可以检查这是否是感兴趣区域的一部分，如果不是则拒绝它（它要么完全在内部，要么完全在外部）。
现在你有一个小矩形列表（可能是 O(n^2)，在你的情况下可能是 ~2500），它们构成了你感兴趣的区域。如果数量足够小以供将来处理，则可以仅使用它们，或者可以将它们合并在一起以减少矩形的数量。
要合并，您可以考虑一个矩形并考虑 4 种合并可能性（右侧或左侧具有相同高度的相邻矩形，或者顶部或底部具有相同宽度的相邻矩形）。
您可以通过维护边缘的排序列表（水平和平行）以及一些哈希表来加快某些处理速度（不仅仅是在合并期间）。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
