写点什么

“查找附近的商铺”|Geohash+MySQL 实现地理位置筛选

  • 2022 年 8 月 01 日
  • 本文字数:7573 字

    阅读完需:约 25 分钟

“查找附近的商铺”|Geohash+MySQL实现地理位置筛选

一、背景

我们的⼀个早期项⽬使⽤了 MyBatis-Plus+MySQL,新⼀期需求中增加了按地理位置筛选最近的店铺列表的功能点。由于此需求相对简单,因此我们考虑在 MySQL 中实现地理位置筛选,并进⾏了以下探索。


二、方案一:MySQL 使⽤GEOMETRY/POINT 类型的字段存储地理位置

由于 MySQL5.6 及之后版本已基本⽀持空间位置扩展,对⼏何对象采⽤WKB 格式存储,WKT 格式展⽰。因此我们⾸先考虑在 MySQL 中使⽤ GEOMETRY/POINT 类型的字段存储地理位置(坐标)进⽽使⽤MySQL 提供的空间索引来进⾏地理位置筛选。

MySQL 中 GEOMETRY/POINT 类型的字段的编码格式为 WKB (Well-known Binary):


可以通过 WKT 值来创建 GEOMETRY/POINT 类型的值

我们的代码中所使⽤的坐标可以轻松转换为 WKT 格式,然后在 WKT 和 WKB 之间进⾏转换即可。

MySQL 使⽤如下⽅式转换 WKT 和 WKB:



衍⽣问题 让 MyBatis-Plus⽀持 GEOMETRY/POINT 类型

如果我们使⽤MyBatis,那么直接在 mapper⾥的 SQL 语句中使⽤这些转换函数即可,但是我们项⽬中使⽤了 MyBatis-Plus,尽量不⼿⼯编写 SQL。因此希望能让 MyBatis-Plus⽀持对坐标和 GEOMETRY/POINT 类型进⾏转换。我们进⾏了⼀些尝试,并最终得到了⽐较合适的解决⽅案。


2.1 尝试⼀ 

使⽤MyBatis TypeHandler 将坐标和 WKT 格式的字符串进⾏转

因为 MySQL⽀持这样的写法来插⼊/更新 GEOMETRY/POINT 类型的字段

INSERT INTO t1 (pt_col) VALUES(Point(1,2));
复制代码


既然 MyBatis 可以扩展 TypeHandler。那么我们可以将应⽤中的坐标类型转换为 WKT 格式的字符串,传到 MySQL 后应该是可以被处理的。但是实际上这⼀思路⽆法成功,因为在 JDBC 驱动中会报错⽆法将 String 转换成为 GEOMETRY/POINT 类型。


2.2 尝试二

使⽤MyBatis-Plus Interceptor 机制,改写 SQL 进⾏转换

例如:

/*应用中使用的SQL为 */update `t_table` set `geom`=?/* 在MyBatis-Plus Interceptor 把上面的SQL改写成 */update `t_table` set `geom`=geomfromtext(?)
复制代码


这个思路⼤致可以实现。但是实现起来⽐较⿇烦,有以下问题:

• 在需要转换的字段上需要通过注解或者其他⽅式进⾏标记

• 需要解析 SQL

• 需要处理字段名驼峰转下划线等细节

• 处理不了 GEOMETRY/POINT 有复杂操作的 SQL

• 查询,更新 SQL 需要分开处理

• 如果有符合条件的 SQL 不希望进⾏改写,还需要特殊处理

因此这个⽅案被放弃了。


2.3 尝试三

使⽤MyBatis TypeHandler 和 JTS 将坐标转换为 WKB 编码的字节

通过引⼊jts-core,我们可以在应⽤中直接将坐标转换为 WKB 编码的字节再传给 MySQL,也可以从 MySQl 中解读 WKB 编码的字节数组并解码为坐标。

import org.apache.ibatis.type.BaseTypeHandler;import org.apache.ibatis.type.JdbcType;
import java.sql.CallableStatement;import java.sql.PreparedStatement;import java.sql.ResultSet;import java.sql.SQLException;
/** * @author shishi on 21/3/22 */public class GeoPointHandler extends BaseTypeHandler<GeoPoint> {
@Override public void setNonNullParameter(PreparedStatement ps, int i, GeoPoint geoPoint, JdbcType jdbcType) throws SQLException { ps.setBytes(i, Converter.geoPointToBytes(geoPoint)); }
/** * Gets the nullable result. * * @param rs the rs * @param columnName Column name, when configuration <code>useColumnLabel</code> is <code>false</code> * @return the nullable result * @throws SQLException the SQL exception */ @Override public GeoPoint getNullableResult(ResultSet rs, String columnName) throws SQLException { return Converter.geoPointFromBytes(rs.getBytes(columnName)); }
@Override public GeoPoint getNullableResult(ResultSet rs, int columnIndex) throws SQLException { return Converter.geoPointFromBytes(rs.getBytes(columnIndex)); }
@Override public GeoPoint getNullableResult(CallableStatement cs, int columnIndex) throws SQLException { return Converter.geoPointFromBytes(cs.getBytes(columnIndex)); }}
复制代码


