计算 一个点 附近的地方

问题

随着地理位置的应用普及,越来越多类似计算 一个点 附近的酒店的需求。比如,显示当前位置2000米范围内的 7 天酒店。

一般来说,在系统里都有一张表,存储了每个 7 天酒店的位置信息,表结构可以简化为三个字段 tb_location(ID, lng, lat),其中 lng:表示经度;lat:表示纬度,这两个字段都是数值类型的,且建了索引。

现在要把 2 公里范围内的 7 天酒店找出来,有的人写的 SQL 语句大概是这样的:
select id from tb_location where calc_distance(lng, lat, curLng, curLat) < 2000

这个语句的问题是没法利用索引,需要全表扫描,计算每一条记录与当前位置的距离,效率很低。

优化

用一张图来说明优化策略:
附近地点计算优化

2 公里范围是一个圆,这个圆的边界是由任意多的点确定的。但一个正方形的边界却是由四个点确定的,所以可以通过把要查找的地点限定在包围这个圆的最小正方形来缩小查找范围。

计算代码如下(收集自网络):

package net.coderbee.gps;

public class GPS {

     private final double EARTH_RADIUS = 6378.137; // 地球半径

     private static double rad(double d) {
          return d * Math.PI / 180.0; // 计算弧长
     }

     /**
     * 计算两个地理坐标之间的距离,
     * 
     * @param Lat1
     * @param Lng1
     * @param Lat2
     * @param Lng2
     * @return 距离,单位是米
     */
     public double calcDistance(double Lat1, double Lng1, double Lat2,
               double Lng2) {
          double radLat1 = rad(Lat1);
          double radLat2 = rad(Lat2);
          double a = radLat1 - radLat2;
          double b = rad(Lng1) - rad(Lng2);
          double s = 2 * Math.asin(Math.sqrt(Math.pow(Math.sin(a / 2), 2)
                    + Math.cos(radLat1) * Math.cos(radLat2)
                    * Math.pow(Math.sin(b / 2), 2)));
          s = s * EARTH_RADIUS;
          s = s * 1000; // 换算成米
          return s;

     }

     /**
     * 计算最小正方形的四个经纬度值
     * 
     * @param lng
     *            经度
     * @param lat
     *            纬度
     * @param distance
     *            距离
     * @return
     */
     public static double[] getRectangle(double lng, double lat, long distance) {
          float delta = 111000;

          double minLng = lng - distance
                    / Math.abs(Math.cos(Math.toRadians(lat)) * delta);
          double maxLng = lng + distance
                    / Math.abs(Math.cos(Math.toRadians(lat)) * delta);
          double minLat = lat - (distance / delta);
          double maxLat = lat + (distance / delta);
          return new double[] { minLng, minLat, maxLng, maxLat };
     }
}

如果需要可以转换为 SQL 的函数。

那么查询的 SQL 语句可以优化为:

select id from (
     select loc.id, calc_distance(loc.lng,  loc.lat,  :curLng,  :curLat) distance
     from tb_location loc 
     where loc.lng >= :minLng and loc.lng < :maxLng 
          and loc.lat >= :minLat and loc.lat < :maxLat
) t 
where t.distance < 2000

发表评论

电子邮件地址不会被公开。 必填项已用*标注

This site uses Akismet to reduce spam. Learn how your comment data is processed.