15

誰かが私の特定のポリゴンパッキング問題に適合する最良のアルゴリズム/ヒューリスティックを教えてくれるかどうか疑問に思いました。境界として単一のポリゴン（凸面または凹面にも穴が含まれる場合があります）と単一の「塗りつぶし」ポリゴン（凸面または凹面の場合もあり、穴が含まれない）が与えられ、指定された数で境界ポリゴンを塗りつぶす必要があります塗りつぶしポリゴンの。（私は2Dで作業しています）。

私が見つけたポリゴンパッキングヒューリスティックの多くは、境界および/または塗りつぶしポリゴンが長方形であり、塗りつぶしポリゴンのサイズが異なることを前提としています。私の場合、塗りつぶしポリゴンは長方形ではないかもしれませんが、すべてがまったく同じになります。

多分これは特定のタイプのパッキング問題ですか？誰かがこのタイプのポリゴンパッキングの定義を持っているなら、私は喜んでグーグルで離れますが、これまでのところ、非常に役立つのに十分似ているものは見つかりませんでした。

ありがとう。

4

4 に答える 4

4

あなたが尋ねる質問は非常に難しいです。これを概観すると、境界のあるポリゴンの内部を重なり合わないディスクでパッキングする（はるかに）単純なケースはすでに困難であり、ディスクは可能な限り最も単純な「パッキング形状」です（他の形状を使用する必要があります）。サイズと中心位置だけでなく、向きも考慮してください）。

実際、任意の整数Nと任意の境界のある多角形領域（ユークリッド平面内）について、「最適」（多角形内部の最大の割合をカバーするという意味で）を決定することは、計算幾何学の未解決の問題だと思います。）N個の内接する重なり合わないディスクのパッキング。各ディスクの半径と中心位置を自由に選択できます。「最良の」答えは、特定の特殊な多角形（長方形、円、三角形など）で知られていると思いますが、任意の形状の場合、最良の「ヒューリスティック」はおそらく次のとおりです。

  1. Nでシェイプカウンターを開始します。
  2. 他のパッキング形状と重なることなく、ポリゴン境界の内側に完全に収まる最大の「パッキング形状」を追加します。
  3. シェイプカウンターをデクリメントします。
  4. シェイプカウンターが0より大きい場合は、手順2に進みます。

私は「おそらく」と言います。なぜなら、「最初に大きい」が、限られたスペースに物を詰め込むための最良の方法であるとは限らないからです。ビンパッキング問題とナップサック問題について読むことで、その特定の狂気の味を掘り下げることができます。

編集：ステップ2自体は難しいです。合理的な戦略は、ポリゴンの内部の任意の点を中心として選択し、ディスクが境界または別のディスク（または両方）に接触するまでディスクを「膨張」させてから、膨張を続けながらディスクを「スライド」させることです。境界や他のディスクとの少なくとも2つの接触点で、「トラップ」されるまで他のディスクと重なることなく、境界の内側に留まるようにします。しかし、この「スライディングプロセス」を形式化するのは簡単ではありません。また、スライドプロセスを正しく行ったとしても、この戦略では、最大の「書き込み可能なディスク」が見つかるとは限りません。「ローカルで最大の」ディスクは、内部の「ローブ」に閉じ込められる可能性があります。狭い「首」

于 2011-09-08T03:46:37.943 に答える
3

返信ありがとうございます。私の要件は、方向を処理する必要がないことで問題をさらに単純化でき、塗りつぶし要素の境界ボックスだけを実際に心配することでさらに単純化できるようなものでした。これらの 2 つの単純化により、問題ははるかに簡単になり、空間ハッシュ グリッドと組み合わせてストライプのような塗りつぶしアルゴリズムを使用しました (塗りつぶしが許可されていない既存の要素があったため)。

このアプローチでは、単純に塗りつぶし領域をストライプに分割し、空間ハッシュ グリッドを作成して塗りつぶし領域内の既存の要素を登録しました。塗りつぶし領域を登録するために 2 番目の空間ハッシュ グリッドを作成しました (ストライプが境界領域内にあるとは限らないため、グリッドをクエリするだけで、塗りつぶし要素が塗りつぶし領域内にあるかどうかのチェックが少し速くなりました。塗りつぶし要素が配置されるすべてのグリッドがいっぱいで、塗りつぶし要素が塗りつぶし領域内にあることがわかりました)。その後、各ストライプを繰り返し処理し、ハッシュ グリッドが許可する場所に塗りつぶし要素を配置しました。これは確かに最適な解決策ではありませんが、私の特定の状況に必要なすべてであり、非常に高速でした. ここから空間ハッシュ グリッドの作成に関する必要な情報を見つけました. この記事から、ストライプで塗りつぶすというアイデアを思いつきました。

于 2011-09-08T16:36:45.817 に答える
1

このタイプの問題は、幾何学的に解くのが非常に複雑です。

100% 最適なソリューションではなく、適切なソリューションを受け入れることができる場合は、ラスター アルゴリズムで解決できます。

境界ポリゴンを 1 つのメモリ内イメージに描画 (ラスタライズ) し、塗りつぶしポリゴンを別のメモリ内イメージに描画 (ラスタライズ) します。

次に、塗りつぶしポリゴンのさまざまな (X、Y) オフセットを使用して 2 つの画像を重ね合わせ、ピクセル値を確認することで、塗りつぶしポリゴンが境界ポリゴンに収まる場所をより簡単に検索できます。

塗りつぶしポリゴンが収まる場所が見つかったら、境界ポリゴンのピクセルをクリアし、塗りつぶしポリゴンが収まる場所がなくなるまで繰り返します。

Google 検索のキーワードは次のとおりです。ラスタライゼーション、オーバーレイ、アルゴリズム

于 2011-08-31T11:25:25.800 に答える