最小間隔でオブジェクトを配置するためのアルゴリズム

Question

デカルト平面上のランダムな小さなサイズの矩形（一般的に1辺に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 

いずれか従って、bは、xとyの両方に重複しないので、それらは2dに重なりません。 他のケースも同様に処理されます。

factorの定義では、これらの不等式のうちの少なくとも1つが等しく保持されるため、結果として得られる係数は最小の解です。