22

给定一组具有 x,y 坐标的数百万个点，选择什么算法可以快速找到距某个位置最近的 1000 个点？这里的“快速”是指家用计算机上大约 100 毫秒。

蛮力意味着进行数百万次乘法然后对它们进行排序。虽然即使是一个简单的 Python 应用程序也可以在不到一分钟的时间内完成，但对于交互式应用程序来说仍然太长了。

这些点的边界框是已知的，因此可以将空间划分为一个简单的网格。然而，这些点的分布有些不均匀，所以我怀疑大多数网格方块会是空的，然后突然其中一些会包含大部分点。

编辑：不一定要准确，实际上可能非常不准确。例如，如果前 1000 名实际上只是前 2000 名中的一些随机点，那将不是什么大问题。

编辑：点集很少改变。

4

7 回答 7

20

使用四叉树怎么样？

您将区域划分为矩形，如果区域的点密度低，则矩形很大，如果区域的点密度高，则矩形会很小。您递归地将每个矩形细分为四个子矩形，直到矩形足够小或包含足够少的点。

然后，您可以开始查看该位置附近矩形中的点，然后向外移动，直到找到 1000 个点。

用于此的代码可能会有些复杂，所以也许您应该先尝试使用简单的网格，看看它是否足够快。

于 2009-05-08T05:27:06.977 回答
13

四叉树很好，但BSP 树保证在 O(log n) 时间内运行。我认为四叉树需要有限的边界体积，并且在某些退化的情况下四叉树会惨遭失败，例如当大量点占据相同相对较小的空间时。

话虽如此，四叉树可以说更容易实现，并且在大多数常见情况下非常有效。这是 UPS 在其路由算法中使用的，因为它的缺点在实践中不会造成重大问题，可能是因为城市往往分布在感兴趣的区域上。

于 2009-05-08T05:34:40.483 回答
7

您想使用四叉树或 RTree 之类的结构。这些是多维索引结构。

关键是使用良好的“空间填充曲线”，这有助于定义点的接近度。一个简单的空间填充曲线是 Zorder，但您会更感兴趣的是类似希尔伯特曲线的东西。

http://en.wikipedia.org/wiki/Space_filling_curve

我不知道这些东西的任何预打包实现。我最近在 2 维中实现了我自己的 RTree，它只支持批量加载和搜索（通过提供的边界框）。

这里的一个缺点是您的点必须包含在有限区域中。知道有空间填充曲线适用于非有限空间，但我对它们一无所知。

于 2009-05-08T06:24:26.883 回答
4

除了 QuadTree 和 BSP 树建议之外，您还应该查找最近邻搜索。算法的选择取决于您添加到基础数据集的频率。如果您经常添加和删除，那么树解决方案会更好。如果数据更加静态，则最近邻搜索和 voronoi 图可以更快并且可以更好地扩展。

于 2009-05-08T06:42:39.307 回答
1

如果点集很少变化，您还可以考虑使用 voronoi 图。我不确定这是否有助于更快地找到第一个点，但它应该可以更容易地找到接下来的 999 个点。

于 2009-05-08T06:41:26.080 回答
0

我假设这些点在数据库或一些可搜索的索引位置？如果是这样，它应该很快。从给定点，您可以在 x 和 y 轴上有一个范围并获取该范围内的所有位置（即指定最左上角 x(a) 和 y(b) 以及最右下角 x(c) 和 y (d))。

然后查询其中 y >= b AND y <= d AND x >= a AND x <=c 的点。假设您在 x 和 y 坐标上分别有索引，这将很快。（假设原点是左上角的 0,0）。

然后，您可以将此范围增加（或减少，如果结果很大）z，直到结果集中的点数 >= 1000。通过一些试运行，您应该能够得出标准偏差和其他统计数字将帮助您确定要开始的矩形的大小。你的程序也可以根据它得到的结果来调整它自己。

一旦你有了粗略的数据集，它就可以通过非常简单的数学计算出每个点与源点之间的距离。

于 2009-05-08T05:50:03.707 回答
0

我知道如果你想要真正快速的结果，我知道它不是最快的，因为我从谷歌找到了这篇文章，我想我会添加我不久前以存储过程的形式使用的 SQL 解决方案。它查找靠近 a 坐标的位置并按距离返回它们。

我希望它可以帮助某人:)

CREATE PROCEDURE [dbo].[getstores] @lat float,  @lng float AS
DECLARE @radius float, @DegToRad float
SET @DegToRad = 57.29577951
SET @radius = 25000
SELECT TOP 10
    name
    ,sto_lat
    ,sto_lng
    ,postcode
    ,ROUND((ACOS((SIN(@lat/57.2958) * SIN(sto_lat/@DegToRad)) +(COS(@lat/@DegToRad) * COS(sto_lat/@DegToRad) *COS(sto_lng/@DegToRad - @lng/@DegToRad))))* 6387.7, 2) AS distance
FROM store
WHERE (sto_lat >= @lat - (@radius/111))
And (sto_lat <= @lat + (@radius/111))
AND (sto_lng >= @lng - (@radius/111))
AND (sto_lng <= @lng + (@radius/111))
AND (
     ISNUMERIC(sto_lat) = 1
    AND
    ISNUMERIC(sto_lat) = 1
)
ORDER BY distance

注意：我已经说过这不是解决这个问题的最佳解决方案，可能只是对于像我这样在谷歌上发现这个问题的人

于 2010-01-21T04:02:49.963 回答