import lombok.extern.slf4j.Slf4j;import org.locationtech.jts.geom.*;import org.locationtech.jts.geom.impl.CoordinateArraySequence;import org.locationtech.jts.geom.impl.CoordinateArraySequenceFactory;import org.locationtech.jts.io.*;
import java.io.ByteArrayInputStream;import java.io.ByteArrayOutputStream;import java.util.List;import java.util.function.Function;import java.util.stream.Collectors;
@Slf4jpublic class Converter {
private static final GeometryFactory GEOMETRY_FACTORY = new GeometryFactory(new PrecisionModel(), 0, CoordinateArraySequenceFactory.instance());

private Converter() { }
/** * 通过jts,读取数据库中的geometry对象并转换为GeoPoint * * @param bytes 数据库中的原始流 * @return GeoPoint对象 */ public static GeoPoint geoPointFromBytes(byte[] bytes) { if (bytes == null) { return null; }
try (ByteArrayInputStream inputStream = new ByteArrayInputStream(bytes)) { byte[] sridBytes = new byte[4]; inputStream.read(sridBytes); int srid = ByteOrderValues.getInt(sridBytes, ByteOrderValues.LITTLE_ENDIAN);
GeometryFactory geometryFactory = GEOMETRY_FACTORY; if (srid != Constants.SPATIAL_REFERENCE_ID) { log.error("SRID different between database and application, db:{}, app:{}", srid, Constants.SPATIAL_REFERENCE_ID); geometryFactory = new GeometryFactory(new PrecisionModel(), srid, CoordinateArraySequenceFactory.instance()); }
WKBReader wkbReader = new WKBReader(geometryFactory); Geometry geometry = wkbReader.read(new InputStreamInStream(inputStream)); Point point = (Point) geometry; return new GeoPoint(point.getX(), point.getY()); } catch (Exception e) { log.error("failed when reading points from database.", e); return null; } }
/** * 通过jts,将GeoPoint对象转换为数据库能识别的数据流 * * @param geoPoint 原始GeoPoint对象 * @return mybatis可识别的byte[] */ public static byte[] geoPointToBytes(GeoPoint geoPoint) { if (geoPoint == null) { return new byte[0]; }
CoordinateArraySequence arraySequence = new CoordinateArraySequence( new Coordinate[]{new Coordinate(geoPoint.getX(), geoPoint.getY())}, 2); Point point = new Point(arraySequence, GEOMETRY_FACTORY);
try (ByteArrayOutputStream outputStream = new ByteArrayOutputStream()) { byte[] sridBytes = new byte[4]; ByteOrderValues.putInt(point.getSRID(), sridBytes, ByteOrderValues.LITTLE_ENDIAN); outputStream.write(sridBytes);
WKBWriter wkbWriter = new WKBWriter(2, ByteOrderValues.LITTLE_ENDIAN); wkbWriter.write(point, new OutputStreamOutStream(outputStream)); return outputStream.toByteArray(); } catch (Exception e) { log.error("failed when writing points to database.", e); return new byte[0]; } }

}
复制代码



方案一的缺陷

由于 MySQL 的空间索引函数存在以下缺陷,导致我们最终选择放弃⽅案⼀⾃⼰实现 Geohash。

三、方案二:⾃⼰实现 Geohash

Geohash 算法把⼀个空间点转化为⼀个哈希串。这个哈希串要求满⾜性质:前缀匹配相同的点,必然接近。这样才能在查询时,缩⼩查询范围。

我们在应⽤层⾯实现 Geohash 算法,计算地理位置的 Geohash 的值,存储在 MySQL 中,这样在 MySQL 中对 Geohash 进⾏字符串⽐较即可筛选地理位置。

Geohash 算法

1. 使⽤⼆分法,将坐标系划出矩形⽹格,将经度、纬度分别转化为⼆进制字符串。例如,⼀个 POINT(70, 10),第⼀步,70 在(-180, 180)中属于较⼤的⼀半,取 1;10 在(-90, 90)中属于较⼤的⼀半,取 1。第⼆步,70 在(0, 180)中属于较⼩的⼀半,取 0;10 在(0, 90)中属于较⼩的⼀半,取 0。第三步,70 在(0, 90)中属于较⼤的⼀半,取 1;10 在(0, 45)中属于较⼩的⼀半,取 0。第四步,70 在(45, 90)中属于较⼤的⼀半,取 1;10 在(0, 22.5)中属于较⼩的⼀半,取 0。这样就得到四位有效数字,经度 1011,纬度 1000。可以看到,四位有效数字等价于±22.5 经度±5.625 纬度。

