Uber开源H3算法（地理索引）的工程化实现

何为地理索引：

在工程领域，尤其是电商平台，外卖平台，打车平台频繁使用的比如某一范围内的商品，商家功能等。会使用到某一范围比如10Km范围内的所有商家场景。那么如何更加方便，简单的实现这样的场景呢？

常用的有：基于GeoHash原理的实现，Google-S2 空间索引的实现，Geomesa Z3的实现，Uber H3索引的实现等；

但是不同的使用场景，每个不同公司可以按照需求的不同选择自己所需的实现技术栈。本文将会结合我们已经在工程领域中实现的Uber H3索引进行详细讲解。

1.H3索引介绍

H3索引，由Uber公司开源。基础为C语言编写的算法；h3-java为包装JNI的通用接口抽象；（由于我们的主要技术语言为java，本文将着重介绍我们关于java方面的使用场景）

官方介绍文档手册：https://uber.github.io/h3/#/documentation/overview/introduction

开源代码地址：https://github.com/uber/h3

java版本开源代码地址：https://github.com/uber/h3-java

H3地理空间索引系统是具有分级线性索引索引的球体的多精度六角形平铺。

H3核心库对纬度/经度坐标和之间的转换提供了函数H3的地理空间索引。

2.当前阶段Uber开源的H3工具包能够对外提供的服务：

给定纬度/经度点，找到特定分辨率下包含H3单元的索引

给定H3索引，找到纬度/经度单元中心

给定H3索引，确定纬度/经度坐标中的单元边界

其他等

3.重要的参考指标：

指标如下：

核心指标介绍： Resolution （精度），正六边形覆盖面积，正六边形变长，每个精度对应的索引个数；

4. 转换下思维方式：

也就是从单纯的点到点覆盖范围计算，查询效率低下，而Uber H3通过为全球地理位置定制了一套，正六边形构成的覆盖图，每个覆盖图有一个唯一Id，通过空间换时间的思想，让点对点的查询变成了索引结构的匹配查询。实现了在没有巨大误差前提下的高效查询。

5.工程化实践介绍：

使用依赖如下：

<dependency>

<groupId>com.uber</groupId>

<artifactId>h3</artifactId>

<version>3.4.0</version>

</dependency>

初始化H3的计算对象和通过经纬度获得H3索引：

private static void init() {

try {

h3 = H3Core.newInstance();

}catch (IOException e) {

logger.error("H3Instance init failed", e);

}

}

public static String getH3IndexByCoordinate(double latitude, double longitude, H3ResolutionEnum resolution) {

//param validate 经纬度参数的合法校验

if (!isValidCoordinate(latitude, longitude)) {

logger.warn("getH3IndexByCoordinate param is invalid,coordinate:{},{}", longitude, latitude);

throw new IllegalArgumentException();

}

//execute h3 index calculate 执行通过经纬度选择的精度，计算H3索引逻辑

try {

if (h3 == null) {

init();

}

// 得到对应精度的H3索引

return h3.geoToH3Address(latitude, longitude, resolution.precision);

} catch (Exception e) {

logger.error("geoToH3Address-error", e);

throw e;

}

}

通过H3索引找到对应的正六边形中心点坐标经纬度：

public static Optional<GeoCoord> getCoordinateByH3Index(String h3Index) {

try {

//param validate 校验H3索引字符串是否合法

if (h3PreCheckInvalid(h3Index)) {

logger.warn("getCoordinateByH3Index,param is invalid!");

return Optional.empty();

}

//execute 获取正六边形中心坐标

GeoCoord geoCoord = h3.h3ToGeo(h3Index);

return Optional.of(geoCoord);

} catch (Exception e) {

logger.error("getCoordinateByH3Index error,h3Index:" + h3Index, e);

return Optional.empty();

}

}

有了上述的两种方式，其实我们已经可以通过Uber H3索引的属性做自己需要的业务拓展了。

比如通过某一个点，获取到符合精度的正六边形中心坐标，以这个正六边形中心坐标，计算直线距离N公里内有多少个索引，得到索引集合。

那么则可以通过索引集合来查询货物或者商家是否有符合集合内索引的属性，如果有则证明在N公里范围内，如果没有则证明不在N公里范围内。

H3核心API方法列举：

final class NativeMethods {

NativeMethods() {

}

  native int maxH3ToChildrenSize(long var1, int var3);

  native void h3ToChildren(long var1, int var3, long[] var4);

  native boolean h3IsValid(long var1);

  native int h3GetBaseCell(long var1);

native boolean h3IsPentagon(long var1);

native long geoToH3(double var1, double var3, int var5);

native void h3ToGeo(long var1, double[] var3);

native int h3ToGeoBoundary(long var1, double[] var3);

native int maxKringSize(int var1);

native void kRing(long var1, int var3, long[] var4);

native void kRingDistances(long var1, int var3, long[] var4, int[] var5);

native int hexRange(long var1, int var3, long[] var4);

native int hexRing(long var1, int var3, long[] var4); native int h3Distance(long var1, long var3);

native int experimentalH3ToLocalIj(long var1, long var3, int[] var5);

native long experimentalLocalIjToH3(long var1, int var3, int var4);

native int h3LineSize(long var1, long var3);

native int h3Line(long var1, long var3, long[] var5);

native int maxPolyfillSize(double[] var1, int[] var2, double[] var3, int var4);

native void polyfill(double[] var1, int[] var2, double[] var3, int var4, long[] var5);

native void h3SetToLinkedGeo(long[] var1, ArrayList<List<List<GeoCoord>>> var2);

native int compact(long[] var1, long[] var2);

native int maxUncompactSize(long[] var1, int var2);

native int uncompact(long[] var1, int var2, long[] var3);

native double hexAreaKm2(int var1); native double hexAreaM2(int var1);

native double edgeLengthKm(int var1);

native double edgeLengthM(int var1);

native long numHexagons(int var1);

native void getRes0Indexes(long[] var1);

native boolean h3IndexesAreNeighbors(long var1, long var3);

native long getH3UnidirectionalEdge(long var1, long var3);

native boolean h3UnidirectionalEdgeIsValid(long var1);

native long getOriginH3IndexFromUnidirectionalEdge(long var1);

native long getDestinationH3IndexFromUnidirectionalEdge(long var1);

native void getH3IndexesFromUnidirectionalEdge(long var1, long[] var3);

native void getH3UnidirectionalEdgesFromHexagon(long var1, long[] var3);

native int getH3UnidirectionalEdgeBoundary(long var1, double[] var3);

}

那么如何正确的入手Uber H3呢？

我建议：1.了解自己的需求场景是否符合范围查找的场景。

2.判断是否对范围查找的误差要求没有特别的高。

3.下载Uber H3源码包：源码包中提供了，基础的场景测试用例，基准测试用例。下载代码后本地debug就可以进行调试。

https://github.com/uber/h3-java/tree/master/src/test/java/com/uber/h3core

4.调试完毕后，根据自己的场景模型，构造符合自己使用的API或者工具类，提供给使用方。

欢迎大家多提宝贵意见。