geometry - ポリゴンの穴を削除する

Question

ポイントの配列によって決定されるポリゴンがあります。

このポリゴンはそれ自体と交差しており、ポリゴン自体にいくつかの穴を開けています。

私の質問は次のとおりです。この穴を省略して、ポリゴンの外側の点を取得するにはどうすればよいですか？

または、何が同じでおそらく簡単になるでしょう：ポイントがポリゴンの内側にあるかどうかをチェックするためのどのアルゴリズムを使用して、ポリゴンの穴のポイントを内側のポイントとして検出する必要がありますか？

前もって感謝します、

/ roger

Answer 1

まず、エッジのすべての交差を見つけ、これらの交差を頂点リストに追加し、これらの交差でエッジを分割します。次に、明らかに外部の頂点（「右端」など）である1つの頂点から開始し、アウトラインをトレースして、結果セットにエッジと頂点を追加します。アウトラインのトレースは、最後のエッジに対して最小の角度でエッジに沿って進むだけです。

Answer 2

ポリゴン内のすべてのポイントの凸包を見つけたい場合があります。

これを行うための1つのアルゴリズムは、複雑さO（nlgn）のグラハムスキャンです。コーメンから：

Let Q be the set of all points in your polygon
Graham-Scan(Q)

1  let p0 be the point in q with the minimum y-coordinate or the leftmost in case of tie
2  let (p1, p2,...,pm) be the remaining points in Q, sorted by polar angle around p0
       if more than one point shares the same polar angle, keep the farthest point

3  let S be an empty stack
4  PUSH(p0, S)
5  PUSH(p1, S)
6  PUSH(p2, S)
7  for i = 3 to m
8    while the angle formed by points NEXT_TO_TOP(S), TOP(S), and pi makes a non-left turn
9        POP(S)
10   PUSH(pi, S)
11 return S

これで、Sにはポリゴンのすべての外側のポイントが含まれます。極座標計算を行う必要がありますが、それは非常に簡単です。極順で並べ替えるには、一番下のポイントとのコタンジェント上のすべてのポイントを並べ替えます。右折をチェックするためのコードを忘れましたが、グラハムスキャンから検索するだけでインターネット上にあります。お役に立てれば！