2D 凹包を生成する効率的なアルゴリズムはありますか?
https://stackoverflow.com/questions/83593
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
GIS ファイル (都市地図) から一連の (2D) 点を取得したので、その地図の「輪郭」(その境界) を定義する多角形を生成する必要があります。その入力パラメータは、設定された点と「最大エッジ長」になります。次に、対応する (おそらく非凸の) ポリゴンを出力します。
私がこれまでに見つけた最良の解決策は、ドロネー三角形を生成し、最大エッジ長よりも長い外側のエッジを削除することでした。すべての外部エッジがそれより短い場合は、単純に内部エッジを削除して、必要なポリゴンを取得します。問題は、これには非常に時間がかかることであり、もっと良い方法はないかと考えています。
他のヒント
私たちの研究室の元学生の 1 人は、博士論文に応用可能なテクニックをいくつか使用しました。そのうちの 1 つは「アルファ シェイプ」と呼ばれるもので、次の論文で参照されていると思います。
http://www.cis.rit.edu/people/faculty/kerekes/pdfs/AIPR_2007_Gurram.pdf
この論文には、さらに参照できる参考文献がいくつか記載されています。
この答えは他の人にとっても興味深いかもしれません。を適用することもできます。 マーチングスクエアアルゴリズムのバリエーション, 、(1) 凹面ハル内に適用され、(2) その後上に適用されます (例:3) 違う 天秤 それは点の平均密度に依存します。効率的なサンプリングに使用できるグリッドを構築するには、スケールが互いの整数倍である必要があります。これにより、空のサンプル = 正方形、完全に点の「クラスター/クラウド」内にあるサンプル、およびその間にあるサンプルを迅速に見つけることができます。後者のカテゴリを使用すると、凹型ハルの一部を表すポリラインを簡単に決定できます。
このアプローチではすべてが線形であり、三角測量は必要なく、アルファ形状も使用せず、ここで説明されている商用/特許取得済みの製品とは異なります ( http://www.concavehull.com/ )
簡単な解決策は、多角形の端の周りを歩くことです。点 P0 と P1 を接続する境界に現在のエッジがあるとすると、境界上の次の点 P2 は可能な限り小さい A を持つ点になります。
H01 = bearing from P0 to P1
H12 = bearing from P1 to P2
A = fmod( H12-H01+360, 360 )
|P2-P1| <= MaxEdgeLength
次に、設定します
P0 <- P1
P1 <- P2
開始した場所に戻るまで繰り返します。
これでもまだ O(N^2) なので、ポイントリストを少し並べ替える必要があります。たとえば、都市の重心からの方向に基づいて点を並べ替えると、各反復で考慮する必要がある点のセットを制限できます。
良い質問！私はこれをまったく試していませんが、最初のショットはこの反復方法です。
- セット N (「含まれていない」) を作成し、セット内のすべての点を N に追加します。
- N から 3 つの点をランダムに選択して、初期多角形 P を形成します。N から削除します。
- 使用 いくつかのポイントインポリゴンアルゴリズム そしてNの点を見てください。N の各点について、その点が P に含まれている場合は、その点を N から削除します。N 内でまだ P に含まれていない点を見つけたら、すぐにステップ 4 に進みます。N が空になったら完了です。
- 見つけた点をAと呼びます。P 内で A に最も近い線を見つけ、その中央に A を追加します。
- ステップ3に戻る
パフォーマンスが十分に優れている限りは機能すると思います。最初の 3 つのポイントに対する適切なヒューリスティックが役に立つかもしれません。
幸運を！
このプラグインを使用して QGIS でそれを行うことができます。https://github.com/detlevn/QGIS-ConcaveHull-Plugin
データと対話するために必要な方法に応じて、おそらくここでそれがどのように行われたかを確認する価値があります。
Bing Maps V8 インタラクティブ SDK には、高度な形状操作内に凹型ハル オプションがあります。
ArcGIS 10.5.1 では、3D Analyst エクステンションには、凹包、球、包絡線、または凸包のジオメトリ タイプを備えた最小境界ボリューム ツールがあります。どのライセンス レベルでも使用できます。
ここに凹包アルゴリズムがあります。 https://github.com/mapbox/concaveman
簡単な近似解決策 (凸包にも役立ちます) は、各小さな要素の東西の北と南の境界を見つけることです。
必要な詳細度に基づいて、上限/下限の固定サイズの配列を作成します。各ポイントについて、それがどの E-W 列にあるかを計算し、その列の上限/下限を更新します。すべてのポイントを処理した後、欠落した列の上部/下部ポイントを補間できます。
また、非常に長くて薄い形状について事前に簡単なチェックを行い、NS または Ew のどちらをビン化するかを決定することも価値があります。
幅広く採用されているリファレンスとして、PostGIS は凸殻から始まり、それを陥没させます。ここで見ることができます。
