10

G'day

等高線に沿ったポイントに最も近いグリッドポイントを見つけるためのスマートな方法をプログラムしようとしています。

グリッドは2次元グリッドであり、およびに格納されxますy（グリッドセルのxおよびyキロメートルの位置が含まれます）。

等高線は、xとyの位置で構成される線であり、必ずしも一定の間隔で配置されているとは限りません。

これを以下に示します。赤い点はグリッドで、青い点は等高線上の点です。各青い点に最も近い赤い点のインデックスを見つけるにはどうすればよいですか？

各青い点に最も近い赤い点を補間します

編集-グリッドは、南極にかなり近い領域の緯度/経度グリッドであることに言及する必要があります。したがって、ポイント（赤い点）は、南極からのメートル単位の位置です（極心平射法を使用）。グリッドは地理的なグリッドであるため、グリッドの間隔が不均等になります。高緯度での歪みのために、セルの形状がわずかに異なります（赤い点がセルの頂点を定義します）。その結果x、y行列のどの行/列が入力ポイントの座標に最も近いかを見つけることができません-からの通常のグリッドとは異なりmeshgrid、行と列の値は異なります...

乾杯デイブ

4

4 に答える 4

10

通常の方法は次のとおりです。

for every blue point {
    for every red point {
        is this the closest so far
    }
}

しかし、より良い方法は、赤いデータをkdツリーに入れることです。これは、データを平均に沿って分割し、2つのデータセットを平均などに沿って分割して、ツリー構造に分割するツリーです。

ここに画像の説明を入力してください

O(n*m)これにより、検索効率がからに変わりますO(log(n)*m)

これがライブラリです：

http://www.mathworks.com.au/matlabcentral/fileexchange/4586-kd-tree

このライブラリは、データからkdツリーを簡単に作成し、その中で最も近いポイントを検索する手段を提供します。

あるいは、単純ではなく同じアイデアの四分木を使用することもできます。（そのために独自のライブラリを作成する必要があるかもしれません）

最大のデータセット（この場合は赤い点）がツリーに入るようにしてください。これにより、最大の時間短縮が実現します。

于 2012-11-27T06:13:19.933 に答える
2

nearestのフラグを使用してそれを行う方法を見つけたと思いますgriddata。

xグリッドおよび行列と同じサイズの行列を作成しyますが、対応する行列要素の線形インデックスで埋められます。これは、ベクトル（である1:size(x,1)*size(x,2)）をと同じ次元に再形成することによって形成されxます。

次にgriddata、nearestフラグを使用して、輪郭上の各ポイントに最も近いポイントの線形インデックス（青い点）を見つけます。次に、を使用して添え字表記に戻すとind2sub、青い点線の等高線上の各点に最も近い点の行列添え字を表す2つの行ベクトルが残ります。

以下のこのプロットは、輪郭（青い点）、グリッド（赤い点）、および最も近いグリッドポイント（緑の点）を示しています。

グリッドの結果

これは私が使用したコードスニペットです：

index_matrix1 = 1:size(x,1)*size(x,2); 
index_matrix1 = reshape(index_matrix1,size(x));
lin_ind = griddata(x,y,index_matrix1,CX,CY,'nearest'); % where CX and CY are the coords of the contour
[sub_ind(1,:),sub_ind(2,:)] = ind2sub(size(x),lin_ind);
于 2012-11-28T00:09:50.057 に答える
1

立体表現では、ポイントがr-theta座標できれいなグリッドを形成していると思います。（私はこれにあまり精通していないので、間違っている場合は訂正してください。私の提案はまだ適用される可能性があります）。

プロットでは、ステレオグラフィックから緯度経度に変換します。これにより、グリッドが歪められます。ただし、最も近いポイントを見つけるには、青い等高線ポイントの緯度経度をステレオグラフィック座標に変換することを検討してください。ステレオグラフィック座標では、rとのtheta値を使用して各ポイントのセルを簡単に決定できます。

立体表現でセルにインデックスを付けることができる場合、別の表現に変換してもインデックスは同じになります。

主な要件は、ある変換の下で、グリッド点が2つのベクトルによって定義されることです。したがって、inXとinのYいずれかがグリッド点になります。次に、その変換によってグリッドと輪郭点の両方を変換します。次に、任意の点が与えられると、に最も近いものと最も近いものを見つけることによって、適切なグリッドセルを見つけることができます。逆変換して、目的の座標系のポイントを取得します。xXyY(x, y)(x1, y1)xx1yy1

于 2012-11-27T23:11:28.620 に答える
1

dsearchn：ND最近傍点検索。

[k, d] = dsearchn(A,B)：最も近いポイントまでの距離dを返します。dは長さpの列ベクトルです。

http://au.mathworks.com/help/matlab/ref/dsearchn.html?s_tid=gn_loc_drop

于 2016-02-04T23:14:02.843 に答える