不規則な多角形を長方形と直角三角形に縮小するパッキング アルゴリズムを探しています。アルゴリズムは、そのような形状をできるだけ少なく使用しようとする必要があり、比較的簡単に実装できる必要があります (課題の難しさを考えると)。また、可能であれば、三角形よりも長方形を優先する必要があります。
可能であれば、この質問への回答は、提案されたアルゴリズムで使用される一般的なヒューリスティックを説明する必要があります。
これは、頂点が 100 未満の不規則なポリゴンの場合、確定的な時間で実行されるはずです。
目標は、素人向けの不規則な多角形の「賢明な」内訳を作成することです。
ソリューションに適用される最初のヒューリスティックは、多角形が規則的か不規則的かを決定します。正多角形の場合、正多角形に関する私の同様の投稿で概説されているアプローチを使用します:正多角形の効率的なパッキング アルゴリズム
これが最適な答えになるかどうかはわかりませんが、少なくとも答えは得られます。
記入すべき詳細がたくさんあることは承知していますが、ドロネー三角形分割から始めるのがおそらく正しい方法だと思います。平面内の Delaunay 三角形分割は効率的に計算でき、一般的に非常に「自然」に見えます。
追加するために編集:私たちはアドホックなヒューリスティックビルにいるので、他の回答で議論されている貪欲なアルゴリズムに加えて、ある種の分割統治戦略も検討する必要があります。例のように形状が凸でない場合は、反射角をできるだけ二等分するように、反射頂点から別の頂点まで繰り返しカットすることで、凸形状に分割します。形状を凸状のピースに分割したら、次に凸状のピースを素敵な「ベース」を持つピース、つまり少なくとも 1 つの側面の端に 2 つの鋭角または直角があるピースに分割することを検討します。ピースにそのような「ベース」がない場合は、ピースの直径に沿って 2 つに分割し、それぞれ「ベース」を持つ 2 つの新しいピースを取得できるはずです (と思います)。これにより、台形のような凸多角形を扱う問題が軽減され、そこから貪欲なアルゴリズムがうまくいくはずです。このアルゴリズムは、台形のピースに到達するまで、かなり自然な方法で元の形状を細分化すると思います。
本当に楽しい問題のように聞こえるので、これで遊ぶ時間があればいいのにと思います!
私の最初の考え (上の図を見て) は、同じ方向を向いている 2 つの隣接する直角を探すことです。長方形が役立つすべてのケースをキャッチできるわけではありませんが、ユーザーの観点からは明らかなケースです (外側の四角い角 = これは長方形であるべきです)。
隣接する直角のペアを見つけたら、短い方の脚の長さを取ると、長方形が 1 つできます。これをポリゴンの左からタイルに引き、繰り返します。削除する明らかな外部長方形がなくなったら、通常のタイリングを行います (Peter の答えは素晴らしいですね)。
免責事項：私はこれについての専門家ではなく、試したこともありません...
