ruby-on-rails - 在 Ruby 中计算大量 Lat/Lngs 到一组 2000 Lat/Lngs

Question

我正在尝试找到解决以下问题的最佳方法:

问题

我在集合 A 中有(最多)100,000 个纬度/经度点 我在 B 组中有(最多)2000 个纬度/经度点

我需要找到集合 B 中的点与集合 A 中的点最近的邻居。

一旦它们配对 - 然后我需要计算它们的距离，这将是: 2000 组 A 点到 2000 组 B 点。

这些点“在内存中”，它们不是来自数据库 - 它们是在系统中完成的其他计算的结果。

当前解决方案

使用 Ruby 中的 KDTree 实现，我可以创建一个 KDTree 查找来匹配我​​拥有的点。然后，我使用 Ruby 中的半正弦方法来计算点配对时的距离。

KDtree 代码:Ruby KDTree Code 半正弦代码:Haversine Code

平台

我正在运行 jruby - 以 rails 作为网络框架。

问题

它很慢!慢了 30 到 40 秒......我认为主要的瓶颈在 KDtree 中，但点查找也需要很长时间(我认为)。在 B 组中的分数越小，速度越快，但 B 组中的分数越高，它变得更快。

问题

有人会想出不同的做法吗？有什么我想念的吗？我认为 Java 库可能要快得多，但我将如何实现它，以及我会使用哪个(Java 不强 - 我使用 Jruby 在 JVM 中处理多线程 ruby​​ 代码)

Answer 1

是否可以将信息保存到数据库中？因为那样你就可以使用 GeoKit ，它利用地理感知数据库(MySQL、Postgres > 8.1 等)，因此您可以执行以下操作:

Location.find(:all, :origin =>[37.792,-122.393], :within=>10, :order=>"distance asc")

此外，您还可以找到两点之间的距离等。响应时间将更接近于数据库查询，并且比您所看到的要快得多。