如何快速查询,距用户 [15km, 20km) 远的地点?

@Ta 06-17 23:12发布,06-17 23:21修改 12075点击

目前方案

  1. 纬度分块(如 1km/块),所有地点按 (lat_chunk, lng, lat) 建索引。
  2. 逐纬度分块,计算东西两边,最小包含距离圆环◎的矩形。
  3. 利用索引,先粗筛出在矩形里的地点,再精细算距离,过滤掉 (矩形 - 圆环) 的地点。

下面是 [8km, 10km),纬度按 1km 分块后,计算出的示意图:

[8km,10km).svg(31.54 KB)

第二步算法(不用细看,下一节用到)

  1. 假设圆环最宽处,是用户所在纬度 user_lat
  2. 处在 user_lat_chunk 上方时,东边的矩形:
    • 左上角:15km 内圈,与块上边纬度交点
    • 右下角:20km 外圈,与块下边纬度交点
  3. 处在 user_lat_chunk 下方时,东边的矩形:
    • 左上角:15km 内圈,与块下边纬度交点
    • 右下角:20km 外圈,与块上边纬度交点
  4. 处在 user_lat_chunk 本块时,东边的矩形:
    • 左上角经度:块上下边,谁离 user_lat 远,取其纬度与 15km 内圈交点
    • 右下角经度:user_lat20km 外圈交点

碰到问题:遗漏地点

后面追踪画图,发现距离圆环◎不是标准(椭)圆(纬度高时,尤为明显)

下面是 [2900km, 3000km),纬度按 100km 分块后,计算出的示意图:

[2900km,3000km).svg(56 KB)

因此第二步里的假设出错,圆环最宽处,不是用户纬度,进而算错某些最小包含矩形了:

[2900km,3000km)放大.svg(11.59 KB)

请教如何修正,或其他更好方法?

回复列表(11|隐藏机器人聊天)
  • @Ta / 06-17 23:15 / /

    @老虎会游泳,为啥我上传 .svgz(压缩过的 .svg),无法显示呢。。

  • @Ta / 06-18 09:14 / /

    @无名啊,浏览器不支持该格式,可以上传普通svg,网站在传输时会自动进行gz压缩。

  • @Ta / 06-18 09:49 / /

    不用太刻意强迫自己必须选择一个圆形区域。直接根据经纬度选择一个矩形区域,性能更好,效果也差不多。
    除非你是做那种精确定位的,如果你是做一般的生活服务类的否则没必要太精确,因为假设 5km 的附近的兴趣点,但是在现实生活中,有的有河流、山地、交通管制等,需要绕行,实际行程可能更远或者更近。

  • @Ta / 06-18 16:48 / /
    @水木易安,有没有可能,楼主是算核爆的大佬,所以要精确的正圆
  • @Ta / 06-19 20:40 / /

    @水木易安,性能更好,是咋说呢?

    免去了一大堆圆环与纬度块交集计算?

    其实我感觉,这个就差临门一脚了。。

    @胡图图,没有可能。。听说这个 Haversine 公式,几十上百公里后,会有几百米误差。。

    想更精准的,要上 Vincenty 公式,能精确到 0.5 毫米。。但计算量太大了。。

  • @Ta / 06-25 01:51 / /

    @老虎会游泳@水木易安@胡图图,算个导数,再求零点,就纠正了。。

    计算过程

    已知半径为 R 的球体上,经纬度为 (\varphi_1,\theta_1) 的点 A_1(\varphi_2,\theta_2) 的点 A_2 间的距离 S 公式为:

    S = Rarccos(sin\theta_1 sin\theta_2 + cos\theta_1 cos\theta_2 cos(\varphi_2 - \varphi_1))

    A_2 在不同纬度上,与 A_1 间的经度差 \varphi_2-\varphi_1 的导函数为:

    \begin{align} {(\varphi_2 - \varphi_1)}' & = {arccos(\frac{cos(\frac{S}{R} )-sin\theta_1 sin\theta_2}{cos\theta_1 cos\theta_2})}' \\ & = \frac{sec\theta_2(cos(\frac{S}{R})sin\theta_2-sin\theta_1)}{cos\theta_1 \sqrt[]{1-\frac{(cos(\frac{S}{R})sec\theta_2-sin\theta_1tan\theta_2 )^{2}}{cos^{2}\theta_1}}} \end{align}

    求其零点,得到 A_1A_2 经度差 \varphi_2-\varphi_1 最大时,A_2 纬度 \theta_2

    \theta_2 = arcsin(\frac{sin\theta_1}{cos(\frac{S}{R})})

    结果图

    [2900km,3000km)纠正.svg(55.88 KB)

  • @Ta / 06-25 01:53 / /

    @老虎会游泳,公式不能正常显示?

    • [math] 的,复杂点则报错?

    • latex 的,直接不显示了。。

  • @Ta / 06-25 02:08 / /

    @老虎会游泳,另外,公式怎么居中显示呢?

    本地上看,是可以正常居中的?

    image.webp(35.38 KB)

  • @Ta / 06-26 01:09 / /
    不是一条sql就能搞定的东西吗
  • @Ta / 06-26 12:29 / /

    @淡然,请教一下,应该怎么写呢?

    速度如何?(比如,x 个地点里,找到 y 个地点,约 z 毫秒)

  • @Ta / 08-29 12:17 / /
    大哥这个图是用什么工具画的
添加新回复
回复需要登录