2D空間に長方形と任意の形状のセットがあります。形状は必ずしも多角形（円の場合もあります）である必要はなく、長方形の幅と高さは異なります。タスクは、可能な限り長方形で形状を近似することです。長方形の寸法を変更することはできませんが、回転は許可されています。
パッキング問題やカバーリングの問題と非常によく似ていますが、カバーエリアは長方形ではありません...
NPの問題だと思います。それを解決するための優れたヒューリスティックを示す論文がいくつかあるはずですが、何をグーグルで検索すればよいかわかりません。どこから始めればいいですか？
更新： 1つのアイデアが頭に浮かびましたが、調査する価値があるかどうかはわかりません。境界形状を水で満たされた物理的な型と見なすとどうなりますか。各長方形は、サイズが正に帯電した粒子と見なされます。次に、最小の長方形をドロップします。次に、ランダムなポイントでサイズで次をドロップします。長方形が近すぎると、互いに反発します。すべてが使用されるまで、長方形を追加し続けます。この方法は機能しますか？
パッキングと自動レイアウト生成アルゴリズムを探すことができると思います。自動VLSIレイアウト生成アルゴリズムは、テキスタイルレイアウトの質問と同じように、同様のものを必要とする場合があります...
この論文Hegedüs：多角形を長方形で覆うためのアルゴリズムは、同様の問題に対処しているようです。そして、この論文は1982年のものなので、これを引用している論文を見るのは興味深いかもしれません。さらに、この会議はこれに関連する研究の問題について話し合っているように思われるので、このアイデアを研究するキーワードや名前の出発点になるかもしれません。
計算幾何学の研究にあなたの特定の問題のためのアルゴリズムがあるかどうか、またはこれらのアルゴリズムが実装するのに十分簡単/実用的であるかどうかはわかりません。これが、前の作品を調べられずにやらなければならなかった場合のアプローチです。これは単なる方向性であり、解決策ではありません...
最適化問題として定式化します。選択した長方形（はいまたはいいえ）の離散変数と連続変数（三角形の位置と方向）があります。これで、2つの独立した最適化を設定できます。長方形を選択する個別の最適化。長方形が与えられると、位置と方向を最適化する連続体。これら2つの最適化をインターリーブします。もちろん、困難は最適化の定式化と、いくつかの奇妙な構成（極小値）でスタックしないようにエラーエネルギーを設計することにあります。標準の最適化ライブラリを使用できるように、最小二乗問題として連続を取得しようとします。
この問題は、遺伝的アルゴリズムや進化戦略アルゴリズムで解くのに適していると思います。私はある種の進化戦略アルゴリズムの助けを借りて、同様のボックスパッキング問題を実行しました。私のブログでこれをチェックしてください。
したがって、このようなアプローチを使用する場合は、染色体ボックスにエンコードします。
次に、そのような適応度関数を最小化してみてください-
y = w1 * box_intersection_area + w2 * box_area_out_of_shape + w3 * average_circle_radius_in_free_space
因子の重要性に影響を与えるなど、重みw1、w2、w3を選択します。遺伝的アルゴリズムが部分的な解決策を見つけるとき-まだ互いに重なり合っているか、形が崩れているボックスを削除します-そしてあなたは少なくとも合法的な（しかし必ずしも最適ではない）解決策を持っているでしょう。
この興味深い問題で頑張ってください！
それは確かにNP困難であり、ハイテクアプリケーションを備えているため、公開された論文は言うまでもなく、合理的に効率的な近似戦略は特許にもありません。
限られた予算でできる最善のことは、問題を制限することから始めることです。すべての長方形が完全に同じであると想定します。コア分割に合わせて効率的に事前にパックできるため、標準の長方形のバイナリサブディビジョンであるすべての長方形も許可されると想定します。追加のポイントについては、コアの長方形を接着して、実質的に異なる比率でいくつかの大きな形状をカバーするためのいくつかの固定スキーマを形成することもできます。残りの部分（事前パッキングと接着スキーマ）が同じである限り、標準の長方形/セルの寸法を変更できると仮定します。これにより、指定された長方形に基づいてコア長方形のおおよそのサイズを決定するパラメーターが得られます。
これで、アスペクト比を試して、このような限られたシステムで保証できるエラーを概算できます。最初の反復では、単純なサブディビジョンスキーマで50％のエラーが発生する可能性があると想定し、スキーマを変更してエラーを減らしますが、事前パッキングの漸近的な複雑さを増すことはありません。1日の終わりには、事前に計算され、現在は固定されているグリッドとバイナリのサブディビジョンに、指定された長方形を常に割り当てるだけです。つまり、レイアウトやバックトラックをまったく実行しようとはしていません。最初の概算に常に満足しています。グリッドに収まります。
スキーマとうまく調和する長方形のクラスを定義する作業を行います-これもプロセス全体を反転させておくためです-与えられたものに実際に適合させようとはしていません-うまく固めるために与えられなければならないものを定義しています-次に、近似値であるため、残りをエラーとしてパントします。
次に、もう少し多くのことを試みることができますが、それ以上のことはできません。バックトラックに陥ったり、任意の小さなエラーを釘付けにしたりすると、指数関数的になります。
研究施設にいて、スーパーコンピューターの時間を得ることができる場合は、病理学的な組み合わせで一連の徹底的な検索を実行して、最適なパッキングがどのように見えるかを確認し、さらにいくつかのサブディビジョンスキーマを導出できるかどうかを確認します。長方形セットのクラス。
最初の2年間または研究にはそれで十分なはずです:-)