根据两个点经纬度计算距离地理空间距离计算及优化 _地理

1.地理空间距离计算面临的挑战
打开美团app ，不管是筛选团购还是筛选商家，默认的排序项都是“离我最近”或者“智能排序”（如下图所示）。
不管是“离我最近”还是“智能排序” ，都涉及到计算用户位置与各个团购单子或者商家的距离（注：在智能排序中距离作为一个重要的参数参与排序打分）。以筛选商家为例，北京地区有5~6w个POI（本文将商家称之为POI），当用户进入商家页，请求北京全城+所有品类+离我最近/智能排序时，我们筛选服务需要计算一遍用户位置与北京全城所有POI的距离。
这种大量计算距离的场景十分消耗资源，从测试来看目前5w个点仅计算一遍距离就需要7ms ，而到100w的时候就需要140多ms ，随着数据的快速增长，筛选服务的性能将会非常堪忧。
如何优化距离的计算，进而提高计算速度、降低cpu使用率已经迫在眉睫。美团移动后台团购组在此方向上进行了些许探索，下文将分为4部分展开：1）地理空间距离计算原理；2）使用的距离计算公式；3）优化方案；4）实际应用。
2 地理空间距离计算原理
地理空间距离计算方法较多，目前我们使用的可以分为两类：1）球面模型，这种模型将地球看成一个标准球体，球面上两点之间的最短距离即大圆弧长，这种方法使用较广，在我们服务端被广泛使用；2）椭球模型，该模型最贴近真实地球，精度也最高，但计算较为复杂，目前客户端有在使用，但实际上我们的应用对精度的要求没有那么高。
下面着重介绍我们最常用的基于球面模型的地理空间距离计算公式，推导也只需要高中数学知识即可。
经纬度距离计算示意图
该模型将地球看成圆球，假设地球上有A(ja,wa) ， B(jb,wb)两点（注：ja和jb分别是A和B的经度， wa和wb分别是A和B的纬度）， A和B两点的球面距离就是AB的弧长， AB弧长=R*角AOB（注：角AOB是A跟B的夹角， O是地球的球心， R是地球半径，约为米）。如何求出角AOB呢？可以先求AOB的最大边AB的长度，再根据余弦定律可以求夹角。
如何求出AB长度呢？
1）根据经纬度，以及地球半径R ，将A、B两点的经纬度坐标转换成球体三维坐标；

文章插图
2）根据A、B两点的三维坐标求AB长度;
3）根据余弦定理求出角AOB;
4）AB弧长=R*角AOB.
3.使用的地理空间距离算法
目前美团团购app后台使用来筛选团购单子和商家，使用了工具包来计算地理空间距离，而提供了多种基于球面模型的地理空间距离的公式，其中一种就是上面我们推导的公式，称之为球面余弦公式。还有一种最常用的是公式，该公式是计算距离的默认公式，本质上是球面余弦函数的一个变换，之前球面余弦公式中有cos(jb-ja)项，当系统的浮点运算精度不高时，在求算较近的两点间的距离时会有较大误差，方法进行了某种变换消除了cos(jb-ja)项，因此不存在短距离求算时对系统计算精度的过多顾虑的问题。
1）公式代码
1
2
3
4
5
6
7
(,,,){
=Math.sin((lon1-lon2)*0.5);

根据两个点经纬度计算距离 地理空间距离计算及优化

根据两个点经纬度计算距离地理空间距离计算及优化