工作需要,实现了一下Geo Hash算法。
尽量直接使用位操作,比网上常见的字符串判断位值得写法效率应该高一点。
TODO:循环的写法可以再优雅一点;注释可以再清晰一点。
import java.util.Arrays;
import java.util.BitSet;
import java.util.HashMap;
/**
* GeoHash编码
* 采用base32格式编码,5位一编码,存在经纬度精度不一致的情况,此时经度的经度优先
*
* @author pengjz <br>
* @version 1.0 <br>
* @description GeoHash <br>
* @date 2021/9/24 16:50 <br>
*/
public class GeoHash {
public static final int BASE_BIT_NUM = 5;
public static final double MIN_LAT = -90;
public static final double MAX_LAT = 90;
public static final double MIN_LON = -180;
public static final double MAX_LON = 180;
private final int hashLength;
/**
* 二进制长
*/
private final int bitLength;
/**
* 单独经纬度的长(单数取维度优先)
*/
private final int latLength;
/**
* 该精度下最小维度
*/
private double minLat;
/**
* 该精度下最小经度
*/
private double minLon;
private final static char[] 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'};
/**
* 定义编码映射关系
*/
final static HashMap<Character, Integer> LOOKUP = new HashMap<>();
/*
初始化编码映射内容
*/
static {
int i = 0;
for (char c : DIGITS) {
LOOKUP.put(c, i++);
}
}
/**
* 构造函数,参数为hash编码长度,长度越长经度越高
* 经度的经度优先
*
* @param hashLength hash编码长度
*/
public GeoHash(int hashLength) {
this.hashLength = hashLength;
this.latLength = (int) ((hashLength * BASE_BIT_NUM + 0.5) / 2 + 0.5);
this.bitLength = latLength * 2;
/*
* Hash编码长度,也就是hash表示的经度
*/
int scaleTime = hashLength * BASE_BIT_NUM / 2;
minLat = MAX_LAT - MIN_LAT;
for (int i = 0; i < scaleTime; i++) {
minLat /= 2.0;
}
minLon = MAX_LON - MIN_LON;
for (int i = 0; i < latLength; i++) {
minLon /= 2.0;
}
}
/**
* hash编码
*
* @param lat 纬度
* @param lon 经度
* @return geo hash
*/
public String encode(double lat, double lon) {
// 经纬度的位编码
BitSet latBits = getBits(lat, MIN_LAT, MAX_LAT);
BitSet lonBits = getBits(lon, MIN_LON, MAX_LON);
BitSet gpsBits = new BitSet();
/*
* 把位编码整合,上一步低精度在低位,高精度在高位,这里需要翻转
*/
for (int i = 0; i < latLength; i++) {
if (lonBits.get(i)) {
gpsBits.set(bitLength - i * 2 - 1);
}
if (latBits.get(i)) {
gpsBits.set(bitLength - i * 2 - 2);
}
}
// 对整合后的位进行编码
return bsToBase32(gpsBits);
}
public String encode(Gps gps) {
return encode(gps.getLat(), gps.getLon());
}
/**
* 将二进制编码转换为hash字符串
*
* @param bitSet 二进制编码
* @return hash字符串
*/
private String bsToBase32(BitSet bitSet) {
StringBuilder sb = new StringBuilder();
for (int i = bitLength; i >= BASE_BIT_NUM; i -= BASE_BIT_NUM) {
final BitSet aSet = bitSet.get(i - BASE_BIT_NUM, i);
final long[] longs = aSet.toLongArray();
if (longs.length > 0) {
sb.append(DIGITS[(int) longs[0]]);
} else {
sb.append(DIGITS[0]);
}
}
return sb.toString();
}
public Gps decode(String geoHash) {
/*
* 整合位编码
* 上一步高精度在高位,需要翻转
*/
BitSet bitSet = base32ToBs(geoHash);
BitSet latSet = new BitSet();
BitSet lonSet = new BitSet();
for (int i = 0; i < latLength; i++) {
// 偶数位,经度
if (bitSet.get(hashLength * BASE_BIT_NUM - 1 - i * 2)) {
lonSet.set(i);
}
// 奇数位,维度
if (hashLength * BASE_BIT_NUM - 2 - i * 2 >= 0
&& bitSet.get(hashLength * BASE_BIT_NUM - 2 - i * 2)) {
latSet.set(i);
}
}
// 算出来是格子靠近0,0的角,需要加挪到格子中间更准
return new Gps(
decodeLat(latSet, MIN_LAT, MAX_LAT) + minLat / 2,
decodeLat(lonSet, MIN_LON, MAX_LON) + minLon / 2
);
}
private double decodeLat(BitSet bitSet, double minLat, double maxLat) {
double mid = 0;
for (int i = 0; i < bitSet.length(); i++) {
mid = (minLat + maxLat) / 2;
if (bitSet.get(i)) {
minLat = mid;
} else {
maxLat = mid;
}
}
return mid;
}
private BitSet base32ToBs(String base32) {
BitSet bitSet = new BitSet();
for (int i = 0; i < this.hashLength; i++) {
int int32 = LOOKUP.get(base32.charAt(i));
for (int j = 0; j < BASE_BIT_NUM; j++) {
final int i1 = 1 << j;
if ((int32 & i1) == i1) {
bitSet.set((this.hashLength - 1 - i) * BASE_BIT_NUM + j);
}
}
}
return bitSet;
}
/**
* 获取经纬度的二进制编码
*
* @param lat 经度/纬度
* @param minLat 最小经度/维度
* @param maxLat 最大经度/维度
* @return 二进制编码
*/
private BitSet getBits(double lat, double minLat, double maxLat) {
BitSet bitSet = new BitSet(latLength);
for (int i = 0; i < latLength; i++) {
double mid = (minLat + maxLat) / 2;
if (lat >= mid) {
bitSet.set(i);
minLat = mid;
} else {
maxLat = mid;
}
}
return bitSet;
}
public String[][] getAroundGeoHash(Gps gps) {
return getAroundGeoHash(gps.getLat(), gps.getLon());
}
/**
* 根据hash code获取周围的hashcode
*
* @param hashCode 中心点的hashcode
* @return 以hashcode为中心点的周围九个格子的hashcode
*/
public String[][] getAroundGeoHash(String hashCode) {
Gps gps = this.decode(hashCode);
return getAroundGeoHash(gps.getLat(), gps.getLon());
}
/**
* 获取包含周围格子的geoHash字符串
* 返回值为二维数组,对应其方位
* 西北 正北 东北
* 正西 中间 正东
* 西南 正南 东南
*
* @param lat 中心点维度
* @param lon 中心点经度
* @return 周围的geoHash字符串
*/
public String[][] getAroundGeoHash(double lat, double lon) {
// 结果矩阵
String[][] result = new String[3][3];
// 北边格子的维度
double northLat = lat + minLat;
// 南边格子的维度
double southLat = lat - minLat;
// 东边各自的经度
double eastLon = lon + minLon;
// 西边各自的经度
double westLon = lon - minLon;
// 西北
result[0][0] = encode(northLat, westLon);
// 正北
result[0][1] = encode(northLat, lon);
// 东北
result[0][2] = encode(northLat, eastLon);
// 正西
result[1][0] = encode(lat, westLon);
// 正中
result[1][1] = encode(lat, lon);
// 正东
result[1][2] = encode(lat, eastLon);
// 西南
result[2][0] = encode(southLat, westLon);
// 正南
result[2][1] = encode(southLat, lon);
// 东南
result[2][2] = encode(southLat, eastLon);
return result;
}
/**
* 验证:http://www.geohash.cn/
*
* @param args 参数
*/
public static void main(String[] args) {
Gps gps = new Gps(37.384482, 76.649411);
System.out.println(gps.getLon() + "," + gps.getLat());
final GeoHash geoHash6 = new GeoHash(6);
String centerHash = geoHash6.encode(gps);
System.out.println(centerHash);
final String[][] aroundGeoHash6 = geoHash6.getAroundGeoHash(gps);
for (String[] geoHash : aroundGeoHash6) {
System.out.println(Arrays.toString(geoHash));
}
Gps gpsDecode = geoHash6.decode(centerHash);
System.out.println(gpsDecode.getLon() + "," + gpsDecode.getLat());
final GeoHash geoHash7 = new GeoHash(7);
centerHash = geoHash7.encode(gps);
System.out.println(centerHash);
final String[][] aroundGeoHash7 = geoHash7.getAroundGeoHash(gps);
for (String[] geoHash : aroundGeoHash7) {
System.out.println(Arrays.toString(geoHash));
}
gpsDecode = geoHash7.decode(centerHash);
System.out.println(gpsDecode.getLon() + "," + gpsDecode.getLat());
}
}
代码中用到得Gps类:
public class Gps {
double lat;
double lon;
public Gps(double lat, double lon) {
this.lat = lat;
this.lon = lon;
}
public double getLat() {
return lat;
}
public void setLat(double lat) {
this.lat = lat;
}
public double getLon() {
return lon;
}
public void setLon(double lon) {
this.lon = lon;
}
}
网友评论