最小间距的物体间距算法

Question

在笛卡儿平面上，给定一堆随机小尺寸的矩形(通常为每面3-8个)，每个矩形的左上角都被指定为x，y坐标，在-1到1之间随机分配，我如何将它们最小地展开，这样就不会出现保持其相对x，y位置的重叠？

我想要一个javascript的答案，但是任何可读的代码都可以。

下面是一些快速而简单的javascript来实现它：

for(some_number_of_rectangles)
  squares.push({
    x:random(-1,1), 
    y:random:(-1,1), 
    width:random(3,8), 
    height:random(3,8)
  })

示例输出：

[ 
  {x:0.5,y:0,width:2,height:2}, //intersects 3rd
  {x:0,y:1,width:2,height:2}, // intersects 4th
  {x:-1,y:0,width:2,height:2},
  {x:0,y:-0.5,width:2,height:2}, //intersects 5th
  {x:0,y:-1.5,width:2,height:2}
] // to simplify the problem, the sizes are all the same, but that won't be the case usually

及其解决办法：

[ // no intersections now
  {x:1,y:0,width:2,height:2}, // movement: 0.5
  {x:0,y:2,width:2,height:2}, // movement: 1
  {x:-2,y:0,width:2,height:2}, // movement: 1
  {x:0,y:-1,width:2,height:2} // movement: 0.5
  {x:0,y:-3,width:2,height:2} // movement: 1.5
]

Answer 1

伪码：

factor = 0
for a in rectangles:
    for b in rectangles:
        factor = max(
            factor,
            min(
                max(
                    a.width / (b.x - a.x),
                    b.width / (a.x - b.x)
                ),
                max(
                    a.height / (b.y - a.y),
                    b.height / (a.y - b.y)
                )
            )
        )
// now multiply all coordinates with factor

推理:之后，每一对矩形，也可以。

factor >= a.width / (b.x - a.x) and factor >= b.width / (a.x - b.x)

或

factor >= a.height / (b.y - a.y) and factor >= b.height / (a.y - b.y)

现在假设，例如a.x <= b.x和a.y <= b.y。然后在第一行

factor*b.x >= factor*a.x + a.width 

或者第二行

factor*b.y >= factor*a.y + a.height

因此，a和b不能同时重叠在x和y中，所以它们在2d不重叠。其他案件的处理方式类似。

根据factor的定义，这些不等式中至少有一个是相等的，因此得到的因子是最小的可能解。