17

z(x,y)Delaunay 三角形分割に基づいて、不規則にサンプリングされた関数の線形補間を実行しようとしています。Delaunay 三角形分割を取得した丘があるとします。

ドロネー三角丘

z三角形の各頂点 (サンプル)の高度はわかっています。z任意の地点の高度が欲しい(x,y)。

  • どの三角形に point が含まれているかを知るにはどうすればよい(x,y)ですか? これがわかれば、三角形の 3 つの頂点の間を補間するのはかなり簡単だと思います。

  • これの既製の実装を知っていますか？おそらく補間ビットも含まれていますか？これのオープンソース実装がどこかにあるに違いないと確信しています。私は特に Java (ソースまたは JAR) に興味がありますが、VB やその他の言語のフレーバーも同様に役立つ可能性があります。

4

5 に答える 5

9

三角形分割を検索ポイントに向かって歩くと、ターゲットの三角形を見つけることができます。これは、三角形が二重に接続されたエッジリストまたは同様の構造に格納されている場合のように、一定時間で隣接する三角形にアクセスできることを前提としています。追加のデータ構造が必要ないため、実装は簡単です。

追加された詳細：Pを検索ポイントとします。T0の任意の三角形T0と点P0を取ります。PがT0にある場合は、終了です。それ以外の場合は、線P0-Pと交差するT0のエッジE0を見つけます。エッジE0上のTの隣接する三角形T1に移動し、T1の点P1を取ります。ここで、三角形TnにPが含まれるまで繰り返します。

于 2011-09-12T14:15:13.360 に答える
3

これは簡単に答えられる質問ではなく、ルックアップに必要なパフォーマンスと、そのパフォーマンスを得るためにどれだけのメモリを交換する準備ができているかによって異なります。

これが非常にまれな操作である場合、または三角形の数が少ない場合は、常にすべての三角形を反復処理できます。ポイントを含む三角形のテストはそれほど高価ではありません。おそらく最初にこれをコーディングして、許容できるパフォーマンスが得られるかどうかを確認する必要があります。

受け入れられない場合は、三角形分割を試してみることができます。基本的に三角形から始めて、探しているポイントに最も近い次の三角形を見つけます。これは、単純な三角形のリストに追加情報があることを前提としています。具体的には、特定の頂点を使用する三角形を見つけることができる (または、隣接する三角形から三角形を見つけることができます。これは、複雑さがほぼ同じです)。これを計算しないと、ポイントを見つけるのとほぼ同じくらいコストがかかります。

それが十分に速くない場合は、ある種のR-Treeをセットアップする必要があります。これにより、三角形をその位置から非常に迅速に見つけることができますが、多くの前処理とツリー用の大量のメモリが必要になります。

頻繁に行わないと、2 番目と 3 番目の方法のそれぞれの前処理を計算する時間が、徹底的な検索で三角形を見つける時間よりも長くなることがあります。

于 2011-09-12T14:32:39.193 に答える
2

私のアルゴリズムの知識は少し錆びています。私の以前の答えの代わりに、ボロノイ図を使用する方がおそらく良いでしょう。

特定のクエリポイントに最も近いオブジェクトを見つけたい場合に、最近傍クエリに応答するために、ボロノイ図の上にポイント位置データ構造を構築できます。最近傍クエリには多数のアプリケーションがあります。たとえば、最寄りの病院、またはデータベース内で最も類似したオブジェクトを検索したい場合があります。

私はこれの詳細についてあなたを助けることはできませんが、うまくいけば、これはあなたを正しい方向に向けることができます。

三角形にリンクするRツリーを使用することもできると思います。

「javar-tree」を使用してグーグルですばやく検索すると、既存のライブラリを見つけるのに役立ちます。

于 2011-09-12T14:16:26.313 に答える
2

Delaunay Hierarchy http://hal.inria.fr/inria-00166711を使用できます 。ポイントのサブセットを取得し、それを三角形化し、2 つのレイヤー間の頂点間にリンクを作成するという考え方です。次に、小さな三角測量で「ウォーク」が実行され、あるレイヤーから次のレイヤーにジャンプして、ウォークを続行します。これは CGAL の三角形分割で実装されています: http://www.cgal.org/Manual/latest/doc_html/cgal_manual/Triangulation_2/Chapter_main.html#Section_37.10

于 2013-03-04T15:57:13.207 に答える
1

ここで動作する実装を見つけました: http://www.cs.bgu.ac.il/~benmoshe/DT/

このfindメソッドは、指定されたポイントを含む三角形を見つけ、zメソッドは平面内挿を行います。

残念ながら、これはコンパイル済みの JAR であるため、アルゴリズムが何であるかはわかりませんが、@Jiri と @DJClayworth によって提案されているように、「三角測量を通り抜ける」ように感じます。

また、残念なことに、この JAR で使用されているかなり型にはまらない命名法があります。より良い命名法でラッパークラスを書くことになるかもしれません。

于 2011-10-07T10:59:02.897 に答える