長方形/正方形を小さな領域に分割し、各サブ領域の最大面積を強制するのは非常に簡単です。領域を辺の長さが sqrt(max_area) の領域に分割し、残り物を注意して扱うことができます。
しかし、四角形で私は困惑しています。どのコーナーの角度もわからないと仮定しましょう。また、4 つの点すべてが同じ平面上にあると仮定しましょう。また、小さな領域がすべて同じサイズである必要はありません。私が持っている唯一の要件は、個々の地域の面積が最大面積未満であることです。
これを簡単にするために使用できる特定のデータ構造はありますか?
私が見つけていないアルゴリズムはありますか？
これを行うために四分木を使用できますか? 私はツリーに非常に精通しているわけではありませんが、構造を実装する方法は知っています。
これを行うときは GIS の作業を念頭に置いていますが、それがクワッドを分割するアルゴリズムに影響を与えないことはかなり確信しています。
結果の領域が十分に小さくなるまで、クワッドを長辺で再帰的に半分に分割できます。
四角形が凸状である場合、実際には、それを 2 つの等しい面積のピースに分割して、同時に周囲の長さが等しくなるようにすることができます。これは公平なパーティショニングと呼ばれ、 The Open Problems Projectで説明されています (より多くのピースに対してはオープンですが、2 つのピースに対して解決されます)。
凸でない四角形の場合、それを 2 つの等しい部分に分割する線を見つけることは難しくありません。
私はこれがうまくいくと信じています.1つの反射頂点を通る線を通し、その領域を均等に分割するまでその頂点の周りを回転させます. 領域を 2 つの等しい半分に分割することが唯一の目的である場合、同じ方法が凸多角形に対して機能します。
一般的な問題 (任意のポリゴンの場合) は、「ポリゴンのハムサンドイッチ セクショニング」という名前で呼ばれます。実際、私はその正確なタイトルで論文を書きました。