algorithm - 逆長方形パッキング

Question

私は、正方形を組み合わせた接続された形状を持っています。たとえば、方眼紙を取り、最初で終わり、それ自体と交差しない既存の線に沿って線を引きます。

ここでの目標は、この形状をできるだけ少なく、重なり合わない長方形で埋めるアルゴリズム（ブルートフォースではない）を見つけることです。

私は最適な解決策を探しています。画像に見られるように、素朴な欲張りアプローチ（最大の長方形を取る）は機能しません。

（最適な）

（よく深い）

私のシナリオは頂点の削減ですが、他のユースケースもあると確信しています。

注：この問題は基本的なようですが、他の場所で解決策を見つけることができませんでした。また、この問題はNP困難ですか？

編集：私のシナリオでは、重なり合わない三角形をできるだけ少なくして形状を塗りつぶすと、さらに良い結果が得られることに気づきました。

score 2 · Accepted Answer

最初の質問をして以来、私はこれを研究するのに多くの時間を費やしてきました。最初の問題（形状を長方形で最適に塗りつぶす）については、「最適な欲張りメッシュ」というヘッダーの下に解決策を記述しました。

複雑さは、実際には、穴のないポリゴンを最適に三角形分割する場合よりも優れています（高速です）。最も遅い部分はホップクロフト・カープアルゴリズムです。

形状をポリゴンとして扱うことについても、リンクされたブログ投稿で説明されています。穴も検討していることに注意してください。

score 0 · Accepted Answer

最初の問題は、三角形の問題よりも難しいです。三角形については、のアルゴリズムを参照してください

余分な頂点なしでそれを行うことができます。

2 に答える 2