在Matlab网格中找到最近的点

Question

你好

我试图编写一种智能方法，以找到沿轮廓的点最接近的网格点。

该网格是一个二维网格，存储在x和y中（它们包含网格单元的x和y公里位置）。

轮廓线是由x和y位置组成的线，不一定是均匀分布的。

如下所示 - 红色点是网格，蓝色点是轮廓线上的点。 我如何找到与每个蓝色点最接近的红色点的索引？

编辑 - 我应该提到，网格是一个接近南极的纬度/经度网格。 因此，点（红点）是离南极的距离（使用极地立体投影表示）的米数。 由于网格是地理网格，因此存在不均匀的网格间距 - 由于高纬度的变形而具有稍微不同的形状的单元格（其中红点定义了单元格的顶点）。 结果是，我不能仅找到与输入点坐标最接近的x和y矩阵的哪一行/列对应 - 与meshgrid的常规网格不同，行和列中的值都有所变化...

谢谢 Dave

- David_G

---

您的网格非常规则，但未对矩形 xy 坐标轴对齐。您是否能够给出网格点的数学定义？我怀疑最好的方法是通过代数方式而不是算法方式来找到答案 - 由于网格是明确定义的，因此您可以通过几何方式确定最接近的点而不是通过测试点对。您的网格十分规则，但未对齐矩形坐标系的 xy 轴。请问您可以给我们一个网格点的数学定义吗？我认为最好的方式是通过代数方法而非算法方法来找到答案——因为该网格是有明确定义的，所以您可以通过几何方法而非测试点对来确定最接近的点。 - Brian L

@BrianL 好主意！如果这些点有旋转变换，那么你可以轴向对齐它们，然后使用扩展框搜索方法进行搜索！ - Fantastic Mr Fox

@BrianL 和 Ben - 在我的编辑中，我试图详细说明网格的性质。它不与xy轴对齐，虽然看起来很规则，但实际上它是地理坐标系（纬度/经度），由于位于高纬度位置（靠近南极），最南端的单元格略小于最北端的单元格。此外，为了方向的参考 - 在上面的图中，北方是指右下方，因为它是一个极射赤面投影。 - David_G

@David_G，你的图片已经消失了，现在这个问题变得不太有用了。你能否重新上传它在这里？ - naught101

是的，抱歉。旧员工网站托管已经失效了！我会尽力解决的。 - David_G

@naught101 哇，我很惊讶我能在五年前的备份中找到它们藏起来了！ - David_G

Answer 1

通常的方法是这样的：

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-k-d-tree

此库将为您提供使数据轻松转换为kd树并在其中搜索最近点的手段。

或者您可以使用四叉树，不过需要实现自己的库，它与kd树的思路相同但更加复杂。

请确保将最大的数据集（在本例中为红点）放入树中，因为这将提供最大的时间减少。

- Fantastic Mr Fox

---

+1 感谢您的建议 @Ben - 我之前没有听说过kd树。如果我无法像您上面建议的那样通过代数方法解决这个问题，我可能会尝试您的建议。 - David_G

我不太明白这样做如何能够显著提高效率。看起来应该可以构造一个病态的例子，例如最近的两个点在第一个平均值的两侧，因此您必须遍历整棵树才能找到它们是最接近的（如果我正确理解了它的使用方式）。是这种情况吗？是平均效率大大提高，但效率上限没有改善吗？ - naught101

@naught101，你不是在KD树中搜索两个点。一个点来自于迭代一组点。最接近这个点的点来自于在KD树中搜索。是的，最坏情况相同，但平均情况为O(log(n))，对于这样一个大数据集来说更好。 - Fantastic Mr Fox

除了效率之外，我认为这种方法在某些情况下可能会产生错误的结果。例如，如果您想匹配的点恰好位于第二次迭代中右上矩形的左下角点的正下方，那么它显然会更接近该点，但实际上它将被分配给第三次迭代中右下矩形的左上角点。这可能会导致距离更远，甚至不是次优选择的分配。我猜这种方法会在前几个（8个？）最佳点中找到一个网格点，但似乎不能保证找到最佳点。 - naught101

@FantasticMrFox：例如，参见 https://imgur.com/a/9vsdLGz - 即使绿点更接近其上方的点，它也将被分配给右下角的点。算法的一部分是通过检查覆盖以绿点为中心、半径为已分配点的圆的整个树的所有部分来完成的。在最坏的情况下，这可能需要回溯整个树。 - naught101

Answer 2

我认为使用griddata的nearest标志可以实现它。

我创建了一个矩阵，其大小与网格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);

- David_G

Answer 3

我猜在立体投影中，你的点以r-theta坐标形式形成了一个整齐的网格。（如果我错了，请纠正我。我的建议仍然适用）。

为了绘图，你需要将立体投影转换为经纬度，这会扭曲网格。但是，为了找到最近的点，请考虑将蓝色轮廓点的经纬度转换为立体投影坐标，在那里可以使用其r和theta值轻松确定每个点的单元格。

如果你能够在立体投影中索引单元格，则在转换到另一种表示时，索引将保持不变。

主要要求是在某些转换下，网格点由两个向量X和Y定义，以便对于X中的任何x和Y中的任何y，(x，y)是一个网格点。接下来通过该变换同时转换网格和轮廓点。然后，给定任意点(x1，y1)，我们可以通过找到最接近x1的x和最接近y1的y来找到适当的网格单元。再次进行转换以获得所需坐标系中的点。

- Brian L

Answer 4

dsearchn：N维最近点搜索。

[k, d] = dsearchn(A,B)：返回到最近点的距离d。d是长度为p的列向量。

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

- electron1979