V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX 提问指南
hereIsChen
V2EX  ›  问与答

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

  •  
  •   hereIsChen · 2019-12-16 11:00:54 +08:00 · 3440 次点击
    这是一个创建于 1802 天前的主题,其中的信息可能已经有所发展或是发生改变。
    有两组数据,第一组为服务人员的经纬度地址,第二组为服务地址的经纬度地址,怎么计算出最近的,如果每个都要单独算感觉服务器受不住,有啥比较好的优化方式
    23 条回复    2019-12-16 18:05:14 +08:00
    wangxiaoaer
        1
    wangxiaoaer  
       2019-12-16 11:08:10 +08:00   ❤️ 1
    你:感觉服务器承受不住。
    服务器:你是不是想太多了?
    吃瓜群众:你丫先试试然后再去畅想可以吗?
    lhx2008
        2
    lhx2008  
       2019-12-16 11:09:55 +08:00 via Android   ❤️ 1
    缓存,近似计算
    hereIsChen
        3
    hereIsChen  
    OP
       2019-12-16 11:31:39 +08:00
    @wangxiaoaer 弟弟服务器,而且不止之后会每天都做类似操作 n 次,真的怕吃不消

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

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

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

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

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

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

    我始终只想表达一个意思,单纯的距离计算没有想象中的耗费资源,你应该结合你的实际数据量,哪怕是用最笨的办法先试一试,如果真的发现遇到瓶颈了,再考虑优化。
    Tumblr
        20
    Tumblr  
       2019-12-16 13:45:59 +08:00
    如果能飞起来,感觉就是个大圆弧( great circle )。。。
    fightingZ
        21
    fightingZ  
       2019-12-16 14:10:51 +08:00
    没理解错的话,这个问题不应该就是多源点寻找最短路径吗
    NingAnMe
        22
    NingAnMe  
       2019-12-16 17:55:38 +08:00
    使用 KDtree。
    1. 适合多维数据找最近。使用数量少的一组构建树,对数量多的一组查最近点。
    2. 如果有一组数据不变,可以把数保存下来。
    不会贴图,你自己查一下复杂度吧。
    SKHuang
        23
    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
    }
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   3659 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 26ms · UTC 00:13 · PVG 08:13 · LAX 16:13 · JFK 19:13
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.