H3:空间索引精度

作者: LiHui 分类: Middleware 发布时间: 2018-08-26 13:41

以Uber打车服务举一个例子,比如有乘客需要打车,调度系统默认会给乘客筛选附近4KM的司机,然后可能会经过一系列的过滤条件,筛选出最合适的一个司机去为乘客服务,要注意的是这里的最合适并不是最近,因为也许最近的一个司机并非空载,或者乘客是一个VIP,而最近的司机并非是服务VIP客户的等等

如下图

NewImage

虽然说最合适不等于最近,但司机空载寻找乘客,考虑成本不可能调度一个最远的司机过来,因此对于调度筛选的过程,在满足其它必须条件的前提下,肯定是距离越近越好

试想一下,假如乘客4KM周围车辆过多,首先按半径过滤,然后范围内每一辆车都要一一进行比较,最终筛选出合适的一辆车,就算乘客周围很近就有空车,还是必须要遍历,比较完范围内所有的车,效率比较低下

在此基础上,Uber的基于六边形的空间索引算法更为优良

1:将整个空间分为大量的六边形格子,每个格子对应一个空间索引,那么对于任何一个位置的点必然会落在某一个格子里,也就会按照经纬度建立起了空间索引

2:知道了经纬度,计算出当前位置空间索引,以及相邻格子索引,如果当前位置空间索引里找不到合适的(一些过滤条件),就扩充到相邻索引,当前索引已记录

3:选择六边形的原因是相邻索引只有6个,三角形和四边形都多余6个,相邻索引越少越好,再慢慢层级扩大,这样就能兼顾距离尽可能较近

Mesh 10 3

到了这里还没有结束,对于格子大小的选择,也是要考虑的,假如格子太大,如果世界就一个格子,显然是神经病,按一开始的例子,试想如果格子边长,半径差不多4KM,那么和一开始算法没什么两样,无法体现出该方法优势,如果格子太小,边长几米,也没必要,因为一辆车都有2米厂,一个格子塞不了几辆车,所以对于格子大小的配置是要好好考量的,也就是空间索引的精度

对此Uber给了一些参考数据

源码:https://github.com/uber/h3

具体参考h3/src/h3lib/lib/geoCoord.c这个C文件,一共提供了16种精度

 /*
 * The following functions provide meta information about the H3 hexagons at
 * each zoom level. Since there are only 16 total levels, these are current
 * handled with hardwired static values, but it may be worthwhile to put these
 * static values into another file that can be autogenerated by source code in
 * the future.
 */

double H3_EXPORT(hexAreaKm2)(int res) {
    static const double areas[] = {
        4250546.848, 607220.9782, 86745.85403, 12392.26486,
        1770.323552, 252.9033645, 36.1290521,  5.1612932,
        0.7373276,   0.1053325,   0.0150475,   0.0021496,
        0.0003071,   0.0000439,   0.0000063,   0.0000009};
    return areas[res];
}

double H3_EXPORT(hexAreaM2)(int res) {
    static const double areas[] = {
        4.25055E+12, 6.07221E+11, 86745854035, 12392264862,
        1770323552,  252903364.5, 36129052.1,  5161293.2,
        737327.6,    105332.5,    15047.5,     2149.6,
        307.1,       43.9,        6.3,         0.9};
    return areas[res];
}

double H3_EXPORT(edgeLengthKm)(int res) {
    static const double lens[] = {
        1107.712591, 418.6760055, 158.2446558, 59.81085794,
        22.6063794,  8.544408276, 3.229482772, 1.220629759,
        0.461354684, 0.174375668, 0.065907807, 0.024910561,
        0.009415526, 0.003559893, 0.001348575, 0.000509713};
    return lens[res];
}

double H3_EXPORT(edgeLengthM)(int res) {
    static const double lens[] = {
        1107712.591, 418676.0055, 158244.6558, 59810.85794,
        22606.3794,  8544.408276, 3229.482772, 1220.629759,
        461.3546837, 174.3756681, 65.90780749, 24.9105614,
        9.415526211, 3.559893033, 1.348574562, 0.509713273};
    return lens[res];
}

/** @brief Number of unique valid H3Indexes at given resolution. */
int64_t H3_EXPORT(numHexagons)(int res) {
    static const int64_t nums[] = {122L,
                                   842L,
                                   5882L,
                                   41162L,
                                   288122L,
                                   2016842L,
                                   14117882L,
                                   98825162L,
                                   691776122L,
                                   4842432842L,
                                   33897029882L,
                                   237279209162L,
                                   1660954464122L,
                                   11626681248842L,
                                   81386768741882L,
                                   569707381193162L};
    return nums[res];
}

double H3_EXPORT(hexAreaKm2)(int res):记录的是单个六边形的大小,单位是KM * KM

double H3_EXPORT(hexAreaM2)(int res):记录的是单个六边形的大小,单位是M * M

double H3_EXPORT(edgeLengthKm)(int res):记录的是单个六边形的边长,单位是KM

double H3_EXPORT(edgeLengthM)(int res):记录的是单个六边形的边长,单位是M

int64_t H3_EXPORT(numHexagons)(int res):记录的是全球六边形的总数,也就是空间索引的总数

把这些精度值做一个列表

NewImage

可以想象一下,精度越小,基本没啥用,神经质;精度越大,基本不好用,因为格子太小,正常情况下可能居中才有用途,一般7~10可能才是城市,小区街道界别,比较适用

纯属恶搞

浙ICP备16024533号

浙公网安备 33010802007459号