2 つの任意のポリゴンをパッキングする際に問題があります。つまり、2 つの任意のポリゴンがあります。この多角形に外接する長方形の面積が最小の場合、この多角形のそのような配置を見つける必要があります (回転と移動を行うことができます)。
私は、これが NP 完全問題であることを知っています。この問題を解決するための効率的なアルゴリズムを選択したいと考えています。No-Fit-Polygon アプローチを探しています。しかし、任意の 2 つのポリゴンの NFP を見つけるための単純で明確なアルゴリズムはどこにも見つかりませんでした。
パラメータスペースは大きすぎないようで、テストも悪くありません。1 つの多角形を固定すると、もう一方の多角形を x 軸に沿って X だけシフトし、y 軸に沿って Y だけシフトし、r だけ回転させることができます。
X と Y の対象領域は、ポリゴンのバウンディング ボックスを見つけることで決定できます。もちろん、r は ～ 360 度です。
では、X、Y、r の興味深い範囲で等間隔の一連の間隔を試してみてはどうでしょうか。おそらく、これらの次元で興味深い点を見つけたら、より詳細な検索を行うことができます。
NP完全な場合は、アルゴリズムではなくヒューリスティックが必要です。可能な側面の各ペアを一緒に配置してから、一方を他方に対してスライドさせて領域を最小限に抑えます。もちろん、それらが凹面である場合は重なり合う可能性があります。