2.使⽤⽪亚诺曲线降维。错位归并即可。1011、1000 -> 11001010,从经度拿 1,从纬度拿 1;再从经度拿 0,从纬度拿 0;从经度拿 1,从纬度拿 0;从经度拿 1,从纬度拿 0。这样得到⼀个⼆进制字符串。

3.使⽤base32 算法,每 5 位转化为⼀个 char。使⽤的字符为 0-9、b-z(去掉 a, i, l, o)。

4.得到的就是 MySQL 默认的 Geohash 了,等价于

st_Geohash(`geom`, i)
复制代码


注意第⼆个参数 i 代表最后结果的有效数字,最常⽤的 i=8,相当于 8*5/2=20 位经纬度有效数字。


Geohash 的应⽤和问题

Geohash 的特征是,其前若⼲位有效字符,代表了包括对象的⼀个更⼤的区域范围。事实上,每少 2 位有效字符,都相当于 2*5/2=5 次⼆分,也就是 2^5=32 倍⼤⼩的⼀个区域。因此在需要查询给定位置附近的地理位置时,使⽤Geohash 可以快速定位到⼀个范围内。

不过,Geohash 同时有⼀个明显的问题。

如图,假设我们希望找到离 a 最近的点。假设我们过滤的时候,使⽤了格⼦5 作为 Geohash 匹配,那么我们找到的最近值会是 e。但实际最近的点,应为隔壁格的 b 点。怎么办呢?

最容易想到的⽅法是再度扩⼤匹配格。但问题是,⽪亚诺曲线是有突变点的


对于某⼀个特定的点,扩增后的范围只能保证包裹它⾃⼰,⽆法确定扩增到何种地步才能包括全部九个相邻格。例如:上图对于格⼦1100,不管是扩⼤为 110、11 哪怕是 1,都⽆法覆盖其左边的 0110 格。

因此,需要⼿动获得周围⼋个格⼦的匹配信息,并使⽤OR 做匹配。这⼀点实现起来也不难,因为相邻格恰好是其横纵坐标±1 即可。

例如,0110 -> (01, 10),1100 -> (10, 10),01 + 1 = 10。获得之后,使⽤or 匹配即可。

给⼀段具体的 Geohash 算法实现:

import java.util.ArrayList;import java.util.BitSet;import java.util.HashMap;import java.util.List;import java.util.stream.Collectors;
public class GeohashUtils { /** * 一共八位,每位通过base32编码,实际相当于40位,经纬度各20位 */ private static final int GEO_HASH_MAX_LENGTH = 8 * 5; private static final char[] BASE32_DIGITS = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'j', 'k', 'm', 'n', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z'}; private static final HashMap<Character, Integer> BASE32_DIGIT_MAP = new HashMap<>(); static { int i = 0; for (char c : BASE32_DIGITS) { BASE32_DIGIT_MAP.put(c, i++); } } private GeohashUtils() {}
/** * * @param GeohashPartial 目标匹配段。即中间那个格子 * @return 供sql使用的匹配段。即所有九个格子 */ public static List<String> findNeighborGeohash(String GeohashPartial) { int accuracyLength = GeohashPartial.length(); // 精度必须为偶数,否则再忽略一位 String middle = ((accuracyLength & 1) == 0)? GeohashPartial: GeohashPartial.substring(0, accuracyLength - 1); long middleDecode = decodeBase32(middle); long[] middleCoordinates = ascensionUsingPeano(middleDecode); List<long[]> allCoordinates = findNeighborCoordinates(middleCoordinates);
return allCoordinates.stream().map(it -> encodeBase32(dimensionUsingPeano(it)) + '%') .collect(Collectors.toList()); }
/** * 解码Base32 */ private static long decodeBase32(String str) { StringBuilder buffer = new StringBuilder(); for (char c : str.toCharArray()) { int j = BASE32_DIGIT_MAP.get(c) + 32; buffer.append(Integer.toString(j, 2).substring(1) ); } return Long.parseLong(buffer.toString(), 2); } /** * 使用皮亚诺曲线升维 */ private static long[] ascensionUsingPeano(long number) { int i = 0; long x = 0; long y = 0; while (number > 0) { y += (number & 1) << i; number >>>= 1; x += (number & 1) << i; number >>>= 1; i++; } return new long[]{x, y}; }
/** * 找到八个相邻格 */ private static List<long[]> findNeighborCoordinates(long[] middle) { List<long[]> result = new ArrayList<>(9);
result.add(new long[]{middle[0] - 1, middle[1] - 1}); result.add(new long[]{middle[0] - 1, middle[1]}); result.add(new long[]{middle[0] - 1, middle[1] + 1}); result.add(new long[]{middle[0], middle[1] - 1}); result.add(middle); result.add(new long[]{middle[0], middle[1] + 1}); result.add(new long[]{middle[0] + 1, middle[1] - 1}); result.add(new long[]{middle[0] + 1, middle[1]}); result.add(new long[]{middle[0] + 1, middle[1] + 1}); return result; }
/** * 使用皮亚诺曲线降维 */ private static long dimensionUsingPeano(long[] coordinates) { int i = 0; long x = coordinates[0]; long y = coordinates[1]; long result = 0; while (i < GEO_HASH_MAX_LENGTH) { result += (y & 1) << (i++); result += (x & 1) << (i++); y >>>= 1; x >>>= 1; } return result; }
/** * 编码Base32 */ private static String encodeBase32(long number) { char[] buf = new char[65]; int charPos = 64; boolean negative = (number < 0); if (!negative){ number = -number; } while (number <= -32) { buf[charPos--] = BASE32_DIGITS[(int) (-(number % 32))]; number /= 32; } buf[charPos] = BASE32_DIGITS[(int) (-number)]; if (negative){ buf[--charPos] = '-'; } return new String(buf, charPos, (65 - charPos)); }
/** * 计算出一个坐标的Geohash */ public static String getGeohash(double longitude, double latitude) { BitSet longitudeBits = encodeBits(longitude, -180, 180); BitSet latitudeBits = encodeBits(latitude, -90, 90); StringBuilder sb = new StringBuilder(); int singleBits = GEO_HASH_MAX_LENGTH / 2;
for (int i = 0; i < singleBits; i++) { sb.append((longitudeBits.get(i))? '1': '0'); sb.append((latitudeBits.get(i))? '1': '0'); } return encodeBase32(Long.parseLong(sb.toString(), 2)); }
/** * 通过给定的上下限,使用二分法计算出二进制字符串 */ private static BitSet encodeBits(double number, double floor, double ceiling) { int singleBits = GEO_HASH_MAX_LENGTH / 2; BitSet buffer = new BitSet(singleBits); for (int i = 0; i < singleBits; i++) { double mid = (floor + ceiling) / 2; if (number >= mid) { buffer.set(i); floor = mid; } else { ceiling = mid; } } return buffer; }
}
复制代码


