如何快速查询,距用户 [15km, 20km) 远的地点?
目前方案
- 纬度分块(如
1km/块),所有地点按(lat_chunk, lng, lat)建索引。 - 逐纬度分块,计算东西两边,最小包含距离圆环◎的矩形。
- 利用索引,先粗筛出在矩形里的地点,再精细算距离,过滤掉
(矩形 - 圆环)的地点。
下面是 [8km, 10km),纬度按 1km 分块后,计算出的示意图:
第二步算法(不用细看,下一节用到)
- 假设圆环最宽处,是用户所在纬度
user_lat。 - 处在
user_lat_chunk上方时,东边的矩形:- 左上角:
15km内圈,与块上边纬度交点 - 右下角:
20km外圈,与块下边纬度交点
- 左上角:
- 处在
user_lat_chunk下方时,东边的矩形:- 左上角:
15km内圈,与块下边纬度交点 - 右下角:
20km外圈,与块上边纬度交点
- 左上角:
- 处在
user_lat_chunk本块时,东边的矩形:- 左上角经度:块上下边,谁离
user_lat远,取其纬度与15km内圈交点 - 右下角经度:
user_lat与20km外圈交点
- 左上角经度:块上下边,谁离
碰到问题:遗漏地点
后面追踪画图,发现距离圆环◎不是标准(椭)圆(纬度高时,尤为明显)。
下面是 [2900km, 3000km),纬度按 100km 分块后,计算出的示意图:
因此第二步里的假设出错,圆环最宽处,不是用户纬度,进而算错某些最小包含矩形了:


