如何以最小的重叠分布矩形

Question

基本上，我需要在更大的矩形中随机分布各种矩形。因此：

1. 虽然有足够的空间，但矩形不会重叠或仅重叠一点。
2. [如果没有足够的空间，则矩形重叠，但仍尝试尽可能少地重叠（因此它们全部堆叠在一个地方）。

我不需要经典理想的左上到右下包装。关键是我需要随机分布。

起初，我尝试通过随机选择矩形的位置然后将碰撞与已放置的所有矩形进行比较来对其进行暴力破解。显然，这并不理想。

然后，我尝试为空间分配“点”，并在这些点附近放置矩形。矩形越接近一点，它施加的压力就越大。然后，对于放置的每个矩形，该压力会逐渐增加。算法尝试以最小的压力将矩形放置在点附近。不幸的是，这导致矩形堆积在左上角和右下角附近。

（（如果您也要关闭此窗口，我什至不知道您还需要什么信息）。

Answer 1

假设您不希望有任何重叠，则可以使用称为扫动的方法来查找所有新矩形中间的可能位置。可以将其划分为矩形，然后计算每个矩形的面积，并以各自的比率随机选择一个矩形。如果那是一个好的解决方案，请询问更多详细信息。

并且如果它们可以重叠，比如说10％，那么就使矩形小于10％，分布它们，然后它们向后膨胀。