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

[hereIsChen]

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

[wangxiaoaer]

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

[lhx2008]

缓存，近似计算

[hereIsChen]

@wangxiaoaer 弟弟服务器，而且不止之后会每天都做类似操作 n 次，真的怕吃不消

@lhx2008 能详细说下么？谢谢

[stoneabc]

模拟退火…？

[lhx2008]

@hereIsChen 如果你的输入数据是固定的，那就算一次把结果存起来。如果是部分固定的，那么就固定的和不固定的分开。如果是完全动态的，你这个应该算 TSP 问题，你可以找一些近似的算法，比如模拟退火

[opengps]

我虽然做了几年 LBS 服务，但不是正规军出身。我给你个我的野蛮办法：强制舍弃小数点精度法
做法就是，本来 6 位小数点，强制四舍五入为 4 位甚至更少来判断是否“相等”！

[opengps]

@opengps 然后，对于没有匹配到服务地址的人，进行一次更少位数的计算，到了一定位数之后才停止分配

[hereIsChen]

@opengps 算的是距离，而不是位置是否相等，最后都会用到计算两点间经纬度的算法，不过舍弃精度应该可以节省一点

[Akikiki]

先把地图划分为多个格子，判断人员和服务地址属于哪个格子，然后判断最近的格子（格子之间的距离可以提前算好），然后再找？最好用六边形的格子。。。

瞎说的哈~

[moyaka]

Geohash 可，比较简单而且性能好。

[wangxiaoaer]

我真不明白你为什么不试一试？

两点之间计算球面距离都特么现成的公式，里面用到的就特么几个三角函数，这点计算量有啥抗不抗的住的？？？？？？？？？

[hereIsChen]

@wangxiaoaer 问题是多对多的优化，而不只是计算两点间的距离，光通过经纬度计算距离当然简单

[opengps]

@hereIsChen 舍弃精度得出的相等，就是实际需求中的“就近”了。计算距离回到这个范围内进行遍历即可。然后单独处理下没有被分配的服务的点，单独派工就好

[opengps]

@wangxiaoaer 传统做法是一个点搜周边多个点，然后排序取最近。一旦需求变成多对多，那么结算量是指数增加的，所以会变得不适用

[aMR]

分格子的思路是对的，进阶一下就是四叉树

[Artemisr]

redis 提供了实现

[wangxiaoaer]

多对多怎么了？按照最笨的办法就是 m x n 次距离计算，10000 x 10000 次计算，纯计算耗时 3 秒，但是没有排序。

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

如果 m n 量很大，Postgresl + PostGIS + 空间索引 + （ sql + ST_Distance ） 搞定。

[rrfeng]

geo 距离搜索现成的算法现成的实现…
没什么好讨论的。

[wangxiaoaer]

https://jsfiddle.net/gy54dbpn/1/

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

我始终只想表达一个意思，单纯的距离计算没有想象中的耗费资源，你应该结合你的实际数据量，哪怕是用最笨的办法先试一试，如果真的发现遇到瓶颈了，再考虑优化。

[Tumblr]

如果能飞起来，感觉就是个大圆弧（ great circle ）。。。

[fightingZ]

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

[NingAnMe]

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

[SKHuang]

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
}