登录 立即注册

首页 > 绿虎论坛 > 电脑 > 讨论/求助 (发帖)

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

作者: @Ta

时间: 06-17 23:12发布,06-17 23:21修改

点击: 12947

目前方案

  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|隐藏机器人聊天)』

1.

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

(/@Ta/2024-06-17 23:15//)

2.

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

(/@Ta/2024-06-18 09:14//)

3.

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

(/@Ta/2024-06-18 09:49//)

4. @水木易安,有没有可能,楼主是算核爆的大佬,所以要精确的正圆
(/@Ta/2024-06-18 16:48//)

5.

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

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

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

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

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

(/@Ta/2024-06-19 20:40//)

6.

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

计算过程

已知半径为 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/2024-06-25 01:51//)

7.

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

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

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

(/@Ta/2024-06-25 01:53//)

8.

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

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

image.webp(35.38 KB)

(/@Ta/2024-06-25 02:08//)

9. 不是一条sql就能搞定的东西吗
(/@Ta/2024-06-26 01:09//)

10.

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

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

(/@Ta/2024-06-26 12:29//)

11. 大哥这个图是用什么工具画的
(/@Ta/2024-08-29 12:17//)

回复需要登录

12月13日 03:22 星期五

本站由hu60wap6华为CPU驱动

备案号: 京ICP备18041936号-1