我正在尝试找到解决以下问题的最佳方法:
问题
我在集合A中有(最多) 100,000个Lat/Lng点我在集合B中有(最多) 2000个Lat/Lng点
我需要找到集合B中的点与集合A中的点的最近邻居。
一旦他们配对-然后我需要计算他们的距离,这将是: 2000设置A点到2000设置B点。
这些点是“在内存中”,它们不是来自数据库-它们是系统中完成的其他计算的结果。
当前解决方案
使用Ruby语言中的KDTree实现,我可以创建一个与我所拥有的点相匹配的KDTree查找。然后,我在Ruby中使用半正弦方法来计算点配对时的距离。
KDtree编码:Ruby KDTree Code半正弦编码:Haversine Code
平台
我运行的是jruby --使用rails作为web框架。
问题
太慢了!像是慢了30到40秒...我认为主要的瓶颈是在KDtree,但点查找也需要很长时间(我认为)。在集合B中的数值越小,它就越快,但是集合B中的点数越多,它就会变得越快。
问题是
有人会想用不同的方式来做这件事吗?是不是我漏掉了什么。我认为Java库可能要快得多,但我该如何实现这一点,以及我该使用哪一个库( Java不强-我在JVM中使用Jruby编写多线程ruby代码)
发布于 2012-03-27 19:37:37
可以将信息持久化到数据库中吗?因为这样您就可以使用GeoKit,它利用了一个地理感知的数据库(MySQL、Postgres > 8.1等),所以您可以这样做:
Location.find(:all, :origin =>[37.792,-122.393], :within=>10, :order=>"distance asc")此外,您还可以找到两点之间的距离等。响应时间将更接近于DB查询,并且比您所看到的要快得多。
发布于 2012-03-27 19:57:23
这只是我脑海中的一个想法。如果您将经度/经度四舍五入到小数点后两位,则在1.11千米内所有带-的点都是相同的。有关更多详细信息,请参阅this。我不是100%确定,但它可能对你有效。对于极地附近的地区来说,这不会起作用,因为那里的经度会缩小。
要加快两个经纬度之间的距离计算,可以使用简单的距离公式而不是地理距离来计算欧几里得距离。这个距离并不准确,但会加快你的进程。
https://stackoverflow.com/questions/9888562
复制相似问题