10

G'day

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

网格是一个二维网格，存储在xand中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树中。这是一棵树，它沿着平均值分割数据，然后沿着它们的平均值分割两个数据集，等等，直到你把它们分成一个树结构。

在此处输入图像描述

这会将您的搜索效率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值很容易确定每个点的像元。

如果您可以索引立体表示中的单元格，则当您转换为另一种表示时，索引将相同。

主要要求是在某种变换下，网格点由两个向量定义，X并且Y，因此对于任何xinX和yin Y，(x, y)都是一个网格点。接下来通过该变换同时变换网格和轮廓点。然后给定一个任意点(x1, y1)，我们可以通过找到最接近x的x1和最接近的y来找到合适的网格单元y1。变换回来以获取所需坐标系中的点。

于 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 回答