陌陌逆地理编码算法改造
什么是逆地理编码
当输入地址而返回坐标时，即将地址信息转换成其所在的对应经纬度坐标，这个过程叫地理编码；反过来，当输入的是点坐标而返回的是一个地址描述，这个过程叫做逆地理编码。
背景
逆地理编码是一项重要的地图基础能力，凡是涉及到地理位置的业务几乎都离不开逆地理编码。陌陌在早期就已经完成了逆地理编码系统的建设，服务名为city-indexer。作为一个基础服务，city-indexer对全平台提供了稳定的逆地理编码能力，实现了从经纬度到区县级行政区划的逆编码功能，日承载流量接近60亿。
然而在长期的实践过程中，我们发现了city-indexer逆地理编码系统仍存在许多可改进的空间。于是，在2021年Q4我们完成了逆地理编码系统的改造，建设了新的逆地理编码服务geocoding。
本文将着重围绕city-indexer服务的缺陷分析以及对新的逆地理编码服务geocoding的系统设计介绍展开。
city-indexer
总体设计
city-indexer服务使用GeoHash作为空间点索引算法。其逆地理编码功能的整体实现思想为：离输入坐标点最近的坐标点所在的行政区划即为输入点的行政区划。
基于该实现思路，city-indexer服务在服务启动时预加载了一批行政区划地点（记为Region，共859566个）, 并记录该地点对应的GeoHash值到内存中的缓存Map<GeoHash, List> cache 中。在实现逆地理编码功能时，则从内存中取出离输入坐标点最近的一个Region作为返回结果。
Region 数据结构如下所示。
{"dataId":"199546","lat":39.996095,"lng":116.467559,"country":"中国","province":"北京市","city":"北京市","sublocality":"朝阳区","formatted_address":"北京市朝阳区","regionCode":"110105"}
实现逆地理编码的算法大致流程如下图：
GeoHash中心点扩散示意图
逆地理编码过程接受一个经纬度参数（lat,lng）,使用（lat,lng）编码出一个GeoHash，以该GeoHash为循环的起点，每次循环从缓存中查找GeoHash列表对应的Region，若查找结果不为空，则以其中距离输入坐标点最近的点作为结果返回。若向外扩散了100个圈仍未找到，则放弃查找，返回空数据。
GeoHash中心点扩散示意图
缺陷分析
city-indexer服务的逆地理编码功能在两方面存在着缺陷，分别是结果准确性以及查询性能。
准确性缺陷
首先， 我们知道一个地点的行政区划信息并不是固定不变的，尤其是对于处于多个行政区划的边界的地点。比如说，某个地点在几年前归属于北京市朝阳区，但经过某次重新划分后，现在已经归属于顺义区，这样的情况是完全有可能出现的。因此，逆地理编码功能所参照的数据需要有较高的实时性才能保证准确性。city-indexer参照的数据点多年未更新且来源不明，参照了正确性难以保障的数据计算出来的结果自然无法保证准确性。
其次，即使保证了参照的所有地点的行政区划归属信息都是正确的，city-indexer所使用的算法得出的结果依旧不可靠。
一方面， 中心点扩散算法并无法保证找到的Region是距离输入的坐标点最近的Region。
中心点扩散最近点查找错误示例
以上图为例，查找的目标点为A, 在黄色的圈中存在Region B, 在蓝色的圈中存在Region C，显然距离A更近的Region是C，然而中心点扩散算法在第二次循环时已经将点B作为结果返回了。
另一方面，就算数据无误并且找到了距离最近的Region，返回的结果依旧有可能是错的。这种情况主要出现在临近行政区划边界线的坐标点上。
朝阳区行政边界图
如上图为朝阳区的行政区划边界线, 假设在缓存中加载了B,C两个坐标点。当输入点为A，该算法会以属于东城区但距离更近的点B作为结果返回。则此时点A便会被误判为是处于东城区。
查询性能缺陷
city-indexer的查询效率与输入坐标点附近缓存数据的密集程度直接相关，在最差的情况下需要循环100次，进行数万次的geohash编码以及缓存的查询，cpu资源损耗严重。
geocoding
基于旧的逆地理编码服务存在的问题，新的逆地理编码服务geocoding为实现以下目标进行了改进：
可维护的数据源
在数据源无误的情况下，不出现定位错误
不依赖任何远程调用
高QPS，排除坐标点不同导致性能差异较大的情况
Point in Polygon 问题
在开始介绍geocoding逆地理编码实现之前，先看一下计算几何的一个经典的问题，如何判断一个点是否在多边形的内部？
其中一个方法是计算射线与多边形边界相交的次数：任一射线穿过多边形，奇数段位于多边形之内，偶数段位于多边形之外。通常称之为射线法。
射线法示意图
如上图所示，检查一点是否在多边形之内，可以作一射线从该点往任意方向投射，若让射线与多边形边的相交次数为奇数，则点位于多边形之内。
除了射线法外，还有转角法、角度和判断法、面积法等多个算法可以解决该问题，为了不占用太多篇幅，在此不做展开，感兴趣的同学可以自行搜索Point in Polygon问题进行了解。
总之，该问题是有着许多成熟并且可靠的解决方案的。而此次逆地理编码服务的重构正是以该问题为基本思路进行的——判断一个经纬度位于哪个行政区划等价于判断该坐标点位于哪个行政区划对应的多边形（一个或多个）的内部。
空间点索引
目前中国区县一共有2000多个，全球的国家有200+。正如同city-indexer不可能遍历80多万个Region去找到距离最近的一个Region。遍历所有行政区划去判断Point in Polygon问题来找到当前坐标所属的行政区划显然是不现实的，我们需要有类似于GeoHash的空间点索引算法去快速定位到坐标点可能属于的多边形，减少计算次数。
我们在geocoding中用到了Google S2Cell作为索引。Google S2 中定义了一个将单位球体分解成单元格层次结构的框架。每个S2Cell 的单元格对应着一个四边形。通过将立方体的六个面投影到单位球上来获得层级的顶层，称为face，通过递归地将每个单元细分为四个子层来获得较低层。例如，下图显示了六个 face 中S2Cell的两个，其中一个已经递归划分了多次。
S2Cell示意图
每个S2Cell都有一个 level 属性，代表递归划分的次数，S2Cell的level范围从 0 到 30。level 30的 Cell总共有6 * 4 ^30个，每个在地球表面 1cm 左右。
有了S2Cell，我们只需要查询经纬度所在S2Cell一共与几个行政区划相交，再判断经纬度是否在这几个行政区划的边界线内即可， Point in Polygon问题的计算次数从2000多次减少到了个位次数。
Google S2 相关应用
前面介绍了Google S2 工具包下的S2Cell,我们利用它来作为索引，帮助我们快速查找到候选的行政区划。对GeoHash有一定了解的同学会可能会感到奇怪，S2Cell看起来似乎跟GeoHash没有太大的区别，都是一个有递归特性的单元格，为什么我们要选择S2 这么个对大家来说比较陌生的工具呢？
事实上，除开性能方面的考虑。我们选择S2的一个更重要的原因是 S2 工具包为我们提供了许多简便易用的方法，让我们减少了许多不必要的重复造轮子的工作。下面我们来介绍一下 geocoding中对S2相关的一些实践。
S2Point & S2Polygon
S2Point代表地球上的一个坐标点，Google S2把地球视作一个单位球，使用一个三维的坐标点 P(x,y,z) (0 <= x,y,z <= 1)来描述一个点。当然了，如果每次要确定一个点都需要计算出这个坐标在三维坐标轴上的数值，那这样的使用方式也太复杂了。S2提供了另一个类S2LatLng 来方便我们确定一个坐标点，我们只需提供一个我们更熟悉的经纬度点L(lat, lng),就可以实例化一个S2Point。
S2Polygon代表多边形，需要注意的是，S2中的多边形与我们通常认知的多边形不太一样。我们一般把在同一平面且不在同一直线上的三条或三条以上的线段首尾顺次连结且不相交所组成的封闭图形叫做多边形，而S2中的多边形则是由n个封闭图形所组成。事实上，这也恰好与符合了行政区划对应的多边形特征。如下图，朝阳区的行政区划多边形就是由两个普通的多边形所组成。
朝阳区行政区划
相应的，对于普通的多边形，S2 则是用另一个类S2Loop来表示，一个S2Loop由n个S2Point组成，即这n个S2Point 顺序相连后围成的一个封闭图形。
简单介绍完了 S2Point 和 S2Polygon ,那么这两个类在我们的逆地理编码系统中可以发挥什么作用呢？其实从这两个类的名称我们应该也都联想到了Point in Polygon问题。没错，S2 提供了该问题的相关方法，只需要我们定义一个S2Point和S2Polygon,就可以调用S2Polygon::contains(S2Point point) 方法判断一个点是否在多边形中。（代码实现可见下图demo。）
S2 Point in Polygon问题
S2RegionCoverer
前面我们还遗留了一个问题，如何确定经纬度所在S2Cell一共与哪几个行政区划相交？S2 的一个利器 S2RegionCoverer 为该问题提供了解法。S2RegionCoverer 即区域覆盖器，S2RegionCoverer::getCovering可以生成n个S2Cell，用来覆盖一个S2Polygon。
S2Cell 覆盖中国对应的S2Polygon
通过该方法，我们就可以成功的建立 S2Cell与行政区划的相交关系。
逆地理编码实现流程
前期准备。
从开源的API中查询到中国所有的行政区划的边界坐标集 （细分到区县）,存储到服务的文件中。
初始化。
读行政边界文件，利用经纬度坐标集生成S2Polygon, 记录行政区划RegionInfo对应的 S2Polygon. 使用S2RegionCoverer生成覆盖S2Polygon的List s2CellList. 遍历s2CellList, 记录 S2Cell与行政区划的相交关系到缓存中 -> Map<S2Cell, List> cache.
逆地理编码过程。
输入 lat, lng
根据lat, lng定义一个点 S2Point
S2Cell::fromPoint(S2Point) 生成对应的S2Cell。
List = cache.get(S2Cell);
遍历regionList, 使用 S2Polygon::contains判断S2Point是否在边界内，若在则返回对应的行政区划
若遍历无果，说明输入坐标点不在我们采集的行政区划内(比如在海上），返回默认错误数据。
改造成果
geocoding实现的逆地理编码系统主要在性能与查询准确性上实现了突破，解决了city-indexer的主要缺陷。
性能
qps数据图
接口耗时数据图
通过性能压测观察，geocoding逆地理编码系统可以在承载11000QPS流量稳定运行，且平均耗时不超过5ms，性能表现优异。
同时，geocoding所采用的算法也解决了中心点扩散算法在点位稀疏地区的性能长尾问题，实现了排除坐标点不同导致性能差异过大这一目标。
准确性
geocoding解决了city-indexer系统的最近点索引错误以及边界点定位错误的问题，在准确性上更加有保障。
总结
本文仅对city-indexer以及geocoding两套逆地理编码系统进行了分析介绍。其中geocoding中大量使用到的Google S2技术，包括S2CellID的编码细节，S2Polygon解决Point in Polygon问题的算法，S2RegionCoverer实现空间覆盖等问题都是值得学习借鉴的，限于篇幅无法过多展开。