0

半径Rの円の内側にN個の長方形のセットを配置するアルゴリズムが必要です。これにより、長方形の境界を超えない最大のサイズに拡大されます。まだ作業中なので、答えが見つかったらここに投稿します...

4

1 に答える 1

2

これを行う場合は、問題が特定のN、R、およびrectangle_scaleで解決可能かどうかをテストする関数を使用して、二分探索で行う可能性があります。

テスト関数はおそらく次のようになります。

testfunction（R、rectangle_scale）

  1. 直径に沿ってできるだけ多くの長方形を合わせます
  2. 直径の上にある長方形に隣接する直径の上にできるだけ多くフィットします（例：2 * R / rectangle_scale * side）またはそのようなもの）
  3. 繰り返します（配置した長方形の上に配置します。長方形が収まらなくなるまでこれを行います
  4. 適合する長方形の数を返します

その場合、二分探索が標準になります。

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になります。

ただし、精度が必要な場合は、インテリジェントな方法で初期の下限/上限を設定するために面積近似のみを使用します。

お役に立てれば！

于 2011-09-09T19:43:52.270 に答える