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

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

V2EX 提问指南

这是一个创建于 1839 天前的主题，其中的信息可能已经有所发展或是发生改变。

有两组数据，第一组为服务人员的经纬度地址，第二组为服务地址的经纬度地址，怎么计算出最近的，如果每个都要单独算感觉服务器受不住，有啥比较好的优化方式

地址

经纬度

优化

纬度

23 条回复 • 2019-12-16 18:05:14 +08:00

wangxiaoaer

2019-12-16 11:08:10 +08:00

你：感觉服务器承受不住。
服务器：你是不是想太多了？
吃瓜群众：你丫先试试然后再去畅想可以吗？

lhx2008

2019-12-16 11:09:55 +08:00 via Android

缓存，近似计算

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 via Android

@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 via Android

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 via Android

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 ）。。。

fightingZ

2019-12-16 14:10:51 +08:00

没理解错的话，这个问题不应该就是多源点寻找最短路径吗

NingAnMe

2019-12-16 17:55:38 +08:00

使用 KDtree。
1. 适合多维数据找最近。使用数量少的一组构建树，对数量多的一组查最近点。
2. 如果有一组数据不变，可以把数保存下来。
不会贴图，你自己查一下复杂度吧。

SKHuang

2019-12-16 18:05:14 +08:00

func GetDistance(lat1 float64, lng1 float64, lat2 float64, lng2 float64) float64 {
var (
radLat1 float64
radLat2 float64
a float64
b float64
s float64
)
radLat1 = GetRad(lat1)
radLat2 = GetRad(lat2)
a = radLat1 - radLat2
b = GetRad(lng1) - GetRad(lng2)
s = 2 * earth_padius * math.Asin(math.Sqrt(math.Pow(math.Sin(a/2), 2)+math.Cos(radLat1)*math.Cos(radLat2)*math.Pow(math.Sin(b/2), 2)))
return s
}

func GetRad(d float64) float64 {
return d * math.Pi / 180.0
}