最大の「ズーム」を持つ円の内側にある固定長の長方形をパックする

Question

半径Rの円の内側にN個の長方形のセットを配置するアルゴリズムが必要です。そうでない最大のサイズに拡大縮小されます円の境界を超えている。私はまだそれに取り組んでいるので、もし私が答えを見つけるなら、私はここにそれを掲示します...

Answer 1

私はおそらく、問題を解決できるかどうかをテストする関数を使ってバイナリサーチを行います与えられたN、R、およびrectangle_scale。直径

に沿って可能な限り多くの矩形が隣接直径上記できるだけ多くを取り付け

testfunction（R、rectangle_scale）

1. フィット：

   テスト機能は、おそらくのようなものでなければなりません

2. 繰り返し（矩形の上に置く。これ以上の長方形がフィットしなくなるまでこれを行う。
が収まる矩形の数を返す

バイナリ検索は、標準のようになります。

while(upperbound-lowerbound > limit) { 
    new_bound = (upperbound+lowerbound)/2; 
    num_fit = testfunction(N, R, new_bound); 
    if(num_fit > N) { 
     upperbound = new_bound; 
    } else { 
     lowerbound = new_bound; 
    } 
} 

は、理想的にはもちろん、数学的にこれをしたいと思います。近似があなたにとってうまくいくなら、あなたはおそらく地域を通してそれを行うことができます。近接は（rectangle_area * scale * N = pi * R^2）=> scale = scale = pi * R^2/N/rectangle_areaになります。

しかし、精度が必要な場合は、初期の下限/上限をインテリジェントに設定するために領域近似を使用します。

希望すると便利です。