我有一个大小为X的面板Y.我想放置N个矩形,随机大小,在这个面板上,但我不希望它们中的任何一个重叠.我需要知道这些矩形的X,Y位置.
算法,有人吗？
编辑:所有N个矩形在开始时都是已知的,可以按任何顺序进行选择.这会改变程序吗？
我有一些可能重叠的矩形,在固定平面内随机大小和位置.由于这些矩形是随机的,有些可能不会重叠:
|-----
| | |----|
|----| | |
|----|
有些可能只有一个角重叠:
|-----| | |--|--| |--|--| | |-----|
有些可能包含在另一个矩形内:
|----------------| | | | |-----| | | | | | | |-----| | |----------------|
有些可能会通过另一个矩形:
|----------------| | | |--|-------------------| | | | | |--|-------------------| |----------------|
等等
我正在尝试找到一种算法,该算法为我提供了一组矩形,这些矩形表示与输入集相同的区域,但没有重叠.有些情况很明显 - 可以丢弃包含在较大矩形内的矩形,并且在角上重叠的矩形可以分成三个矩形,也可以将矩形分成另一个矩形.我正在寻找的是一种处理所有这些情况的通用算法.我不在乎它是否效率不高 - 输入设置相当小(最多25个矩形)
找到重叠的矩形很容易,但它很快就会变得更难,尤其是当您考虑到一个矩形可能与多个其他矩形重叠时.
这是我的头脑.有什么建议吗？
更新:
我刚刚意识到了一件事:
我可以在添加矩形的时候运行这个算法,一个接一个地添加,或者在添加了所有矩形之后.添加矩形可能更容易,因为您只需要考虑一个矩形,但您仍需要考虑单个矩形与多个其他矩形重叠的情况.