原始需求

最近在做一个项目，需要获得地图上任意坐标点为中心150公里范围内所有数据库内有效坐标点。团队内最疯狂快速的想法是指数据库内所有当前国家的坐标点全取来，然后一一和中心点进行比较。但如果是中心点在国家边缘还是会有问题无法计算另一个国家的坐标，如果数据内出现类似中国、俄罗斯这种大范围的国家这数据这计算难度太不现实了。笑…

解决方案

ingress game scan 第一个想到的就是若干年前玩过的Ingress是有对地理位置进行分区的，整个地球会分成6个大区。若干小区域并对其进行编号，开G进行搜索后发现Google家对其算法库进行了封装出了一个S2Geometry C++类库。

准备环境

按官方的建议，该库可以支持MacOS或Linux平台。需要一个C++11的编译器，另外 需要安装 OpenSSL(大数支持)，googletest测试框架。

# 基础环境安装
$ apt-get install libgflags-dev libgoogle-glog-dev libgtest-dev libssl-dev
# 编译器安装
$ apt-get install cmake

# 获取S2源码包
$ git clone https://github.com/google/s2geometry.git
# 编译S2
$ cd s2geometry
$ mkdir build
$ cd build
$ cmake -S .. -DWITH_GFLAGS=ON -WITH_GTEST=ON
$ make
$ make test
$ make install

到此开发环境已经构建好，我们接下来讲下S2的原理

S2原理

erath

S2库是把整个球体投影到6个面上，先得到6个大的区间块，然后再通过希尔伯特曲线【Hilbert Curve】进一步的进行划分，把每一个经纬度都转换成一个cell点。

曲线的划分方法

最终得到一个一维的坐标系，比如公司附近的坐标 40.154657, 116.309742 进行转换后会得到 1/223320133133131321303022012101 其中第一位是球的6个面，我们处在第一面，后面的32位4进制就是希尔伯特曲线一级一级下来的坐标系。每一位也叫一个等级，等级越高表示的区域越大。第0级一共6个块，每个块的平均面积是85011012.19 km^2 我们平时 已经常用的第06级每个块的平均面积为 20754.64 Km^2

了解了以上原理我先来做第一个DEMO、取出某一坐标点的cellId

Demo1将坐标点转换为CellId

#include <iostream>

#include "s2/s2earth.h"
#include "s2/s2cell_id.h"

int main(int argc, char **argv) {
    S2LatLng latlng = S2LatLng::FromDegrees( 40.154657, 116.309742);
    S2CellId cellid = S2CellId(latlng);
    std::cout << "cellid is: " <<  cellid;
}

编译后我们执行下试试，可以看到输出结果 [cellid is: 1/223320133133131321303022012101]

最终DEMO 取出指定范围的所有点

接下来我们考虑如何取出某一点为半径范围的所有块。


//首先我们要的是一个圆形，我们先建立一个cap对象表示这个圆形
S2Cap cap = S2Cap::FromCenterHeight(latlng.Normalized().ToPoint(),(radius_radians*radius_radians)/2.0);
    
//接下来我们来获得该范围的坐标集合
S2RegionCoverer coverer();
S2CellUnion uni = coverer.GetCovering(cap);
//接下来我们打印该坐标块集合
for(size_t i=0 ;i<uni.size(); ++i) {
    std::cout << "cellid "<< i <<" is: " << uni[i] << " level is:" << uni[i].level()<<" token is: " << uni[i].ToToken().c_str() << "\n";
}

执行后我们会得到 如下 结果

cellid 0 is: 1/223302 level is:6 token is: 35e5
cellid 1 is: 1/22331233 level is:8 token is: 35edf
cellid 2 is: 1/2233130 level is:7 token is: 35ee4
cellid 3 is: 1/2233132 level is:7 token is: 35ef4
cellid 4 is: 1/2233133 level is:7 token is: 35efc
cellid 5 is: 1/22332 level is:5 token is: 35f4
cellid 6 is: 1/2233303 level is:7 token is: 35f9c
cellid 7 is: 1/223331 level is:6 token is: 35fb

可以看到结果里的块有各个等级，原因是我们会用尽量少的cell块，并且每个cell表示尽量多的面积，处于圆中心的会是一个5级的块，越向边缘，块的等级会越小越精细

比如我们为了表示某个圆形，当使用5个块时结果如下

cell5

当我们使用50个块时

cell 50

当我们使用500个块时

cell500

我们从上面可以看出块越多的时候，肯定会更精细，当然越精细带来的结果就是效率更低。所以更多的时候要结合你的业务来看到底需要取多少块，精确到哪个级别。

思考

如果此次需求不是圆形呢？是某个省/州

zhou

参考资料


如果觉得文章内容比较实用，期望获得更新通知，请关注公众号：

guohaiqr.jpg