矩形的马赛克

Question

我有一个大窗口，其中有n个小窗口。任务放置小窗户，使他们之间没有交集，或说这是不可能的。

所有窗口都是矩形的，并具有所有顶点的坐标。

我知道确定是否容易将其中一个矩形与其他矩形交叉。只要查看包含任何其他矩形中顶点的坐标就足够了。

但是，这里是如何找到一个可以移动这个矩形的空闲区域？

就我而言，小窗口出现在大窗口中。问题看起来像。

Answer 1

这看起来有点像Rectangle Packing问题。 有examples和implementations那里可以帮助。

不同之处在于你正在处理的是UI，而不是纹理或其他问题。你可以选择上面提到的解决方案，但我想你会需要某种过渡动画，以便用户看到/理解他/她的窗口最终会到达哪里。

这取决于我想这个功能是如何工作的。用户是否允许首先与窗口相交？

我想所有的矩形将需要适应一个larget一个（显示）

我一直在玩的纸在我的办公桌不同大小的矩形和这里的东西，想到：

1st确定您是否有足够的空间：将左侧空间分割为矩形并添加矩形区域，然后检查空间区域是否大于或等于交叉区域。如果继续。

1. 遍历所有矩形并找到交点。
2. 对于每个交叉点，存储所涉及的矩形。
3. 循环遍历所有具有交叉点和存储的可用空间中
   剩余方向（例如，左，左上，上，等）
4. 对于交点每个矩形，在空间添加水平左侧的矩形检查它是否大于交叉矩形的宽度，然后在垂直空间上做同样的事情。这一步应该允许确定是否只能移动带有交点的矩形以获得足够的空间来清除交点。
5. 如果上面的aplies使用剩余的空间来确定你需要移动每个矩形需要多少。根据哪个剩余间距较大（例如，总顶部+底部与总左侧+右侧），选择分离方向（垂直或水平）。然后在分离的方向移动每个盒子（例如，g如果水平移动具有最小水平空间的矩形的那个量，则另一个矩形朝向它的剩余空间）并且重新评估这种情况的交点。如果没有交叉口，万岁......否则，垂直空间也是这样。
6. 如果此品4不适用，这意味着您不能使用它们周围的空间稍微移动矩形，则需要使用更多空间。包括最近的盒子和它的空间 然后再检查一次额外的空间是否足够。

这里就是我所说的剩余空间拆分成箱找到区域：

我建议首先检查矩形包装解决方案，我的联系，因为它们使用的可用空间优化它实际上工作，而不是我通过玩纸带来:) 我还没有编码/测试我的解决方案呢。

HTH

Answer 2

一个简单的解决方案是蛮力。对所有小矩形进行排列，并将它们放置在最左上角的位置。如果你设法放置它们，你有一个解决方案。如果你失败了，你回到下一个排列并再试一次。如果用完选项，则失败。这将起作用，但显然当矩形数量增加时，它很快就无法使用。