与えられたポイントとエッジのポリゴンを見つける方法は？

Question

平面上のN点とそれらを結ぶM線分を考えると、内部に他のポリゴンを含まないすべてのポリゴン（凸面または凹面）を見つけることができます。例えば

：

設立5つの多角形があります

1 - 2 - 5から6

2から5

3 - - 3 - 5

7 - 8 - 9

10 - 13 - 20 - 12 - 11

どのようにこれらのポリゴンとそれに対応する頂点とエッジを識別できますか？そして、これに対する最速の解決策は何ですか？

Answer 1

セグメントの端を頂点とし、セグメントをエッジとして構築し、次に循環を見つけるにはDFSを使用します。

同じエッジは、2-5のような複数のサイクル（ポリゴン）に属している可能性があり、サイクルを選択するには多くのバリエーションがあることに注意してください。あいまいさを除外するには、作成することができますfundamental set of cycles

編集します。コメントでwestonが気付いたように、ポリゴンには他のものが含まれている可能性があります。したがって、より幾何学的なアプローチのスケッチ：

グラフの隣接関係のリストを作成します。
極角で永遠にリストをソートします。
それの度が0の場合は1あれば、頂点とエッジを削除し、頂点を削除する最も下の頂点A.
を選択してください。
それ以外の場合は、この頂点から最小の角度でエッジEを取得します。

ウォーク、
移動Fエッジに沿ってC.
行き止まり場合にBから選択B.
頂点最も左のエッジFをペアFと頂点Cを除去し、

B.に戻ります

左手の規則を使用して、頂点Aまたは行き止まりの頂点に達するまで移動を繰り返します。歩行処理で
は次数2の頂点から出射エッジを削除するか、または使用されるそれらをマークします。