私は、交差した線分のセットを持っています。次のように私は、これらの線分の交点から生じるすべてのポリゴンを検出したい：一連の線からのポリゴン検出？
私はこの問題を解決するためのアルゴリズムを提示した紙を見つけたが、私は本当にコンピュータサイエンスないんだけど私はそれを理解できませんでした。 paperへのリンクは次のとおりです。この瞬間、私の計画は、1）すべての交差点を見つけ、2）何らかの形でこれらの交差点を使ってポリゴンを特定することです。私はブルートフォースで（1）を解くことができますが、（2）はややトリッキーです。私はRやC++のソリューションを好むだろうが、どんな言語でもできる。
線分が常に閉じた多角形のチェーンであり、何らかのエッジリストにあると仮定します。あなたが言ったように、交差点がすでに計算されている（ブルートフォースはO（n^2）時間を意味します。この場合、線分がn^2回交差するときに最適です）。
（1）からの交点をこのリストに挿入して交差する線分を分割し、交点としてマークし、この点の交差する線分すべてを参照することができます。さらに、各ラインセグメント上に2つのポリゴンが入射するので、各エッジにそれぞれの参照フィールドを追加する。次に、左端の頂点を入力し、エッジリストに沿って歩いてください。左側の入射ポリゴン（ここでは）のポリゴンナンバー1への参照を横断するすべてのエッジに追加します。交差点に到達した場合は、後で復旧するために何らかのスタックに置いてください。その点を分析し、左端のパス（交点に到達した線分とすべての外向き線分の間）を歩き続けます。ある時点で出発点に達し、最初の単純なポリゴンが閉じられます。
ここで、スタックから最初の交点を取得します。そこに開始/終了する偶数の線分がなければなりません。 （まだ）参照されている入射ポリゴンが最大1つある線分を見つけ、それをポリゴン2番の開始線として使用します。これまでと同じ方法でチェーンに沿って歩くことができます。 （線分の右の入射ポリゴンを参照する場合は、交差点を一番右に回します。）スタックが空でなければ、あなたは完了です。
編集：解決策をもう一度見た後、私はこれを見つけましたimplementation from Dan Sunday。すでに実装されているので、それがより有用であると私は推測します。
Alfredo Ferreiraは、重複するラインのセットからポリゴンを検出するためのC++コードを開発しました。コードはこちらのページでご確認いただけます。http://3dorus.ist.utl.pt/tools/PolygonDetector.html 希望の方はこちら
プログラマーを雇いたいと思うような音がします。 –
rgeosパッケージから 'gIntersect'を使うことができるかもしれません。これは、空間オブジェクトである限り、行を切り取るためです。おそらくSpatialLinesDataFrameのように、何が他の側から出るのかは分かりません。 – Badger