多个点经纬度距离最近算法,怎么优化?

2019-12-16 11:00:54 +08:00
 hereIsChen
有两组数据,第一组为服务人员的经纬度地址,第二组为服务地址的经纬度地址,怎么计算出最近的,如果每个都要单独算感觉服务器受不住,有啥比较好的优化方式
3475 次点击
所在节点    问与答
23 条回复
wangxiaoaer
2019-12-16 11:08:10 +08:00
你:感觉服务器承受不住。
服务器:你是不是想太多了?
吃瓜群众:你丫先试试然后再去畅想可以吗?
lhx2008
2019-12-16 11:09:55 +08:00
缓存,近似计算
hereIsChen
2019-12-16 11:31:39 +08:00
@wangxiaoaer 弟弟服务器,而且不止之后会每天都做类似操作 n 次,真的怕吃不消

@lhx2008 能详细说下么?谢谢
stoneabc
2019-12-16 11:37:08 +08:00
模拟退火…?
lhx2008
2019-12-16 11:42:39 +08:00
@hereIsChen 如果你的输入数据是固定的,那就算一次把结果存起来。如果是部分固定的,那么就固定的和不固定的分开。如果是完全动态的,你这个应该算 TSP 问题,你可以找一些近似的算法,比如模拟退火
opengps
2019-12-16 11:45:37 +08:00
我虽然做了几年 LBS 服务,但不是正规军出身。我给你个我的野蛮办法:强制舍弃小数点精度法
做法就是,本来 6 位小数点,强制四舍五入为 4 位甚至更少来判断是否“相等”!
opengps
2019-12-16 11:46:47 +08:00
@opengps 然后,对于没有匹配到服务地址的人,进行一次更少位数的计算,到了一定位数之后才停止分配
hereIsChen
2019-12-16 11:50:06 +08:00
@opengps 算的是距离,而不是位置是否相等,最后都会用到计算两点间经纬度的算法,不过舍弃精度应该可以节省一点
Akikiki
2019-12-16 11:50:35 +08:00
先把地图划分为多个格子,判断人员和服务地址属于哪个格子,然后判断最近的格子(格子之间的距离可以提前算好),然后再找?最好用六边形的格子。。。

瞎说的哈~
moyaka
2019-12-16 11:54:06 +08:00
Geohash 可,比较简单而且性能好。
wangxiaoaer
2019-12-16 11:58:43 +08:00
我真不明白你为什么不试一试?

两点之间计算球面距离都特么现成的公式,里面用到的就特么几个三角函数,这点计算量有啥抗不抗的住的?????????
hereIsChen
2019-12-16 12:00:41 +08:00
@wangxiaoaer 问题是多对多的优化,而不只是计算两点间的距离,光通过经纬度计算距离当然简单
opengps
2019-12-16 12:33:02 +08:00
@hereIsChen 舍弃精度得出的相等,就是实际需求中的“就近”了。计算距离回到这个范围内进行遍历即可。然后单独处理下没有被分配的服务的点,单独派工就好
opengps
2019-12-16 12:34:19 +08:00
@wangxiaoaer 传统做法是一个点搜周边多个点,然后排序取最近。一旦需求变成多对多,那么结算量是指数增加的,所以会变得不适用
aMR
2019-12-16 12:56:52 +08:00
分格子的思路是对的,进阶一下就是四叉树
Artemisr
2019-12-16 13:07:28 +08:00
redis 提供了实现
wangxiaoaer
2019-12-16 13:16:37 +08:00
多对多怎么了?按照最笨的办法就是 m x n 次距离计算,10000 x 10000 次计算,纯计算耗时 3 秒,但是没有排序。

如果你的 m n 量级不够大,这种方式完全不用担心。

如果 m n 量很大,Postgresl + PostGIS + 空间索引 + ( sql + ST_Distance ) 搞定。
rrfeng
2019-12-16 13:18:47 +08:00
geo 距离搜索现成的算法现成的实现…
没什么好讨论的。
wangxiaoaer
2019-12-16 13:37:45 +08:00
https://jsfiddle.net/gy54dbpn/1/

随手做的一个测试,不是很严谨,刚忘记贴了。

我始终只想表达一个意思,单纯的距离计算没有想象中的耗费资源,你应该结合你的实际数据量,哪怕是用最笨的办法先试一试,如果真的发现遇到瓶颈了,再考虑优化。
Tumblr
2019-12-16 13:45:59 +08:00
如果能飞起来,感觉就是个大圆弧( great circle )。。。

这是一个专为移动设备优化的页面(即为了让你能够在 Google 搜索结果里秒开这个页面),如果你希望参与 V2EX 社区的讨论,你可以继续到 V2EX 上打开本讨论主题的完整版本。

https://www.v2ex.com/t/629390

V2EX 是创意工作者们的社区,是一个分享自己正在做的有趣事物、交流想法,可以遇见新朋友甚至新机会的地方。

V2EX is a community of developers, designers and creative people.

© 2021 V2EX