複数の重なり合うポリゴンで覆われた共通領域を計算する方法を探しています。多角形はすべて直角です。これにより作業が容易になります。
たとえば、次のようになります。
BBBBBB BBBBBB AAA---BB AAA---BB あああああ AA--AA AA--AA LL LL ルルルル ルルルル
A、B、L でカバーされる共通の領域を見つけたいと思います。これは次のようになります: B = 5x4 = 20 + A = 6x5 = 30 + L = 4x2 + 6x2 = 20 = 70 マイナス重複領域: - 10 = 60 (すべてのポリゴンでカバーされる共通領域)
3 つ以上のポリゴンが同じ領域を占める状況に対応できる必要があります。x/y座標の配列の配列を入力として取ることができる、これに適したアルゴリズムはありますか? (サンプル Java ソース コードは大歓迎です)。
このような領域を計算する従来の方法は、スイープ アルゴリズムを使用することです。長方形の単純なケースでのアルゴリズムの説明を得るために、重複する長方形の領域の質問を見ることができます。
次に、ポリゴンを長方形に分解するか、スイープ中にこの分解が暗黙的に行われるようにスイープ アルゴリズムを適応させることができます。
これを行う別の方法は、周回積分を使用して面積を計算することです。面積の周囲を歩き回り、グリーンの定理と数値求積法を使用して面積を計算します。簡単に簡単。
ポリゴンを2Dintまたはbool配列として表すことができる場合（ij番目のスロットがポリゴンに含まれている場合はA [i] [j] == 1、それ以外の場合は0）、より大きな2Dでポリゴンの結合を作成できます。バウンディング」配列。
アルゴリズムは次のようなものです。
// get your polygons, each represented by a 2D array as described above
// create a "bounding" array B that can contain all polygons (watch out for
// sparsely spaced polygons in which case B could be large)
// populate B s.t. B[i][j] == 1 if ijth slot is contained in
// the union of all polygons
// count all slots in B where B[i][j] == 1 (this will be the "common" area)
実行時間とスペースの要件について考える：すべてのポリゴンのすべてのスロットをトラバースする必要があります。バウンディング配列Bのすべてのスロットをトラバースする必要があります。スペースの最悪のケースは、すべてのポリゴンの交点が空の場合です（おそらくそれらはまばらに配置されています）。最初に空の交差点のケースを確認する価値があるかもしれません...次に、交差点が空の場合、「共通」領域は個々の領域の合計にすぎません。