javascript - 最小间隔对象的算法

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 的定义，至少这些不等式中的一个将保持相等，因此结果因子是最小可能的解决方案。