12

我有一个超过 15000 个经纬度坐标的列表。给定任何 X,Y 坐标，找到列表中最近坐标的最快方法是什么？

4

13 回答 13

8

我为一个网站做过一次。即在您的邮政编码 50 英里范围内找到经销商。我使用大圆计算来找到北 50 英里、东 50 英里、南 50 英里和西 50 英里的坐标。这给了我一个最小和最大纬度以及最小和最大长度。从那里我做了一个数据库查询：

select *
    from dealers
    where latitude  >= minlat
      and latitude  <= maxlat
      and longitude >= minlong
      and longitude <= maxlong

由于其中一些结果仍然会在 50 多英里之外，所以我在那个小坐标列表上再次使用了大圆公式。然后我打印出列表以及与目标的距离。

当然，如果您想搜索国际日期变更线或两极附近的点，那么这是行不通的。但它适用于北美内部的搜索！

于 2008-08-30T13:11:16.643 回答
6

您将需要使用称为Voronoi 图的几何结构。这将平面划分为多个区域，每个区域一个区域，其中包含最接近每个给定点的所有点。

用于创建 Voronoi 图和安排数据结构查找的确切算法的代码太大，无法放入这个小编辑框。:)

@Linor：这基本上就是您在创建 Voronoi 图后要做的事情。但是，您可以选择与 Voronoi 图线非常匹配的分割线，而不是制作矩形网格（这样您将获得更少的穿过分割线的区域）。如果您沿着每个子图的最佳分割线递归地将 Voronoi 图分成两半，则可以对要查找的每个点进行树搜索。这需要一些前期工作，但可以节省以后的时间。每个查找将按 log N 的顺序进行，其中 N 是点数。16 次比较比 15,000 次要好很多！

于 2008-08-30T10:41:35.147 回答
3

您描述的一般概念是最近邻搜索，并且有大量技术可以准确或近似地解决这些类型的查询。基本思想是使用空间分区技术将复杂度从每个查询的 O(n) 降低到每个查询的（大约）O(log n)。

KD-Trees 和 KD-Trees 的变体似乎工作得很好，但四叉树也可以工作。这些搜索的质量取决于您的 15,000 个数据点集是否是静态的（您没有向参考集添加大量数据点）。Mount 和 Arya 在Approximate Nearest Neighbor库上的工作既易于使用又易于理解，即使没有良好的数学基础。它还为您在查询的类型和容差方面提供了一些灵活性。

于 2008-08-30T12:01:48.870 回答
2

这取决于您想要执行多少次，以及可用的资源 - 如果您只进行一次测试，那么 O(log N) 技术就很好。如果您在服务器上执行一千次，则构建位图查找表会更快，直接给出结果或作为第一阶段。2GB 的位图可以将整个世界经纬度映射到 0.011 度像素（赤道 1.2 公里）处的 32 位值，并且应该适合内存。如果你只做一个国家，或者可以排除两极，你可以有一个更小的地图或更高的分辨率。对于 15,000 点，您可能有一个小得多的地图 - 我首先调整它的大小，作为进行经纬度到邮政编码搜索的第一步，这需要更高的分辨率。根据要求，您可以使用映射值直接指向结果，

于 2008-08-30T12:33:04.943 回答
1

您没有指定最快的含义。如果您想在不编写任何代码的情况下快速获得答案，我会尝试使用gpsbabel 半径过滤器。

于 2008-08-30T12:19:15.817 回答
1

根据您的说明，我将使用几何数据结构，例如 KD-tree 或 R-tree。MySQL 有一个 SPATIAL 数据类型可以做到这一点。其他语言/框架/数据库有库来支持这一点。基本上，这样的数据结构将点嵌入到矩形树中，并使用半径搜索树。这应该足够快，而且我相信比构建 Voronoi 图更简单。我想有一个阈值，您更喜欢 Voronoi 图的附加性能，因此您将准备好支付增加的复杂性。

于 2008-08-31T11:54:37.430 回答
1

这可以通过多种方式解决。我将首先通过生成一个连接最近点的Delaunay网络来解决这个问题。这可以通过开源 GIS 应用程序GRASS中的 v.delaunay 命令来完成。您可以使用 GRASS 中的众多网络分析模块之一来完成 GRASS 中的问题。或者，您可以使用免费的空间 RDBMS PostGIS进行距离查询。PostGIS 空间查询比 MySQL 中的要强大得多，因为它们不受 BBOX 操作的限制。例如：

SELECT network_id, ST_Length(geometry) from spatial_table where ST_Length(geometry) < 10;

由于您使用的是经度和纬度，因此您可能想要使用Spheroid-Distance 函数。借助空间索引，PostGIS 非常适合大型数据集。

于 2008-12-30T15:14:10.983 回答
0

即使您创建了一个 voronoi 图，这仍然意味着您需要将您的 x、y 坐标与所有 15,000 个创建的区域进行比较。为了使这更容易，我想到的第一件事是在可能的值上创建某种网格，以便您可以轻松地将 x/y 坐标放置到网格中的一个框中，如果相同的话完成区域列表后，您应该快速缩小可能的候选对象进行比较（因为网格会更矩形，一个区域可能位于多个网格位置）。

于 2008-08-30T11:34:12.120 回答
0

过早的优化是万恶之源。

15K坐标不是那么多。为什么不遍历 15K 坐标，看看这是否真的是一个性能问题？您可以节省大量工作，而且可能永远不会太慢以至于无法注意到。

于 2008-08-30T12:12:50.327 回答
0

这些坐标分布在多大范围内？他们在哪个纬度？您需要多少精度？如果它们非常接近，您可能会忽略地球是圆的这一事实，而只是将其视为笛卡尔平面，而不是搞乱球面几何和大圆距离。当然，随着您离赤道越来越远，经度与纬度相比会变小，因此某种比例因子可能是合适的。

从一个相当简单的距离公式和蛮力搜索开始，看看这需要多长时间，以及结果是否足够准确，然后再看中。

于 2008-08-30T14:24:51.663 回答
0

谢谢大家的回答。

@Tom，@Chris Upchurch：坐标彼此相当接近，并且它们位于大约 800 平方公里的相对较小的区域内。我想我可以假设表面是平坦的。我需要一遍又一遍地处理请求，并且响应应该足够快以获得更多的网络体验。

于 2008-08-31T08:18:05.700 回答
0

网格非常简单，而且速度非常快。它基本上只是一个二维列表数组。每个数组条目表示落在网格单元内的点。很容易设置网格：

对于每个点 p
  获取包含 p 的单元格
  将点添加到该单元格的列表

查找内容非常容易：

给定一个查询点 p
  获取包含 p 的单元格
  针对查询点 p 检查该单元格（及其 8 个邻居）中的点

阿莱霍

于 2008-11-15T21:35:45.120 回答
0

只是为了逆向，你的意思是距离很近还是（驾驶）时间很近？在市区，我很乐意在高速公路上行驶 5 英里（5 分钟），而不是在另一个方向行驶 4 英里（20 分钟走走停停）。

因此，如果它是您需要的“最接近”的指标，我会查看带有旅行时间指标的 GIS 数据库。

于 2008-12-30T15:35:39.240 回答