当前位置：网站首页>“查找附近的商铺”｜Geohash+MySQL实现地理位置筛选

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

2022-08-01 14:52:00 【InfoQ】

一、背景

我们的⼀个早期项⽬使⽤了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;

@Slf4j
public 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(&quot;SRID different between database and application, db:{}, app:{}&quot;, 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(&quot;failed when reading points from database.&quot;, 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(&quot;failed when writing points to database.&quot;, 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 亿美元，成为新加坡最大的独立科技创业公司之一。