我有超过一万五千个经度和纬度坐标的列表。给定任何X，Y坐标，最快的方法是找到列表上最接近的坐标？

解决方案

回答

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

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

@Linor：从本质上讲，这就是创建Voronoi图之后要做的事情。但是，我们可以选择与Voronoi图的线条紧密匹配的分隔线，而不是制作矩形网格(这样我们将获得更少的与分隔线交叉的区域)。如果沿每个子图的最佳分界线递归将Voronoi图一分为二，则可以对要查找的每个点进行树形搜索。这需要先做一些工作，但可以节省以后的时间。每次查找的顺序为log N，其中N是点数。 16个比较比15,000个要好得多！

回答

即使我们创建了一个voronoi图，这仍然意味着我们需要将x，y坐标与所有1.5万个已创建区域进行比较。为了简化操作，我想到的第一件事是在可能的值上创建某种网格，以便我们可以轻松地将x / y坐标放置在网格中的一个框中，完成区域列表后，我们应该迅速缩小可能的候选对象以进行比较(因为网格将更加矩形，一个区域可能位于多个网格位置)。

回答

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

KD树和KD树的变体似乎效果很好，但是四叉树也可以工作。这些搜索的质量取决于15,000个数据点集是否是静态的(我们没有在参考集中添加大量数据点)。即使在数学上没有很好的基础，Mount和Arya在"近似最近邻居"库中的工作也易于使用和理解。它还为我们提供查询类型和容限的灵活性。

回答

过早的优化是万恶之源。

15K坐标不是很多。为什么不遍历15K坐标，看看这是否真的是性能问题？我们可以节省很多工作，也许它永远不会变得太慢而不会引起注意。

回答

我们没有指定最快的含义。如果我们想在不编写任何代码的情况下快速获得答案，那么我可以尝试一下gpsbabel半径过滤器。

回答

相反，它取决于我们要执行多少次，以及一次进行测试时可以使用哪些资源，那么O(log N)技术是好的。如果在服务器上进行一千次，则构造位图查找表会更快，可以直接给出结果，也可以作为第一步。 2GB的位图可以将整个世界的经纬度映射到0.011度像素处的32bit值(在赤道处为1.2km)，并且应该适合内存。如果我们仅在一个国家/地区进行操作，或者可以排除极点，则可以使用较小的地图或者更高的分辨率。对于15,000点，我们可能有一张较小的地图，我首先将其调整大小，这是对需要较高分辨率的邮政编码进行邮政编码搜索的第一步。根据要求，我们可以使用映射的值直接指向结果，或者指向候选对象的简短列表(这将允许使用更小的映射，但是需要更大的后续处理，因此我们不再位于O(1)查找区域中) 。

回答

我曾经为一个网站这样做。 IE。在距离邮政编码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具有执行此操作的SPATIAL数据类型。其他语言/框架/数据库具有支持此功能的库。基本上，这种数据结构将点嵌入矩形树中，并使用半径搜索树。这应该足够快，而且我相信比构建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;

由于我们使用的是经度和纬度，因此我们可能想使用Spheroid-Distance函数。有了空间索引，PostGIS可以很好地扩展大型数据集。

回答

只是为了相反，你是说距离或者开车时间很近？在市区，我很乐意在高速公路上行驶5英里(5分钟)，而不是在另一个方向行驶4英里(20分钟停走)。

因此，如果它是我们需要的"最接近"度量标准，那么我将研究具有旅行时间度量标准的GIS数据库。