现在几乎所有的O2O应用中都会存在 “按范围搜素、离我最近、显示距离” 等等基于位置的交互,那这样的功能是怎么实现的呢?
恰好近期在做相关需求,在此做下记录。
我们知道,经纬度是经度与纬度的合称组成一个坐标系统。
经度(longitude):是地球上一个地点离一根被称为本初子午线的南北方向走线以东或以西的度数,其数值在
0~180
度之间。纬度(latitude):是指某点与地球球心的连线和地球赤道面所成的线面角,其数值在
0~90
度之间。
一、数据库结构
DROP TABLE IF EXISTS `customer`; CREATE TABLE `customer` ( `id` int(11) unsigned NOT NULL auto_increment COMMENT '自增主键', `name` varchar(50) NOT NULL COMMENT '名称', `lon` double(9,6) NOT NULL COMMENT '经度', `lat` double(8,6) NOT NULL COMMENT '纬度', PRIMARY KEY (`id`) ) ENGINE=InnoDB AUTO_INCREMENT=8 DEFAULT CHARSET=utf8 COMMENT='商户表'; INSERT INTO `customer` VALUES ('1', '天津市区', '117.315575', '39.133462'); INSERT INTO `customer` VALUES ('2', '北京市区', '116.407999', '39.894073'); INSERT INTO `customer` VALUES ('3', '保定', '115.557124', '38.853490'); INSERT INTO `customer` VALUES ('4', '石家庄', '114.646458', '38.072369'); INSERT INTO `customer` VALUES ('5', '昌平区1', '116.367180', '40.009561'); INSERT INTO `customer` VALUES ('6', '海淀区2', '116.313425', '39.973078'); INSERT INTO `customer` VALUES ('7', '海淀区1', '116.329236', '39.987231');
二、计算两点之间的距离
公式如下,单位(米)
第一点经纬度:lng1、lat1
第二点经纬度:lng2、lat2
round(6378.138*2*asin(sqrt(pow(sin((lat1*pi()/180-lat2*pi()/180)/2),2)+cos(lat1*pi()/180)*cos(lat2*pi()/180)* pow(sin((lng1*pi()/180-lng2*pi()/180)/2),2)))*1000)
至于,公式如何成立的,网上有很多文章可以查看,不过多说明了。
1、MySQL 计算距离
知道了这个公式之后,然后我们开始用 mysql 自带的数学函数,计算 customer 表中,每个地方的距离。
传入参数 纬度 40.0497810000
经度 116.3424590000
SELECT *, ROUND( 6378.138 * 2 * ASIN( SQRT( POW( SIN( ( 40.0497810000 * PI() / 180 - lat * PI() / 180 ) / 2 ), 2 ) + COS(40.0497810000 * PI() / 180) * COS(lat * PI() / 180) * POW( SIN( ( 116.3424590000 * PI() / 180 - lon * PI() / 180 ) / 2 ), 2 ) ) ) * 1000 ) AS juli FROM customer ORDER BY juli ASC -- 参数变量,简化版 SET @lo = 116.366216; SET @la=39.939834; SELECT *, ROUND(6378.138*2*ASIN(SQRT(POW(SIN((@la*PI()/180-lat*PI()/180)/2),2)+COS(@la*PI()/180)*COS(lat*PI()/180)*POW(SIN((@lo*PI()/180-lon*PI()/180)/2),2)))*1000) AS juli FROM customer ORDER BY juli ASC
至此,我们就能清楚的查看到纬度 39.939834
,经度 116.366216
距离 customer 表中的每个地区的距离(单位 m)
如果要取公里,将后面的 * 1000
条件去掉即可。
2、Java 实现
公式成立,那么我们不仅可以使用 mysql 计算,也可以使用 java 函数来实现。
import java.text.DecimalFormat; /** * 根据两点间经纬度坐标(double值)计算两点间距离,LBS操作相关工具类 */ public class LBSKit { private static final double EARTH_RADIUS = 6378137; private static double rad(double d) { return d * Math.PI / 180.0; } /** * 根据两点间经纬度坐标(double值),计算两点间距离,保留两位小数 * * @param lat1 纬度 * @param lng1 经度 * @param lat2 纬度 * @param lng2 经度 * @return 距离:单位为千米 */ public static double distanceOfTwoPoints(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 = Math.round(s * 10000) / (double) 10000; double res = s / 1000; DecimalFormat df = new DecimalFormat("#.00"); return Double.parseDouble(df.format(res)); } /** * 根据两点间经纬度坐标(double值),计算两点间距离 * * @param lat1 纬度 * @param lng1 经度 * @param lat2 纬度 * @param lng2 经度 * @return 距离:单位为米 */ public static double getDistance(double lat1, double lng1, double lat2, double lng2) { double Lat1 = rad(lat1); double Lat2 = rad(lat2); double a = Lat1 - Lat2; double b = rad(lng1) - rad(lng2); double s = 2 * Math.asin(Math.sqrt(Math.pow(Math.sin(a / 2), 2) + Math.cos(Lat1) * Math.cos(Lat2) * Math.pow(Math.sin(b / 2), 2))); s = s * EARTH_RADIUS; s = Math.round(s * 10000) / 10000; return s; } public static void main(String[] args) { // 移动设备经纬度 double lng1 = 116.366216, lat1 = 39.939834; // 商户经纬度 double lng2 = 116.403909, lat2 = 39.918533; System.out.println("距离:" + getDistance(lat1, lng1, lat2, lng2) + " 米"); System.out.println("距离:" + distanceOfTwoPoints(lat1, lng1, lat2, lng2) + " 千米"); } }
执行结果
距离:3996.0 米 距离:4.0 千米
三、区间查找
除了可以自己根据公司来计算之外,还有很多的工具包可以使用。就比如下面的方式。
先利用工具包,获取到具体范围的经纬度,然后在 SQL 中,使用 between and
查询区间。
1、使用 spatial4j 来计算。
<!-- https://mvnrepository.com/artifact/org.locationtech.spatial4j/spatial4j --> <dependency> <groupId>org.locationtech.spatial4j</groupId> <artifactId>spatial4j</artifactId> <version>0.7</version> </dependency>
Java 示例
double lon = 116.312528, lat = 39.983733; // 经纬度 int radius = 5; // 千米 SpatialContext geo = SpatialContext.GEO; Rectangle rectangle = geo.getDistCalc().calcBoxByDistFromPt(geo.makePoint(lon, lat), radius * DistanceUtils.KM_TO_DEG, geo, null); System.out.println(rectangle.getMinX() + " - " + rectangle.getMaxX()); // 经度范围 116.25384300580865 - 116.37121299419135 System.out.println(rectangle.getMinY() + " - " + rectangle.getMaxY()); // 纬度范围 39.93876698161192 - 40.02869901838808
计算出经纬度范围之后,SQL是这样:
SELECT id, name FROM customer WHERE (lon BETWEEN ? AND ?) AND (lat BETWEEN ? AND ?);
为了查询速度,需要给 lon
、lat
两个字段建立联合索引:
INDEX `idx_lon_lat` (`lon`, `lat`)
2、Geohash 网格查找
Geohash 原理这里不再叙述,可查看文章了解:GeoHash核心原理解析
Geohash 算法是 把二维的经纬度编码转换成一维的字符串,它的特点是越相近的经纬度编码后越相似,所以可以通过前缀 like 的方式去匹配周围的商户。
customer 表要增加一个字段,来存储每个商户的 geohash 编码,并且建立索引。
CREATE TABLE `customer` ( `id` INT(11) UNSIGNED NOT NULL AUTO_INCREMENT COMMENT '自增主键', `name` VARCHAR(5) NOT NULL COMMENT '名称', `lon` DOUBLE(9,6) NOT NULL COMMENT '经度', `lat` DOUBLE(8,6) NOT NULL COMMENT '纬度', `geo_code` CHAR(12) NOT NULL COMMENT 'geohash编码', PRIMARY KEY (`id`), INDEX `idx_geo_code` (`geo_code`) ) ENGINE=InnoDB AUTO_INCREMENT=8 DEFAULT CHARSET=utf8 COMMENT='商户表';
新建了一个 geo_code
字段,那么这个字段的值该怎么维护呢?
spatial4j
也提供了一个工具类 GeohashUtils.encodeLatLon(lat, lon)
,默认精度是 12
位。在新增/修改时候,维护这个字段数据。这个存储做好后,就可以通过 geo_code
去搜索了。
double lng1 = 34.2675560000; double lat1 = 108.9534750000; System.out.println(GeohashUtils.encodeLatLon(lat1, lng1)); // uzbrgzbzgzvx 默认精度12 System.out.println(GeohashUtils.encodeLatLon(lat1, lng1, 5)); // uzbrg
有了已知的经纬度,计算 geo_code
,这时可以指定精度计算,那精度应该指定多长呢?
可以参考如下 geo_code 长度和距离的对照表:文章 Geohash-Cell_Dimensions
geohash length | width | height |
---|---|---|
1 | 5,009.4km | 4,992.6km |
2 | 1,252.3km | 624.1km |
3 | 156.5km | 156km |
4 | 39.1km | 19.5km |
5 | 4.9km | 4.9km |
6 | 1.2km | 609.4m |
7 | 152.9m | 152.4m |
8 | 38.2m | 19m |
9 | 4.8m | 4.8m |
10 | 1.2m | 59.5cm |
11 | 14.9cm | 14.9cm |
12 | 3.7cm | 1.9cm |
假设我们的需求是 1
公里范围内的商户,geo_code
的长度设置为 5
就可以了。
使用 GeohashUtils.encodeLatLon(lat, lon, 5)
,计算出经纬度的 geo_code
之后,SQL是这样:
SELECT id, name FROM customer WHERE geo_code LIKE CONCAT(?, '%');
这样会比区间查找快很多,并且得益于 geo_code
的相似性,可以对热点区域做缓存。但这样使用 geohash
还存在一个问题,geohash
最终是在地图上铺上了一个网格,每一个网格代表一个 geohash
值,当传入的坐标接近当前网格的边界时,用上面的搜索方式就会丢失它附近的数据。比如下图中,在绿点的位置搜索不到白家大院,绿点和白家大院在划分的时候就分到了两个格子中。
解决这个问题思路也比较简单,我们查询时,除了使用绿点的 geohash
编码进行匹配外,还使用周围 8
个网格的 geohash
编码,这样可以避免这个问题。那怎么计算出周围8个网格的geohash呢,可以使用 geohash-java 来解决。
<!--https://mvnrepository.com/artifact/ch.hsr/geohash--> <dependency> <groupId>ch.hsr</groupId> <artifactId>geohash</artifactId> <version>1.3.0</version> </dependency>
java 代码
// 移动设备经纬度 double lon = 116.312528, lat = 39.983733; GeoHash geoHash = GeoHash.withCharacterPrecision(lat, lon, 10); // 当前 System.out.println(geoHash.toBase32()); // N, NE, E, SE, S, SW, W, NW GeoHash[] adjacent = geoHash.getAdjacent(); for (GeoHash hash : adjacent) { System.out.println(hash.toBase32()); }
最终我们的sql变成了这样:
SELECT id, name FROM customer WHERE geo_code LIKE CONCAT(?, '%') OR geo_code LIKE CONCAT(?, '%') OR geo_code LIKE CONCAT(?, '%') OR geo_code LIKE CONCAT(?, '%') OR geo_code LIKE CONCAT(?, '%') OR geo_code LIKE CONCAT(?, '%') OR geo_code LIKE CONCAT(?, '%') OR geo_code LIKE CONCAT(?, '%') OR geo_code LIKE CONCAT(?, '%');
原来的 1
次查询变成了 9
次查询,性能肯定会下降,这里可以优化下。还用上面的需求场景,搜索 1
公里范围内的商户,从上面的表格知道,geo_code
长度为 5
时,网格宽高是 4.9KM
,用 9
个 geo_code
查询时,范围太大了,所以可以将 geo_code
长度设置为 6
,即缩小了查询范围,也满足了需求。
还可以继续优化,在存储 geo_code
时,只计算到 6
位,这样就可以将 sql 变成这样:
SELECT id, name FROM customer WHERE geo_code IN (?, ?, ?, ?, ?, ?, ?, ?, ?);
这样将前缀匹配换成了直接匹配,速度会提升很多。
3、过滤
上面两种搜索方式,都不是精确搜索,只是尽量缩小搜索范围,提升响应速度。所以需要在应用程序中做过滤,把距离大于 1
公里的商户过滤掉。计算距离同样使用 spatial4j
。
// 移动设备经纬度 double lng1 = 116.366216, lat1 = 39.939834; // 商户经纬度 double lng2 = 116.403909, lat2 = 39.918533; SpatialContext geo = SpatialContext.GEO; double distance = geo.calcDistance(geo.makePoint(lng1, lat1), geo.makePoint(lng2, lat2)) * DistanceUtils.DEG_TO_KM; System.out.println(distance); // KM
执行结果:3.9925058293343847
,同上面的 LBSKit
类代码 3996.0
米,4.0
千米,结果近乎一样。
过滤代码就不写了,遍历一遍搜索结果即可。
三、总结
全文的重点都在于搜索如何实现,更好的利用数据库的索引,两种搜索方式以百万数据量为分割线,第一种适用于百万以下,第二种适用于百万以上,未经过严格验证。可能有人会有疑问,过滤和排序都在应用层做,内存占用会不会很严重?这是个潜在问题,但大多数情况下不会。看我们大部分的应用场景,都是单一种类POI(Point Of Interest)的搜索,如酒店、美食、KTV、电影院等等,这种数据密度是很小,1公里内的酒店,能有多少家,50家都算多的,所以最终要看具体业务数据密度。本文没有分析原理,只讲了具体实现,有关分析的文章可以看参考链接。
四、相关工具
百度坐标拾取工具:http://api.map.baidu.com/lbsapi/getpoint/index.html
GPS经纬度查询工具:http://www.gpsspg.com/maps.htm
五、相关文章
未经允许请勿转载:程序喵 » MySQL 和 Java 根据经纬度查询最近距离,适用于所有数据库方案