计算许多地理点之间距离的算法

Question

我有一个矩阵有大约1000个地理空间点(经度,纬度),我试图找到1KM范围内的点.

注意:"这些点是动态的,想象1000辆车正在移动,所以我必须每隔几秒重新计算所有距离"

我做了一些搜索并阅读了像(Floyd-Warshall)这样的Graph算法来解决这个问题,我最终得到了很多关键词,现在我有点迷失了.我正在考虑性能,因为搜索半径很短,我不会考虑地球的曲率.

基本上,似乎我必须计算每个点到每个其他点之间的距离,然后从矩阵中的每个点开始对距离进行排序,并获得其范围内的点.因此,如果我有1000个坐标,我必须执行此过程(1000 ^ 2-1000)次,我不相信这是最佳解决方案.谢谢.

Answer 1

如果你制作一个1km间距网格的模型:

  0   1    2    3
 ___|____|____|____
0   |    |    |
   c|   b|a   |   d
 ___|____|____|____
1   |    |    |
    |    |f   |
 ___|e___|____|____
2   |    |g   | 

让我们假设你的出发点是.如果您的网格大小为1千米,则1公里范围内的点必须位于同一个小区或8个邻居之一(点b,d,e,f).

每个其他单元格都可以忽略(c,g).

虽然d与c的距离几乎相同,但c可以提前下降,因为有2个障碍可以穿越,而a和d位于其边界的相对区域,因此距离彼此近2 km.

对于元素的早期删除,您可以排除,只需检查坐标的x或y部分即可.由于a属于(0,2),如果x为0或更小,或> 3,则该点已经超出范围.

仅过滤少数候选人后,您可以使用详尽的搜索.

Answer 2

就您而言，您应该查看 GeoHash ，它允许您快速查询给定距离内的坐标。

仅供参考，MongoDB 在内部使用 geohash，并且性能非常出色。