寻找附近点的算法？

Question

针对一个包含数百万个x,y坐标点的集合，如何快速查找距离某个位置最近的前1000个点？这里的“快速”指的是在家用电脑上约100毫秒内完成。

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

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

编辑：不需要精确，实际上可以相当不准确。如果前1000个实际上只是前2000个中的一些随机点，那也不是很重要。

编辑：点集很少发生变化。

- Bemmu

---

它必须是精确的吗？或者如果选择的1000个中有900个是最接近的1000个之一，这也可以吗？ - TonJ

这组点是固定的吗？在点集合发生变化之前，您会为多个不同的位置获取最接近的1000个点吗？ - Juha Syrjälä

Answer 1

使用四叉树如何？

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

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

这种方法的代码可能会变得相当复杂，因此您可以先尝试简单的网格，看看它是否足够快速。

- Juha Syrjälä

Answer 2

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

话虽如此，Quadtrees在实现上更容易，而且在大多数常见情况下非常有效。这是UPS在其路由算法中使用的方法，因为它的缺点在实践中并不会带来显著的问题，可能是因为城市倾向于分散在感兴趣的区域内。

- Kyle Simek

Answer 3

你想使用类似四叉树或R树的结构，这些都是多维索引结构。

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

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

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

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

- Tom

---

这些填充空间的曲线对我来说是一个非常新鲜的思考问题的视角，非常感谢！ - Bemmu

Answer 4

除了四叉树和BSP树的建议，您还应该查找最近邻搜索。算法的选择基于您向基础数据集添加的频率。如果您经常添加和删除，则树形解决方案更优。如果数据更静态，则最近邻搜索和Voronoi图可以更快且更好地扩展。

- SmacL

Answer 5

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

- Niki

Answer 6

我知道有人说过，如果你想要非常非常快的结果，它可能不是最快的。但是，通过谷歌搜索，我找到了这篇文章，我想分享一下我以前使用的 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

注意：我已经说明这不是最好的解决方案，仅仅是对于像我一样通过谷歌找到此问题的人可能有用。

- Doug

Answer 7

我假设这些点在数据库或某个可搜索的索引位置中？如果是这样，那么应该很快。从给定的点，您可以在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。通过一些试运行，您应该能够得出标准差和其他统计数字，这将帮助您确定要开始的矩形的大小。您的程序还可以根据其获得的结果来调整自身。

一旦您拥有了粗略的数据集，就可以很容易地计算出每个点与源点之间的距离。

- Rosstified

---

它们不在关系型数据库中，我记得阅读过像MySQL这样的关系型数据库在这种情况下只能使用一个索引。 - Bemmu

这听起来是个好主意。如果你正确设置了索引，数据库软件有一些很好的算法可以使这些查询变得非常快速。如果它们不在数据库中，请编写一个快速脚本将它们放入其中，并至少进行测试。这不一定是最快的解决方案，但很可能是最快实施的方案，毕竟你的时间比几个 CPU 周期更有价值，对吧？ - Kyle Simek

使用单一的1D索引无法高效地满足对两个不同属性的范围查询。关系型数据库并非神奇。 - Nick Johnson