您将需要使用一种称为aVoronoi图。这将平面划分为多个区域，每个区域对应一个点，这些区域包含最靠近每个给定点的所有点。

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

@Linor：这基本上就是你在创建Voronoi图后要做的事情。但是，你可以选择与Voronoi图中的线非常匹配的分界线，而不是制作矩形网格（这样你会得到更少的与分界线相交的区域）。如果你沿着每个子图的最佳分割线将Voronoi图递归地一分为二，那么你可以对你想要查找的每个点进行树搜索。这需要在前面做一些工作，但在后面可以节省时间。每个查找将按照对数N的顺序进行，其中N是点数。16次比较比15000次要好得多！

我曾经为一个网站这样做过。也就是说，在你的邮政编码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树的变体似乎工作得很好，但四叉树也会工作。这些搜索的质量取决于您的15000个数据点集是否是静态的（您没有向参考集添加大量数据点）。Mount和Arya在近似最近邻居库易于使用和理解，即使没有良好的数学基础。它还为您提供了查询类型和容差方面的一些灵活性。

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

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

根据您的说明，我将使用几何数据结构，如KD树或R树。MySQL有一个SPATIAL数据类型来实现这一点。其他语言/框架/数据库都有库来支持这一点。基本上，这样的数据结构将点嵌入矩形树中，并使用半径搜索该树。这应该足够快，我相信这比构建Voronoi图更简单。我想有一个阈值，超过这个阈值，你会更喜欢Voronoi图的附加性能，这样你就可以为增加的复杂性付出代价了。

这可以通过多种方式解决。我将首先通过生成Delaunay网络相互连接最近的点。这可以通过开源GIS应用程序中的v.Delaunay命令来实现GRASS。您可以使用众多GRASS中的网络分析模块。或者，您可以使用免费的空间RDBMSPostGIS进行距离查询。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坐标，看看这是否真的是一个性能问题？你可以节省很多工作，也许它永远不会慢到让人注意到。

这些坐标分布的区域有多大？他们在什么纬度？你需要多大的准确性？如果它们离得很近，你可能会忽略地球是圆的这一事实，而把它当作一个笛卡尔平面，而不是纠缠于球面几何和大圆距离。当然，随着你离赤道越来越远，经度比纬度小，所以某种比例因子可能是合适的。

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

谢谢大家的回答。

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

网格非常简单，而且速度非常快。它基本上只是一个列表的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

阿列霍

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

因此，如果这是您需要的最接近的度量，我会查看具有旅行时间度量的GIS数据库。