经纬度、经度坐标的比较

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

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

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

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

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

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

过早的优化是万恶之源。

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

你没有具体说明你所说的最快是什么意思。如果您想在不编写任何代码的情况下快速获得答案，我会尝试一下 gpsbabel 半径过滤器。

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

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

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

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

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

这些坐标分布在多大的区域？它们在什么纬度？您需要多高的精度？如果它们离得很近，你可能会忽略地球是圆的事实，把它当作一个笛卡尔平面，而不是弄乱球形几何和大圆距离。当然，随着离赤道越来越远，与纬度相比，经度会变小，因此某种比例因子可能是合适的。

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

感谢大家的回答。

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

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

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

for each point p
  get cell that contains p
  add point to that cell's list

而且查找内容非常容易：

given a query point p
  get cell that contains p
  check points in that cell (and its 8 neighbors), against query point p

阿莱霍

这可以通过多种方式解决。我首先会通过生成一个将最近点彼此连接起来的 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;

由于您使用的是经度和纬度，因此您可能希望使用“椭球体距离”函数。借助空间索引，PostGIS 可以很好地扩展大型数据集。

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

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