四、总结

⽬前 MySQL 对于空间位置扩展的实现还是⽐较薄弱的,实际应⽤中存在诸多限制。因此在相对⽐较简单的地理位置需求上可以考虑使⽤MySQL。好在 Geohash 算法也⽐较成熟,⾃⼰实现起来也不太⿇烦。

如果有⽐较复杂的地理位置需求,还是要考虑 ElasticSearch 等对地理位置查询⽀持的更好的数据库/第三⽅组件。


参考链接:

1.Geohash 算法原理及实现 - 简书

https://www.jianshu.com/p/2fd0cf12e5ba

2.mybatis 读写数据库 geometry 类型数据 - CodeAntenna

https://codeantenna.com/a/iBy59n9uan

3.Mybatis 拦截器实现 Geometry 类型数据存储与查询 - 掘金

https://juejin.cn/post/6857012707901341710


关于领创集团(Advance Intelligence Group)

领创集团成立于 2016 年,致力于通过科技创新的本地化应用,改造和重塑金融和零售行业,以多元化的业务布局打造一个服务于消费者、企业和商户的生态圈。集团旗下包含企业业务和消费者业务两大板块,企业业务包含 ADVANCE.AI 和 Ginee,分别为银行、金融、金融科技、零售和电商行业客户提供基于 AI 技术的数字身份验证、风险管理产品和全渠道电商服务解决方案;消费者业务 Atome Financial 包括亚洲领先的先享后付平台 Atome 和数字金融服务。2021 年 9 月,领创集团宣布完成超 4 亿美元 D 轮融资,融资完成后领创集团估值已超 20 亿美元,成为新加坡最大的独立科技创业公司之一。


往期回顾 BREAK AWAY

Spring data JPA 实践和原理浅析

如何解决海量数据更新场景下的 Mysql 死锁问题

企业级 APIs 安全实践指南 (建议初中级工程师收藏)

Cypress UI 自动化测试框架

serverless让我们的运维更轻松


发布于: 刚刚阅读数: 3
用户头像

智慧领创美好生活 2021.08.12 加入

AI技术驱动的科技集团,致力于以技术赋能为核心,通过科技创新的本地化应用,改造和重塑金融和零售行业,以多元化的业务布局打造一个服务于消费者、企业和商户的生态圈,带来个性化、陪伴式的产品服务和优质体验。

评论

发布
暂无评论
“查找附近的商铺”|Geohash+MySQL实现地理位置筛选_MySQL_领创集团Advance Intelligence Group_InfoQ写作社区