Tho*_*omi 8 language-agnostic algorithm ascii-art
我有一些可能重叠的矩形,在固定平面内随机大小和位置.由于这些矩形是随机的,有些可能不会重叠:
|-----
| | |----|
|----| | |
|----|
有些可能只有一个角重叠:
|-----| | |--|--| |--|--| | |-----|
有些可能包含在另一个矩形内:
|----------------| | | | |-----| | | | | | | |-----| | |----------------|
有些可能会通过另一个矩形:
|----------------| | | |--|-------------------| | | | | |--|-------------------| |----------------|
等等
我正在尝试找到一种算法,该算法为我提供了一组矩形,这些矩形表示与输入集相同的区域,但没有重叠.有些情况很明显 - 可以丢弃包含在较大矩形内的矩形,并且在角上重叠的矩形可以分成三个矩形,也可以将矩形分成另一个矩形.我正在寻找的是一种处理所有这些情况的通用算法.我不在乎它是否效率不高 - 输入设置相当小(最多25个矩形)
找到重叠的矩形很容易,但它很快就会变得更难,尤其是当您考虑到一个矩形可能与多个其他矩形重叠时.
这是我的头脑.有什么建议吗？
更新:
我刚刚意识到了一件事:
我可以在添加矩形的时候运行这个算法,一个接一个地添加,或者在添加了所有矩形之后.添加矩形可能更容易,因为您只需要考虑一个矩形,但您仍需要考虑单个矩形与多个其他矩形重叠的情况.
小智 3
矩形与 x 轴和 y 轴平行吗？我想他们是。
您可以尝试使用KD-Trees。
或者，如果您想要一些自制的东西，但不一定高效，您可以“矩形化”，然后根据需要将矩形合并回来。
我所说的“矩形”是指您首先找到一个更大的矩形，其中所有矩形都适合（基本上是由最小左边缘、最大右边缘、最小底部边缘、最大顶部边缘形成的矩形）。
现在伸出矩形的所有边缘以切过大矩形。您现在有了一个“矩形”。基本上，这意味着您对垂直边缘和水平边缘进行排序，并选择相邻的对以形成一个小矩形。对于每个小矩形，您现在可以检查这是否是感兴趣区域的一部分，如果不是则拒绝它（它要么完全在内部，要么完全在外部）。
现在你有一个小矩形列表（可能是 O(n^2)，在你的情况下可能是 ~2500），它们构成了你感兴趣的区域。如果数量足够小以供将来处理，则可以仅使用它们，或者可以将它们合并在一起以减少矩形的数量。
要合并，您可以考虑一个矩形并考虑 4 种合并可能性（右侧或左侧具有相同高度的相邻矩形，或者顶部或底部具有相同宽度的相邻矩形）。
您可以通过维护边缘的排序列表（水平和平行）以及一些哈希表来加快某些处理速度（不仅仅是在合并期间）。