gis - ポリゴンを既存の領域に分割/分割する方法は?

Question

各領域に意味のある要素がばらばらになるように、ポリゴンを領域 (より大きなポリゴン) に「分割」/サブセット化するという問題に直面しています。

たとえば、次のリージョン/ポリゴンがあります。ある時点で、1 つの領域 (ここでは R1 としましょう) の形状しかわかりません。L3 が R1 に属することは明らかです。L1、L2、P1 はどうですか？それらの周りにバウンディング ボックスを作成し、南東座標 (minX と minY) が R1 に属しているかどうかを確認することを考えました。このように、L1 は R2 と交差していなくても、R2 に属します。

この種のアルゴリズムについて何を調べる必要があるか、またはこの空間分離の問題を解決する方法について具体的な考えはありますか?

Answer 1

リージョンとポリゴンがすべてポリゴン (頂点の離散シーケンス) として記述されている場合は、利用可能なポリゴン クリッピング手法を利用できます。

特に、Sutherland-Hodgman法とWeiler-Atherton法を見てください。

ウィンドウの前処理が許可されている場合 (同じウィンドウに対象となるポリゴンが多数ある場合)、スキャンライン手法を使用して、ある程度の最適化が可能です。これはもう少し洗練されたものです。

線分エンティティの場合は少し簡単です。