3

NxN 値の高さマップがあります。

x 座標と y 座標が与えられている点 A (赤い点) を指定して (z はデータからわかっているので、A は表面の頂点です)、円周上にある一連の点を見つけたいと思います。中心が A で半径が R の円は、データ ポイントによって記述される想像上の表面にドレープされた円形の「布」(グレー) の適切な近似値です。

私が見つけようとしている点のセット間の逆距離であるサンプリングは、均一である必要はありませんが、メッシュのエッジとA から距離 R の円。

この一連のポイントを見つける方法は?

これは既知の問題ですか?

円がドレープされた 3D 高さマップ
(ソース: keplero.com )

- 編集

Jan が使用している仮定は正しいです。サンプルは、[0,0] に位置合わせされた (XY 平面内の) 規則的な長方形または正方形のグリッドを形成します。しかし、距離を計算するために Z 方向の変位を考慮したいと思います。高さマップを地形として見ることができ、私が探しているアルゴリズムは、指定された緯度または経度のパスを移動して、A から R の距離にあるポイントをマークする探検家に与える指示として探しています。 、これまでに行われたすべての Z 変位が考慮されています。探検家も谷を登ったり降りたりします。

このための自明なアルゴリズムは、次のようなものになります。R が与えられると、x 軸と y 軸の最大変位は完全に平らな面に対応することがわかっています。勾配がない場合、x、y ポイントはすべて境界正方形 Ax-R < x < Ax+r および Ay-R 内にあります。

この時点で、境界がグリッドの 1 つのセルの端に入ると、そのセルから出なければならないため、近くのセルへの移動が開始されます。

4

2 に答える 2

1

これを正確に解決するのは非常に難しいと思うので、探索者が表面上をたどる経路をシミュレートするという簡単なアプローチを試してみることをお勧めします。

開始点Aと移動距離を指定して、からのXY平面上dの点の円を計算します。PdA

の各ポイントについてp、P線分A-pをグリッドと交差させて、エクスプローラーがから移動している場合に発生する順序で、エクスプローラーが1つのグリッドの正方形から次のグリッドの正方形に交差する一連のポイントになりAます。これらのポイントには、グリッドデータからの内挿によってz座標を指定する必要があります。したがって、このポイントシーケンスを進めて、これまでに移動した距離を追跡できます。最終的には目標距離に到達します-pこの時点になるように調整してください。

Pには、探している境界が含まれています。必要に応じて、サンプルの忠実度（のサイズP）を調整します。

于 2012-11-30T13:01:14.740 に答える
0

明確にするために-3Dで三角形分割されたサーフェスがあり、メッシュ内の特定の開始頂点に対して、サーフェスに沿ったパス（つまり、測地線）を介して長さで到達可能Viな頂点のセットを見つけたいと考えています。ULi <= R

1 つのアプローチは、これをグラフベースの問題に変換することです。

  1. 重み付けされた無向グラフG(V,E)を形成します。ここVで、 は三角形分割されたサーフェス メッシュの頂点のEセットであり、 はこのメッシュのエッジのセットです。エッジの重みは、各エッジのユークリッド (3d) の長さである必要があります。このグラフは離散距離マップです。つまり、メッシュ内の隣接する各頂点間の「表面に沿った」距離です。
  2. ダイクストラのアルゴリズムのバリアントを開始頂点から実行し、制約を満たすVi長さのパスのみを展開します。訪問した頂点のセットは、 の最短 (測地線) パスで到達できる頂点になります。LiLi <= RULi <= R

このアプローチの精度は、サーフェス メッシュの解像度に関連している必要があります。各要素内のサーフェスの曲率が高すぎない限り、ユークリッド エッジの長さは実際の測地線距離の適切な近似値である必要があります。そうでない場合は、サーフェス メッシュその辺は磨くべき。

お役に立てれば。

于 2012-11-26T21:24:36.080 に答える