algorithm - 2D 形状を長方形に効率的に配置します。どのようにアプローチするのですか？

Question

私は 7 つのインターネットで広範囲に検索してきましたが、役に立ちませんでした。私が必要としているものに最も近いのは、 2D のみの The Cutting Stock Problem のようです(ウィキペディアではその解決方法に関する指示が提供されていないため、これは残念です)。もう 1 つの類似の問題は、UV アンラッピングです。そこには解決策がありますが、さまざまな 3D ソフトウェアのアドオンから得られるものだけです。

長い話を短くする - 私が欲しいのはこれです:既知の幅と高さの長方形が与えられた場合、既知のサイズ (自由に回転できる) の形状 (ポリゴン) がその長方形の中にいくつ収まるかを調べなければなりません。

たとえば、T 字型のピースを選択し、同じ長方形に両方を効率的に詰め込むことができ、長方形ごとに 4 つの形状が得られます。

バウンディングボックスに基づいてそれらをタイル張りするだけでなく、3つしか収まらない場合

もちろん、これは単なる例です...そして、この特定のケースを解決するのにあまり役に立たないと思います. 私が今考えられる唯一のアプローチは、複雑さをバックトラックするか、この問題の特定のケースのみを解決することです。それで...何かアイデアはありますか？

Answer 1

tを正方形に配置することで他の回答が言ったことを検討してください。ただし、単に正方形のままにするのではなく、形状をリストに設定します。次に、True と False を使用して、ネストされたリストをシェイプとして埋めます。つまり、T シェイプの [[True,True,True],[False,True,False]] です。次に、関数を使用して図形をグリッドに配置します。結果を最適化するには、新しい形状の false の数が、以前の形状のグリッド上に既に存在する true と重複することに注意を払うトラッカーを作成します。この関数は、重なりが最も多い場所に形状を配置します。より高度な最適化を作成するには変更が必要になりますが、それはあなたが探している一般的な前提です。

Answer 2

テトリスのゲーム(あなたの問題のサブセット) に興味がある人はいますか?

これはパッキング問題として知られています。どのような形状に直面する可能性が高いかを事前に知らなければ、最良の答えを与えるアルゴリズムを考え出すことは、不可能ではないにしても非常に困難です。おそらく、ポリゴンが「適切な」ポリゴン (円、正方形、正三角形など) でない限り、ほとんどの場合、おおよその最適なソリューションを提供するヒューリスティックに落ち着かなければならないでしょう。

1 つの一般的なヒューリスティック (入力ポリゴンの形状によっては最適とは言えませんが) は、ポリゴンの周りに四角形を描画して問題を単純化し、四角形がポリゴンを覆うのに十分な大きさになるようにすることです。(下の図の例では、青い多角形の周りに赤い四角形を描いています。)

これが完了したら、その長方形を取り、その長方形をできるだけ大きな長方形に収めようとします。これにより、問題が長方形のパッキング問題に単純化され、解決が容易になり、頭を包み込むことができます。このアルゴリズムの例は、次のリンクにあります。

Rectangle 内の同一の Rectangle をパッキングするための効果的な再帰的分割アプローチ。

明らかに、問題のポリゴンが長方形と同じ形状に近くない場合、このヒューリスティックは最適ではありませんが、特にポリゴンがどのように見えるかについてあまり知識がない場合は、作業するための最小限のベースラインが得られますのように (または、ポリゴンがどのように見えるかに大きなばらつきがあります)。このアルゴリズムを使用すると、次のように大きな長方形が塗りつぶされます。

これは、中間の長方形を除いた同じ画像です。

これらの T 字型のポリゴンの場合、ヒューリスティックは可能な限り最善ではありません (実際、この提案された近似ではほとんど最悪のシナリオである可能性があります) が、他のタイプのポリゴンでは非常にうまく機能します。