66

GISファイル（都市地図）からの（2D）ポイントのセットがあるので、そのマップ（その境界）の「等高線」を定義するポリゴンを生成する必要があります。その入力パラメータは、設定されたポイントと「最大エッジ長」になります。次に、対応する（おそらく非凸の）ポリゴンを出力します。

これまでに見つけた最善の解決策は、ドロネー三角形を生成してから、最大エッジ長よりも長い外部エッジを削除することでした。すべての外部エッジがそれよりも短くなった後、内部エッジを削除して、必要なポリゴンを取得します。問題は、これは非常に時間がかかることであり、もっと良い方法があるかどうか疑問に思っています。

4

10 に答える 10

10

私たちの研究室の元学生の 1 人は、博士論文にいくつかの適用可能な手法を使用しました。それらの1つは「アルファ形状」と呼ばれ、次の論文で参照されていると思います。

http://www.cis.rit.edu/people/faculty/kerekes/pdfs/AIPR_2007_Gurram.pdf

その論文は、あなたが従うことができるいくつかのさらなる参考文献を提供します.

于 2008-09-17T14:24:59.340 に答える
4

この論文では、平面内の一連の点の形状を特徴付けるための単純な多角形の効率的な生成について説明し、アルゴリズムを提供します。同じアルゴリズムを利用した Java アプレットもここにあります。

于 2014-02-15T10:19:45.437 に答える
2

ここにいる人たちは、「ポイントの数に対してほぼ線形」に動作するポイントのセットの凹包を決定するための最近接アプローチを開発したと主張しています。悲しいことに、彼らの論文は非常によく守られているようで、あなたは彼らにそれを求める必要があります.

上記を含む優れた参考文献のセットを次に示します。これにより、より良いアプローチを見つけることができます。

于 2008-09-17T14:39:44.453 に答える
2

答えは他の誰かにとってまだ興味深いかもしれません:マーチング スクエア アルゴリズムのバリエーションを適用し、 (1) 凹包内に適用し、(2) 次に (たとえば 3)平均密度に依存するさまざまなスケールに適用することができます。ポイント。効率的なサンプリングに使用できるグリッドを構築するなど、スケールは互いに int 倍数である必要があります。これにより、空のサンプル = 正方形、ポイントの「クラスター/クラウド」内に完全にあるサンプル、およびその間にあるサンプルをすばやく見つけることができます。後者のカテゴリは、凹包の一部を表すポリラインを簡単に決定するために使用できます。

このアプローチではすべてが線形であり、三角測量は必要なく、アルファ形状を使用せず、ここ ( http://www.concavehull.com/ )で説明されている商用/特許取得済みの製品とは異なります。

于 2012-01-29T15:40:02.747 に答える
1

簡単な近似解 (凸包にも役立ちます) は、東西の小さな要素ごとに北と南の境界を見つけることです。

必要な詳細に基づいて、上限/下限の固定サイズの配列を作成します。各ポイントについて、どの EW 列にあるかを計算し、その列の上限/下限を更新します。すべてのポイントを処理した後、見逃した列の上下のポイントを補間できます。

また、非常に長くて薄い形状を事前に簡単にチェックし、NS または Ew をビンに入れるかどうかを決定することも価値があります。

于 2008-09-17T14:25:20.837 に答える
1

このプラグインを使用して QGIS で実行できます。 https://github.com/detlevn/QGIS-ConcaveHull-Plugin

データとやり取りするために必要な方法に応じて、ここでどのように行われたかを確認する価値があるでしょう。

于 2016-02-18T23:01:09.123 に答える
1

良い質問！私はこれをまったく試していませんが、最初のショットは次の反復的な方法です。

  1. セット N (「含まない」) を作成し、セット内のすべてのポイントを N に追加します。
  2. N からランダムに 3 つのポイントを選択して、最初のポリゴン P を形成します。N からそれらを削除します。
  3. いくつかのポイント イン ポリゴン アルゴリズムを使用して、N 内のポイントを調べます。N 内の各ポイントについて、現在 P に含まれている場合は、N から削除します。N 内にまだ P に含まれていないポイントが見つかるとすぐに、ステップ 4 に進みます。N が空になったら、完了です。
  4. 見つけた点を A と呼びます。A に最も近い P の行を見つけ、その中央に A を追加します。
  5. 手順 3 に戻る

十分に機能する限り、うまくいくと思います — 最初の 3 つのポイントの優れたヒューリスティックが役立つかもしれません。

幸運を！

于 2008-09-17T14:37:14.677 に答える
1

簡単な解決策は、ポリゴンのエッジを歩き回ることです。ポイント 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) なので、ポイントリストを少し並べ替える必要があります。たとえば、都市の重心からの方位でポイントを並べ替えると、各反復で考慮する必要があるポイントのセットを制限できます。

于 2008-09-17T14:42:29.160 に答える
1

Bing Maps V8 インタラクティブ SDK には、高度な形状操作内に凹型ハル オプションがあります。

https://www.bing.com/mapspreview/sdkrelease/mapcontrol/isdk/advancedshapeoperations?toWww=1&redig=D53FACBB1A00423195C53D841EA0D14E#JS

ArcGIS 10.5.1 内の 3D Analyst エクステンションには、凹包、球体、エンベロープ、または凸包のジオメトリ タイプの最小境界体積ツールがあります。どのライセンスレベルでも使用できます。

ここに凹包アルゴリズムがあります: https://github.com/mapbox/concaveman

于 2018-02-13T22:06:17.457 に答える