algorithm - 円にいくつの正方形を詰めることができますか？

Question

サイズa × aの正方形を半径Rの円にいくつ詰めることができますか？

解決策は必要ありません。ある種の最初のアイデアが必要です。

Answer 1

こんなに長い答えを書いてしまったことをお詫びします。私のアプローチは、理論上の最大値と保証された最小値から始めることです。問題に取り組むときは、これらの値を使用して、使用するアルゴリズムがどれだけ優れているかを判断できます。より良い最小値を考えることができる場合は、代わりにそれを使用できます。

円の面積を使用するだけで、問題の上限を定義できます。

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

ここで、Lはパックする正方形の幅または高さ、rは正方形をパックする円の半径です。これは上限であると確信しています。これは、a）個別の数のボックスが必要であり、b）円の面積よりも多くのスペースを占有できないためです。（正式な証明は、これより1つ多いボックスがあると仮定すると、ボックスの面積の合計が円の面積よりも大きくなるという線に沿って機能します）。

したがって、上限があれば、すべての円に存在する任意の解を取り、それを最小解と呼ぶことができます。

それでは、円の内側に収まる最大の正方形を見て、すべての円に存在する解決策を考えてみましょう。

円の内側に収めることができる最大の正方形は、周囲に4つの点があり、幅と長さはsqrt(2) * radius次のとおりです（ピタゴラスの定理を使用し、短い方のエッジの長さには半径を使用します）

したがって、最初に注意することは、sqrt(2) * radiusが正方形の寸法よりも小さい場合、円に正方形を収めることはできないということです。結局のところ、これはあなたが収めることができる最大の正方形だからです。

これで、指定したLを使用して、この大きな正方形を通常の正方形のグリッドに分割する簡単な計算を実行できます。これにより、問題に対する少なくとも1つの解決策が得られます。したがって、この最大の正方形の内側に正方形のグリッドがあります。このグリッドの1行に収めることができる正方形の数は次のとおりです。

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

したがって、この最小限のソリューションは、少なくとも

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

円の内側の正方形の数。

ですから、迷子になった場合に備えて、私がしたのは、円の中に収まる最大の正方形を取り、その中の通常のグリッドにできるだけ多くの正方形を詰めて、少なくとも1つの解決策を与えることでした。

この段階で0の答えが得られた場合、円の中に正方形を収めることはできません。

理論上の最大値と絶対最小値を備えたので、正方形をパッキングするために好きな種類のヒューリスティックアルゴリズムを試すことができます。単純なアルゴリズムは、円を行に分割し、各行にできるだけ多くの正方形を収めることです。次に、この最小値をガイドラインとして使用して、より良いソリューションを考え出すことができます。より良い解決策を探すためにより多くの処理能力を費やしたい場合は、理論を最良にどれだけ近づけるかについてのガイドラインとして理論を使用します。

そして、これを気にするなら、私が特定した最小アルゴリズムをカバーする最大および最小の理論上のパーセンテージがあなたに与えるものを理解することができます。最大の正方形は常に一定の比率をカバーします（円周率/ 4または円の内部面積の約78.5％だと思います）。したがって、理論上の最大最小値は78.5％のカバーです。そして、最小の自明でない（つまり、ゼロ以外の）理論上の最小値は、最大の正方形の内側に1つの正方形しか収まらない場合です。これは、パッキングする正方形が、最大の正方形の幅と高さの半分より1大きい場合に発生します。円に収まります。基本的に、1つのパックされた正方形で内側の正方形の25％強を占めます。つまり、約20％のカバーが得られます。

Answer 2

中点円アルゴリズムなどを使用して円をラスタライズします。塗りつぶされたピクセルの数は、円に収めることができる正方形の数です。もちろん、実際にはピクセルを塗りつぶしているのではなく、数えているだけなので、これには、円の面積ではなく、円周に比例した時間がかかるはずです。

厳密に円の内側にあるピクセルのみをカウントするように、ラスタライズの半径を慎重に選択する必要があります。

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

Answer 3

数分間考えた後、暗闇の中でのショット...

円の半分で作業し、最後に2倍にした場合はどうなりますか。直径の長さと半径の幅の正方形のグリッドから始め、基本的に半円を覆います。次に、各正方形の4つの角すべてをチェックし、それらの座標が円の半径内にあることを確認します。もちろん、これには、ある種の座標系またはグリッド上に円と正方形をプロットする必要があります。

私はこれが理にかなっていることを願っています...それは私の頭の中にあり、明確にするのは少し難しいようです:)

編集：それを引き出した後、私はこの方法が少し調整することでうまくいくと思います。直径に沿って正方形を並べますが、最初の正方形をぴったり合うまで下にスライドさせます。それを所定の位置にセットし、それらが収まらなくなるまで、その隣に正方形を並べ始めます。この正方形の線の端に移動し、正方形の列が半径に達するまで同じ手順を繰り返します。

Answer 4

正方形は好きなだけ円に詰めることができます。この記述に疑問がある場合は、一枚の紙に大きな円を描き、その中に一辺の長さが10 ^（-18）mの正方形を描き、繰り返します。円の境界に近づいたら、一辺の長さが10 ^（-21）mの正方形を描き始めます。

したがって、最初のステップは、質問を洗練し、問題をより正確に述べることでなければなりません。