algorithm - n個の長方形で多角形を近似する方法は?

Question

最大のカバレッジを提供する n 個の重なり合わない長方形で指定されたポリゴンを近似できるアルゴリズムはありますか? 最大カバレッジとは、長方形領域の合計が最大化されることを意味します。長方形は必ずしも同じサイズではありません。

私が扱っているポリゴンは凸面です。正確な解決策を見つけるのが難しい/費用がかかる場合（私はそうなると予想しています）、単純で優れたヒューリスティックも歓迎します。

編集私は常に多角形の内側にある長方形で多角形を近似することを考えていましたが、完全に多角形の内側にない長方形のソリューションも問題ありません。その場合、面積の最大化は面積の最小化になります。

編集 2これらの四角形は直交する四角形、つまり軸に沿っていることを忘れていました。

Answer 1

1. 処理するポリゴン Q のキューを作成する

2. 初期ポリゴンを Q に追加する

3. Q から多角形 P を削除する

4. P の最長辺 A を見つける
5. A が X 軸上になるように P を回転させる
6. P が三角形の場合、A の中心にある垂線で分割します。
7. G と H の 2 つの半分を Q に追加し、3 に進みます。
8. (現在、P には 4 つ以上の辺があります)
9. X および/または Y が急性の場合:

10. P、A の次に長い辺を取り、5 に進みます

11 . A から赤い四角形を投影します。P、B、C と交差する 2 つの点を見つけます。

12 . 長い方 (B) を選択し、緑色の長方形を完成させます

13 . 残りの数字 (D、E、および F) を Q に追加します。

14 . 後藤3

Answer 2

最初のアイデアですが、他の人がそれを改善できるかもしれません。

• 多角形の内側のどこかに正方形を配置し、エッジからできるだけ離します。
• 繰り返し 1.) 成長させ、2.) 移動させて回転させ、エッジからの距離を最大化します。これ以上伸びなくなるまで
• 配置された四角形のエッジをポリゴンのエッジと見なしながら、最初から開始します。