1

私は、3 次元空間に配置されたデータ ポイントの大規模なセット (400 万以上) があり、それぞれにスカラー関数値があるという問題に取り組んでいます。これは、XD、YD、ZD、および FD の 4 つの配列で表されます。タプル (XD[i]、YD[i]、ZD[i]) は、FD[i] の値を持つデータ ポイント i の位置を参照します。

データと同じスペースに、たとえば 100x100x100 ポイントの直線グリッドを重ね合わせたいと思います。このグリッドは次のように設定されます。

[XGrid, YGrid, ZGrid] = np.mgrid[Xmin:Xmax:Xstep, Ymin:Ymax:Ystep, Zmin:Zmax:Zstep]
XG = XGrid[:,0,0]
YG = YGrid[0,:,0]
ZG = ZGrid[0,0,:]

XGrid は、グリッド内の各ポイントの x 値の 3D 配列です。XG は、XStep の距離で区切られた、Xmin から Xmax までの x 値の 1D 配列です。

内挿アルゴリズムを使用したいのですが、各グリッド ポイントの関数の値を周囲のデータに基づいて見つける必要があります。このアルゴリズムでは、関心のあるグリッド ポイントに最も近い (または少なくとも近い) 20 個のデータ ポイントが必要です。つまり、グリッド ポイント (XG[i]、YG[j]、ZG[k]) について、20 個の最も近いデータ ポイントを見つけたいと考えています。

私が考えることができる唯一の方法は、各データ ポイントを通過する 1 つの for ループと、すべての (非常に多くの!) データ ポイントを通過する後続の埋め込み for ループを用意し、ユークリッド距離を計算し、20 個の最も近いものを選択することです。

for i in range(0,XG.shape):
  for j in range(0,YG.shape):
    for k in range(0,ZG.shape):

      Distance = np.zeros([XD.shape])

      for a in range(0,XD.shape):
        Distance[a] = (XD[a] - XG[i])**2 + (YD[a] - YG[j])**2 + (ZD[a] - ZG[k])**2

      B = np.zeros([20], int)
      for a in range(0,20):
        indx = np.argmin(Distance)
        B[a] = indx
        Distance[indx] = float(inf)

これにより、グリッド ポイントに最も近いデータ ポイントのインデックスの配列 B が得られます。これは、各グリッド ポイントの各データ ポイントを通過するのに時間がかかりすぎるように感じます。

距離を計算する前にデータポイントを整理する方法など、計算時間を短縮できる提案を探しています。

4

3 に答える 3

1

一見似ているが2Dの問題を見て、そこからのアイデアで改善できないかどうかを確認してください。

頭のてっぺんから、座標（3つの別々の配列）に従ってポイントを並べ替えることができると思います。グリッドポイントに最も近いポイントが必要な場合は[X, Y, Z]、これら3つの配列内のポイントをすばやく見つけて、そこから開始します。

于 2012-07-10T10:46:59.000 に答える
1

また、ユークリッド距離は実際には必要ありません。これは、次のように説明できる相対距離にのみ関心があるためです。

abs(deltaX) + abs(deltaY) + abs(deltaZ)

そして、高価な電力と平方根を節約します...

于 2012-07-10T10:51:40.357 に答える