##4.2 简化距离计算公式方法
1）基本思路
我们的业务场景仅仅是在一个城市范围内进行距离计算，也就是说两个点之间的距离一般不会超过200多千米。由于范围小，可以认为经线和纬线是垂直的，如图所示，要求A（116.8，39,78）和B（116.9，39.68）两点的距离，我们可以先求出南北方向距离AM，然后求出东西方向距离BM，最后求矩形对角线距离，即sqrt(AMAM + BMBM)。

南北方向AM = R纬度差Math.PI/180.0；
东西方向BM = R经度差Cos<当地纬度数* Math.PI/180.0>
这种方式仅仅需要计算一次cos函数。

public static double distanceSimplify(double lat1, double lng1, double lat2, double lng2, double[] a) {      double dx = lng1 - lng2; // 经度差值      double dy = lat1 - lat2; // 纬度差值      double b = (lat1 + lat2) / 2.0; // 平均纬度      double Lx = toRadians(dx) * 6367000.0* Math.cos(toRadians(b)); // 东西距离      double Ly = 6367000.0 * toRadians(dy); // 南北距离      return Math.sqrt(Lx * Lx + Ly * Ly);  // 用平面的矩形对角距离公式计算总距离     } } 

我们对这个方法的有效性和性能进行验证。
1.1）有效性验证
我们首先检验这种简化是否能满足我们应用的精度，如果精度较差将不能用于实际生产环境。

我们的方法叫distanceSimplify，lucene的方法叫distHaversineRAD。下表是在不同尺度下两个方法的相差情况。

可以看到两者在百米、千米尺度上几乎没有差别，在万米尺度上也仅有分米的差别，此外由于我们的业务是在一个城市范围内进行筛选排序，所以我们选择了北京左下角和右上角两点进行比较，两点相距有260多千米，两个方法差别17m。从精度上看该优化方法能满足我们应用需求。

1.2）性能验证

2）进一步优化
我们看到这里计算了一次cos这一三角函数，如果我们能消除此三角函数，那么将进一步提高计算效率。
如何消除cos三角函数呢？

采用多项式来拟合cos三角函数，这样不就可以将三角函数转换为加减乘除了嘛！

首先决定多项式的最高次数，次数为1和2显然都无法很好拟合cos函数，那么我们选择3先尝试吧，注：最高次数不是越多越好，次数越高会产生过拟合问题。

使用org.apache.commons.math3这一数学工具包来进行拟合。中国的纬度范围在10~60之间，即我们将此区间离散成Length份作为我们的训练集。

public static double[] trainPolyFit(int degree, int Length){     PolynomialCurveFitter polynomialCurveFitter = PolynomialCurveFitter.create(degree);     double minLat = 10.0; //中国最低纬度     double maxLat = 60.0; //中国最高纬度     double interv = (maxLat - minLat) / (double)Length;     List<WeightedObservedPoint> weightedObservedPoints = new ArrayList<WeightedObservedPoint>();     for(int i = 0; i < Length; i++) {         WeightedObservedPoint weightedObservedPoint = new WeightedObservedPoint(1,  minLat + (double)i*interv, Math.cos(toRadians(x[i])));         weightedObservedPoints.add(weightedObservedPoint);      }     return polynomialCurveFitter.fit(weightedObservedPoints); }   public static double distanceSimplifyMore(double lat1, double lng1, double lat2, double lng2, double[] a) {      //1) 计算三个参数      double dx = lng1 - lng2; // 经度差值      double dy = lat1 - lat2; // 纬度差值      double b = (lat1 + lat2) / 2.0; // 平均纬度      //2) 计算东西方向距离和南北方向距离(单位：米)，东西距离采用三阶多项式      double Lx = (a[3] * b*b*b  + a[2]* b*b  +a[1] * b + a[0] ) * toRadians(dx) * 6367000.0; // 东西距离      double Ly = 6367000.0 * toRadians(dy); // 南北距离      //3) 用平面的矩形对角距离公式计算总距离      return Math.sqrt(Lx * Lx + Ly * Ly); } 

我们对此优化方法进行有效性和性能验证。
2.1）有效性验证
我们的优化方法叫distanceSimplifyMore，lucene的方法叫distHaversineRAD，下表是在不同尺度下两个方法的相差情况。

可以看到在百米尺度上两者几乎未有差别，在千米尺度上仅有分米的区别，在更高尺度上如72千米仅有5.6m米别，在264千米也仅有8.1米区别，因此该优化方法的精度能满足我们的应用需求。

2.2）性能验证

#5 实际应用
坐标转换方法和简化距离公式方法性能都非常高，相比lucene使用的Haversine算法大大提高了计算效率，然而坐标转换方法存在一些缺点：
a）坐标转换后的数据不能被直接用于空间索引。lucene可以直接对经纬度进行geohash空间索引，而通过空间转换变成三维数据后不能直接使用。我们的应用有附近范围筛选功能（例如附近5km的团购单子），通过geohash空间索引可以提高范围筛选的效率；
b）坐标转换方法增大内存开销。我们会将坐标写入倒排索引中，之前坐标是2列（经度和纬度），现在变成3列（x,y,z），在使用中我们往往会将这数据放入到cache中，因此会增大内存开销；
c）坐标转换方法增大建索引开销。此方法本质上是将计算从查询阶段放至到索引阶段，因此提高了建索引的开销。

基于上述原因我们在实际应用中采用简化距离公式方法（通过三次多项式来拟合cos三角函数），此方法在团购筛选和商家筛选的距离排序、智能排序中已经开始使用，与之前相比，筛选团购时北京全城美食品类距离排序响应时间从40ms下降为20ms。

阅读全文……

发表评论

IT瘾于2016年3月27日 上午03时34分00秒发布 #