算法寻找附近的点？

StackOverflow https://stackoverflow.com/questions/838344

题

考虑到与x，y坐标一套几百万点，什么是首选迅速从一个位置找到顶部1000最近点的算法？ “快速”在这里是指在家用计算机上大约100毫秒。

蛮力将意味着数以百万计做乘法，然后对它们进行排序。而即使是简单的Python应用程序可以做的，在不到一分钟，它仍然是一个交互式的应用程序过长。

的点的边界框将是已知的，因此将所述空间分隔成简单的网格将是可能的。然而，点分布不均匀有点，所以我怀疑最方格将是空的，然后突然它们中的一些将包含的点的一大部分。

编辑：没有确切，实际上可以说是相当不准确的。它不会是一个巨大的交易，如果顶部1000实际上是从顶部2000例如只是一些随机点。

编辑：设置点的很少改变

有帮助吗？

解决方案

如何使用四叉树？

您划分区域以矩形，如果区域具有点的密度低，矩形大，并且如果区域具有点的高密度，矩形将是小的。你递归每个矩形细分成4个个子矩形直到矩形是足够小或包含足够的几点。

然后就可以开始在附近位置矩形看着点，直到你找到了你1000点向外移动。

代码这有可能会有些复杂，所以也许你应该用简单的网格第一次尝试，看看它是否足够快。

其他提示

您想使用一个结构象一个四叉树或RTREE。这些是多维索引结构。

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

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

我不知道这个东西任何预先包装的实现。我最近实施自己RTREE 2名维只支持批量加载和检索（通过提供边界框）。

这里的一个缺点是，你的点都被包含在一个有限的区域。有知道有一些对于那些不是有限的空间工作空间填充曲线，但我不知道他们什么。

在除四叉树和BSP树的建议，你应该看看了邻近搜索 。算法的选择是基于你是如何经常添加到您的基本数据集。如果要添加和删除的时候，树上的解决方案优越。如果数据是多个静态，最近邻搜索和Voronoi图可以更快和更好的比例绘制的。

如果设定点的变化很少，你也可以考虑使用Voronoi图。我不知道是否可以帮助找到的第一的一点快，但它应该使人们更方便寻找下一个999点。

我假定的点是在数据库或一些可搜索的索引的地址？如果是的话它应该是相当快。从给定的点，你可以在x和y轴的范围，并获得该范围内的所有位置（即指定上最左边的角落X（a）和Y（b）和最底部右下角X（C）和y （d））。

然后做一个查询其中对于点，其中y> = B和Y <= d和X> = A和X <= C。这将是快假设你在x指数和y坐标seperatly。 （假设原点是0,0在左上角）。

然后，您可以用z增加（或减少，如果结果是巨大的）这个范围内，直到点的结果集内的数量> = 1000。通过一些试运行，你应该能够拿出一个标准偏差等统计的数字，这将帮助您确定矩形入手的大小。你的程序还可以调整它的这种自我基于它得到的结果。

一旦你的粗略数据设置其相当简单的数学到每个点和源点之间计算出的距离。

我知道它是说，通过看，如果你想真的真的快速的结果不是最快的，我发现这个职位从谷歌我想我补充一点，我用了一段时间以前，在一个存储过程的形式，我的SQL解决方案。它看起来由一个坐标位置接近和距离返回它们。

我希望它可以帮助别人：）

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

请注意：我已经说过，这是不是最好的解决办法这个问题只是也许有人谁发现这对谷歌和我一样

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