最小限の長方形で単純な凹多角形をカバーするのに疲れています。私の長方形は任意の長さにすることができますが、最大幅があり、ポリゴンが鋭角になることはありません。
私は、凹多角形を三角形に分解して、各三角形の境界を最小限に抑えた最小の重なり合う長方形のセットを生成し、それらの長方形をより大きな長方形にマージすることを考えました。ただし、これはポリゴンのエッジの小さなノッチでは機能しないと思います。それらのノッチの反射頂点によって作成された三角形は、間違った長方形を作成します。ノッチにまたがる/無視する長方形を探しています。
計算幾何学については何も知らないので、どうやって質問を始めたらいいのかよくわかりません。
似ているが、必要なものではない他の投稿を見つけました。
- ポリゴンを最小量の長方形と三角形に分割します
- 最小数の正方形で任意のポリゴンをカバーする
- 最大数の点をカバーするように$k$の長方形を見つけます
- 長方形のセットをカバーするために最も少ない長方形を見つけるためのアルゴリズム
いくつかの例：黒が入力です。赤は許容可能な出力です。
別の例：2番目の出力が優先されます。ただし、両方の出力を生成し、別の要素を使用して優先度を決定することはおそらく必要であり、このアルゴリズムの責任ではありません。
曲線を模倣するポリゴンは非常にまれです。このシナリオでは、長方形の領域の多くが無駄になります。ただし、各長方形は最大幅の制約に従うため、これは許容されます。
また、この記事は私が必要としているものに近いことがわかりました。
- パウル・ヤコブ、ダニエラ・マリネスク、クリスティーナ・ルカによる長方形の作品で覆う
おそらくもっと良い質問は、「凹多角形の長方形のような部分をどのように識別できるか」です。
これは、目的の実装を示す画像です。
グリーンは実際の材料使用量です。赤い長方形がレイアウトです。青はポリゴン全体のMBRです。私は小さなMBRを取得して、それらを埋めることを試みるべきだと考えています。ポリゴンの中央で終わる左上隅の2〜3個の緑色の長方形は高価です。それが私が最小化したいものです。緑の長方形には最小と最大の幅と高さがありますが、領域をカバーするために必要な数の行と列を使用できます。繰り返しますが、入力にまたがらない長方形の数を最小限に抑える必要があります。緑の長方形の形を変更して、非常に高価な小さな場所に合わせることができます。言い換えれば、できるだけ多くの長方形をできるだけ多くスパンすることが理想的です。
たぶん私は単にこのような長方形の領域を識別しようとしているはずです：
または、おそらくより良いアプローチは、MBRの代わりに最大の内接長方形を使用することです。最大の内接長方形が元のポリゴンとエッジを共有していない領域が残るまで、長方形を使用してポリゴンを継続的に切り詰めることができました。残りの領域は、ヒューリスティックなアプローチで処理する必要があります。
私は会社のエンジニアリング部門と製造部門と協力して、この問題をより明確にするために取り組んできました。私はまだ確認を待っていますが、最大の内接長方形のセットを返すアルゴリズムが機能すると考えています。形状を完全にカバーするわけではありませんが、非直交領域を一部のヒューリスティックに任せながら、直交領域を優先します。唯一のトリックは、これらの直交領域を最大化することです。