頂点データとエッジデータから最小ポリゴンを取得するにはどうすればよいですか？

Question

私はe1, e2, e3, ...という名前のすべての頂点を持ち、それらのそれぞれがGPS

でコーディネートのデータはまた、私は(e1, e2), (e2, e3), ...

などのすべてのエッジ件のデータを持っていると私はすべてを取得する必要があるとしましょうこれらの頂点とエッジデータで作られたポリゴン。

。彼らはでなければはお互いに重なっているべきです。

。 最小値は、これ以上小さくならない（頂点を削除することによって）

Answer 1

あなたのすべてのエッジは交差していませんか？これはあなたの質問から明らかではありません。その場合、私があなたの質問を正しく理解すれば、正式なグラフの領域を正式に決定したいと思っています。

もしそうなら、可能なアプローチがあります（グラフが接続されていると仮定します）。各頂点に対して、時計回りの順序で隣接する頂点のリストを作成します。 1つを選択し、頂点の1つを開始頂点として選択します。今度は、エッジをたどり、開始頂点に達するまで、頂点で時計回りの次のエッジを選んでパスをトレースします。そのパスはリージョンを限定します。あなたがそれに沿って旅した方向を覚えておいてください。両方向で使用されていないエッジがある限り、このプロセスを繰り返します。