いくつかの三角測量作業を試した後、ポリゴンに穴があるかどうかを判断する方法についての質問に出くわしました。
既知の穴の処理方法は知っていますが、穴が存在するかどうかを判断する方法がわかりません。
例：
次の頂点があるとします。
0 ( 0, 0)
1 ( 0,20)
2 (20,20)
3 ( 0,20)
4 ( 2, 2)
5 ( 6, 2)
6 ( 6, 6)
7 ( 2, 6)
それが次のような単純なポリゴンであるかどうかを確認するにはどうすればよいですか。
または、次のような非単純/複雑なポリゴン：
使用するデータは穴の開いた多角形になる可能性があるのでお願いしますが、そのことを事前に知ることはできません。
注：ポリゴンが複雑になることはありません。ポリゴンの外側の頂点がいつ終了し、穴を構成する頂点がいつ開始するかを知る必要があります。
頂点だけからは、ポリゴンのエッジのレイアウトを推測することはできません。エッジも保持する必要があります（たとえば、頂点のペアとして）。
あなたの例では、別のグラフレイアウトは、たとえば0-1-5-6-2-3-7-4-0であり、結果のポリゴンには穴がまったく含まれていません。
エッジがある場合は、それらが円を形成するように位置合わせできます。つまり、共通の2番目/ 1番目の要素を持つエッジをグループ化します：（0、1）、（1、2）、（2、3）、（3、0）および（4、5）、（5、6）、（6、7）、（7、4）。穴がある場合、それ以上グループ化できないそのようなグループが2つ以上あります。次に、他のポイントに囲まれた領域内にあるポイントを見つけて、穴がどこにあるかを知ることができます。
隣接していない2つの線分が交差しているかどうかを確認すると、穴とポリゴンの間に分割があります。はい、このアルゴリズムはO（n 2）ですが、少し前もって知っておくと、テストの数を減らすのに役立ちます。
私はまだ評判が低すぎて答えにコメントできませんが、穴に関する数学的慣習に従うことを強くお勧めします。外側のポリゴンは反時計回りに移動し、穴は常に時計回りに移動する必要があります。MATLABはこれを逆の順序で実行しますが、ポリゴン（時計回り）と穴（反時計回り）の両方に適用されます。
ある円「B」から点を選択し、選択した点が別の円「A」の内側か外側かを判断できます。もしそうなら、あなたは穴を取得します。そうでない場合は、円Aから点を選択し、その点が円Bの内側にあるかどうかを判断します。内側にある場合は、穴を取得します。