円に何個の四角形を詰めることができますか？

Question

いくつの正方形のサイズxは、半径Rの円にパックできますか？

解決策は必要ありません。私はちょっとしたスタートアイデアが必要です。

Answer 1

私はこのような長い答えを書くことをお詫び申し上げます。私のアプローチは、理論上の最大値と保証最小値で開始することです。問題に近づくと、これらの値を使用して、使用するアルゴリズムの良さを判断できます。より良い最小値を考えることができれば、それを代わりに使うことができます。

我々は単に円の面積を使用して問題の上限を定義することができ

Lを使用して、梱包された正方形の幅または高さであり、rは円の半径である

Upper Limit = floor((PI * (r pow 2))/(L * L)) 

あなた四角をパッキングしています。これは上限であると確信しています。なぜなら、a）離散数のボックスを持たなければならず、b）円の面積よりも多くのスペースを取ることができないからです。 （正式な証拠は、これより1つ多くの箱があると仮定した場合、箱の面積の合計が円の面積よりも大きいと仮定した線のどこかで働く）。

上限があるため、すべてのサークルに存在するすべてのソリューションを使用して、最小限のソリューションと呼ぶことができます。

だから、サークル内に収まる最大の正方形を見て、すべてのサークルに存在する解を考えてみましょう。

あなたが円内に収まることができる最大の正方形perimiter上の4点を有し、（ピタゴラスの定理を用いて、より短い辺の長さの半径を使用して）sqrt(2) * radiusの幅と長さを有する

したがって、最初に注意する点は、sqrt(2) * radiusが四角形の寸法よりも小さい場合は、四角形を四角形に合わせることができないということです。

ここで指定したLを使用して、この大きな正方形を正方形の正方形に分割する簡単な計算を行うことができます。だから、あなたはこの最大の正方形内にsqauresのグリッドを持っています。あなたはこの本のグリッドの1行に収まる正方形の数は

floor((sqrt(2) * radius)/ L) 

あるので、この最小ソリューションは、あなたが円の内側の正方形の少なくとも

Lower Limit = floor((sqrt(2) * radius)/ L) pow 2 

番号を持つことができると主張しています。

もしあなたが迷ってしまった場合、私がしたのは、円の中に入ることができる最大の四角形を取って、少なくとも1つの解決策を提供するために、

この段階で0になると、サークル内に四角形を入れることはできません。

これで、理論上の最大値と最小値が得られるようになりました。あなたは、矩形を詰めるのに好きなヒューリスティックアルゴリズムを試すことができます。単純なアルゴリズムは、円を行に分割し、各行にできるだけ多くのsqaureに収まるようにすることです。その後、より良い解決策を思いつくために、この最小限をガイドラインとして採用することができます。あなたがより良い解決策を探してより多くの処理能力を使いたいなら、あなたは理論的にどれほど近づいているかのガイドラインとして理論を使用します。

あなたがこれについて気にするならば、私が識別している最小限のアルゴリズムでカバーの最大と最小の理論的なパーセンテージを計算することができます。最大の広場は常に一定の比率（私が思う円の内側の面積のπ/ 4または約78.5％）をカバーします。したがって理論上の最大値の最小値は78.5％です。そして、最小の非自明な理論上の最小値は、あなたが梱包している正方形が最大の正方形の幅と高さの半分よりも大きい場合に起こる、円に収まる基本的に1平方フィートの正方形で25％を占めており、約20％のおおよそのカバーを得ます。

Answer 2

好きなだけ多くの四角形を丸で囲むことができます。あなたがこの声明を疑っているなら、紙の上に大きな円を描き、その中に辺の長さが10 ^（ - 18）mの正方形を描き、それを繰り返します。円の境界線に近づくと、辺の長さが10 ^（ - 21）mの四角形を描き始めます。

最初の手順は、質問を洗練して問題をより正確に記述することです。

Answer 3

思考の数分後に暗闇の中でだけでショット...あなたが半円形で働いていたし、最後にそれを倍増したらどう

。私は、直径の長さと半径の幅の四角形のグリッドから始め、基本的に半円を覆います。次に、各四角の四隅をすべて確認し、その座標が円の半径内にあることを確認します。これはもちろん、ある種の座標系またはグリッド上で円と四角をプロットする必要があります。私は、これは理にかなって願っています

それは私の頭の中だと、:)

EDIT明確に少し難しいようだ...：それを引き出した後 を、私はこの方法は少し微調整して働くだろうと思います。私は、直径に沿って正方形を整列させますが、それが収まるまで最初のものを下にスライドさせます。それを適切な位置にセットし、隣り合っている正方形の一番上に一直線になるようにしてください。この四角形の端に移動し、四角形の列が半径に達するまで同じ手順を繰り返します。

Answer 4

midpoint circle algorithmのようなものを使用して円をラスタライズします。塗りつぶされたピクセルの数は、あなたが円に収まることができる平方の数です。もちろん、ピクセルを塗りつぶすのではなく、ピクセルを数えているだけなので、領域の面積ではなく円の円周に比例した時間が必要です。

ラスタライズの半径を慎重に選択する必要があります。これにより、サークルの内側にあるピクセルだけがカウントされます。

編集：グリッドにサブピクセルオフセットを適用すると結果が変わる可能性があるため、正確には正しくない可能性があります。正確な解決策の出発点として役立つかもしれないので、ここで答えを残しておきます。