•  09-06-2019
  •  | 
  •  

题

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

有帮助吗？

解决方案

您将需要使用称为 沃罗诺伊图. 。这会将平面划分为多个区域，每个区域一个区域，其中包含距离每个给定点最近的所有点。

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

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

其他提示

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

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

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

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

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

KD 树和 KD 树的变体似乎工作得很好，但四叉树也可以工作。这些搜索的质量取决于您的 15,000 个数据点集是否是静态的（您没有向参考集中添加大量数据点）。芒特和艾莉亚的工作 近似最近邻 即使没有良好的数学基础，图书馆也易于使用和理解。它还为您的查询类型和容差提供了一定的灵活性。

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

您没有具体说明最快是什么意思。如果您想快速获得答案而不编写任何代码，我会给出 GPS巴贝尔半径过滤器 走吧。

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

这可以通过多种方式解决。我首先会通过生成一个来解决这个问题 德洛奈 网络连接彼此最近的点。这可以通过开源 GIS 应用程序中的 v.delaunay 命令来完成 草. 。您可以使用多种方法之一来完成草丛中的问题 网络分析模块 在草丛中。或者，您可以使用免费空间 RDBMS 后地理信息系统 进行距离查询。PostGIS 空间查询比 MySQL 中的空间查询强大得多，因为它们不受 BBOX 操作的限制。例如：

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

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

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

过早的优化是万恶之源。

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

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

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

谢谢大家的回答。

@汤姆，@克里斯·厄普彻奇：坐标彼此相当接近，而且面积相对较小，约为800平方公里。我想我可以假设表面是平坦的。我需要一遍又一遍地处理请求，并且响应应该足够快以获得更多的网络体验。

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

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

阿莱霍

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

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

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top