在matlab网格中找到最近的点

Question

天儿真好

我正在尝试编写一种智能方法来找到沿轮廓点的最近点网格点.

网格是一个2维网格,存储在x和y(它包含网格单元的x和y公里位置).

轮廓是由x和y位置组成的线,不一定是规则间隔的.

如下所示 - 红点是网格,蓝点是轮廓上的点.如何找到最接近每个蓝点的红点的索引？

编辑 - 我应该提到网格是纬度/经度网格,是一个非常接近南极的区域.因此,点(红点)是距离南极的米的位置(使用极坐标立体图).由于网格是地理网格,因此网格间距不相等 - 由于高纬度地区的扭曲,形状单元格略有不同(红点定义了单元格的顶点).结果是我不能只找到x和y矩阵的哪一行/列最接近输入点坐标 - 与常规网格不同meshgrid,行和列中的值会有所不同......

干杯戴夫

Answer 1

通常的方法是:

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

但更好的方法是将红色数据放入kd树中.这是一个沿着它的平均值分割数据的树,然后沿着它们的平均值分割两个数据集,直到你将它们分成树结构.

这将改变你的搜索effeciancy O(n*m)到O(log(n)*m)

这是一个图书馆:

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

该库将为您提供从数据中轻松制作kd树并搜索其中最近点的方法.

或者你可以使用四叉树,不是简单但相同的想法.(你可能必须为此编写自己的库)

确保最大的数据集(在这种情况下是您的红点)进入树中,因为这将减少最大的时间.

Answer 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);