从另一个点有效地找到最近的点
Efficiently find closest point from another point
我有一个包含约 10.000 个点的坐标列表 A（纬度、十进制形式的经度）和第二个包含约 100 万个点的相同类型的坐标列表 B。
我想为列表 B 中的每个元素找到列表 A 中最近的点。
我已经完成的是创建两个列表的笛卡尔积并使用半正弦公式找到所有组合的距离。
然后我得到列表 A 中的点，这些点与列表 B 中的每个点具有最小距离。
由于组合总数超过100亿，计算距离的时间过长。
有没有办法确保列表 B 中的每个点都与列表 A 中的一个点匹配，同时还能提高性能？
如果您已经创建了叉积并计算出所有的半正弦距离，那么您已经完成了大部分工作，所以我假设问题是如果您有新的集合 A 和B.
为了反复找到 A 中的最近点，我会构建某种包含 A 中的点的树结构，并在树的每个节点存储信息，这相当于一个边界框或包含其所有后代的等效项。然后当试图找到 A 中最近的点时，你递归地搜索包含 A 的树，当你到达一个节点时从递归调用返回并且你可以从存储在那里的信息计算出它的所有后代都离目标点更远比目前最接近的匹配。
为了让这段代码起作用，边界框信息需要准确，但如果树是愚蠢的，它会减慢搜索速度，但不会阻止他们找到正确答案。这尤其意味着，当您构建树时，您可以安全地忽略经度在 180W = 180E 处环绕的不便习惯。您可以假装经纬度是一个矩形网格并构建一个 k-d 树，您可以将纬度和经度组合起来并对其进行位交错并在结果上构建一个一维搜索树，您可以计算 https://en.wikipedia.org/wiki/Geohash and build a search tree based on this, or you could calculate lots of haversines and build a https://en.wikipedia.org/wiki/Cover_tree -所有这些都应该有效，我不知道哪个最好——这可能取决于您的数据和可用的库。
spatstat 包中的 nncross 函数可用于查找两个不同点的距离 datasets.Using 此函数将在很大程度上减少所花费的时间。
https://www.rdocumentation.org/packages/spatstat/versions/1.53-2/topics/nncross
我有一个包含约 10.000 个点的坐标列表 A（纬度、十进制形式的经度）和第二个包含约 100 万个点的相同类型的坐标列表 B。
我想为列表 B 中的每个元素找到列表 A 中最近的点。
我已经完成的是创建两个列表的笛卡尔积并使用半正弦公式找到所有组合的距离。
然后我得到列表 A 中的点，这些点与列表 B 中的每个点具有最小距离。
由于组合总数超过100亿，计算距离的时间过长。
有没有办法确保列表 B 中的每个点都与列表 A 中的一个点匹配，同时还能提高性能？
如果您已经创建了叉积并计算出所有的半正弦距离，那么您已经完成了大部分工作，所以我假设问题是如果您有新的集合 A 和B.
为了反复找到 A 中的最近点，我会构建某种包含 A 中的点的树结构，并在树的每个节点存储信息，这相当于一个边界框或包含其所有后代的等效项。然后当试图找到 A 中最近的点时，你递归地搜索包含 A 的树，当你到达一个节点时从递归调用返回并且你可以从存储在那里的信息计算出它的所有后代都离目标点更远比目前最接近的匹配。
为了让这段代码起作用，边界框信息需要准确，但如果树是愚蠢的，它会减慢搜索速度，但不会阻止他们找到正确答案。这尤其意味着，当您构建树时，您可以安全地忽略经度在 180W = 180E 处环绕的不便习惯。您可以假装经纬度是一个矩形网格并构建一个 k-d 树，您可以将纬度和经度组合起来并对其进行位交错并在结果上构建一个一维搜索树，您可以计算 https://en.wikipedia.org/wiki/Geohash and build a search tree based on this, or you could calculate lots of haversines and build a https://en.wikipedia.org/wiki/Cover_tree -所有这些都应该有效，我不知道哪个最好——这可能取决于您的数据和可用的库。
spatstat 包中的 nncross 函数可用于查找两个不同点的距离 datasets.Using 此函数将在很大程度上减少所花费的时间。 https://www.rdocumentation.org/packages/spatstat/versions/1.53-2/topics/nncross