交差する長方形のセットが与えられた場合、それらの境界ポリゴンを見つけるための標準アルゴリズムはありますか? (長方形の和集合とまったく同じ領域の境界を示す多角形。) 長方形はすべて、2 つの直交軸に沿った辺で同じ方向を向いていると見なすことができます。
検索で、凸状の境界ポリゴンのアルゴリズムを見つけましたが、ここでは、長方形がカバーする領域のみを包含することを本当に好みます。これは、おそらく凹状になります。
(長方形が領域を完全に囲んでいる場合は、それを境界ポリゴン内に含めても問題ありません。)
それを行う標準的な方法があるかどうかはわかりませんが、境界ポリゴンの頂点は、長方形の角とそれらの辺が交差する点になり、長方形内にあるものを除外することがわかります。
ポイントを注文するには、セット内の 1 つのポイントから始めます。それは 2 つのエッジの交点かコーナーのどちらかであるため、いずれにしても少なくとも 2 つのエッジ上にあることが保証されます。次のポイントに到達するまで、エッジの 1 つに沿って移動するだけです。内側のポイントは既に削除しているため、内側に到達する前に常に別の頂点に到達します。
ある長方形の角が別の長方形の端に沿っている場合、角から離れた 1 つのパスが長方形の内部につながるため、注意が必要です。そのため、トレースする正しいエッジを選択する要素がいくつかあります。しかし、内部にあるために除外したポイントのリストを保持している場合、除外されたポイントに行くのは間違った方向であることがわかります。
編集 もっと明示的に言ってみましょう。
(1) すべての長方形のすべての辺から始めます。それらが交差する場所を計算し、そこでエッジを分割します。
(2) これで、セグメントのリストができました。すべてのセグメントの端点をチェックして、長方形の内側にあるかどうかを確認します。
(3) ここで、別の外部エンドポイントを持つ少なくとも 1 つのセグメントのエンドポイントである外部エンドポイントのいずれかを取得します。エンドポイントから他の外部エンドポイントまで線を引きます。
(4) その外部エンドポイントは、別の外部エンドポイントを持つ別のセグメントのエンドポイントでもある必要があります。その外部エンドポイントに線を引きます。
(5) 開始したエンドポイントに戻るまで繰り返します。
長方形の結合を計算する必要がある場合、これは一般に計算幾何学で「マージ」操作として知られているものです。これは通常、スイープ ライン アルゴリズムによって簡単に実装できます。
スイープ ライン アプローチでは、通常、スイープ ライン エンジンの実装というかなりの初期投資が必要です。それが完了すると、エンジンをすぐに使用して、入力ジオメトリに対するセット指向の操作 ("merge"、"and"、"or"、"diff" など) を簡単に実装できます。
http://en.wikipedia.org/wiki/Boolean_operations_on_polygons
一方、軸指向 (等理論的) ジオメトリのスイープ ライン エンジンの実装は、かなり簡単な作業です。これは、大量の入力を処理する必要がある場合、つまり四角形の数が比較的多い場合に最適な方法です。他の回答で言及されているさまざまなエッジトラバーサルベースのアプローチは、比較的小さな入力でのみうまく機能します。