地理分区算法

Question

问题陈述:我有一个位置数据库，如果特定位置 X 在指定距离半径内，我想返回。简而言之，返回我搜索中 X 点半径范围内的所有城市。

此解决方案导致对数据库中的每个点进行强力搜索。但是，为了优化搜索，如果 map 被某些环分区，那么这意味着我在分区 0 中搜索，首先是最近的分区，然后移出直到我满意为止。

是否有一种算法可以有效地划分 map 并返回基于接近度的位置搜索。

简而言之:{A, B, C...} 是 map 中的点。对于空间中的这些点 {x}，找到 x 距离 d 内的所有点。

Answer 1

看看使用 R-tree或 R*-tree为此。

我不确定您打算使用哪种语言，但是 Boost.geometry有一个合理的 C++ 实现。

对于 python 有一个包装器 libspatialindex在 Rtree 中做同样的事情包。