複数のポリゴンの面積を計算する方法は？

Question

私は数日前にこの質問を投稿しました：How to intersect multiple polygons?。今私は推奨されたスイープラインアルゴリズムを実装しました（具体的には、Martinez、Rueda、Feitoのものです）。

結果は重複しないポリゴンのセットです。しかし、これらのポリゴンは互いに（穴）を含むことができ、境界（穴または島ポリゴン）に接触することができます。

私が何を意味するかの写真：私はこれがすべての特殊なケースをカバーするべきだと思う

。交点はスイープラインアルゴリズムによって処理されます。

ここでは、ポリゴンの領域（灰色の部分）が必要です。私の最初のアイデアは、ポリゴンをポリゴンで追加し、それらが互いに含まれているかどうかをチェックし、必要なポリゴンのみを選択するためのインテリジェントな選択メカニズムを使用することでした。しかし、これはいくつかのO（n^2）アルゴリズムを生成する。各ポリゴンを処理するためには、すべてのエッジを既に処理されているすべてのエッジと比較する必要がある。

いいえ。あなたは私に合計面積を計算するヒントを教えてもらえますか？

Answer 1

標準的な頂点の順序は、ポリゴンの場合は反時計回りで、穴の場合は時計回りです。このコンベンションを使用してデータを保存する場合は、標準polygon area calculation methodの領域を計算するだけです。穴の領域は負の値になります。

これ以外の順序でご使用の場合は問題があります。今すぐ改善する。