地理索引 uber s3

Google S2

    正方体投影

        以正方体投影作为基准，六个面逐级纬度二分。

 希尔伯特曲线

 相邻相近



            等距连续？



    编码方式

            六面ID+ 所在层级经纬度二分下标（0、1），受曲线旋转影响，逐层排列。



    映射修正

            使面积差距小

            

   线性变换：s = 0.5 * (1 + u)



            tan变换：s = 2 / pi * (atan(u) + pi / 4) = 2 * atan(u) / pi + 0.5



            二次变换（Uber选择）：u >= 0，s = 0.5 * sqrt(1 + 3*u) 



                                                        u < 0, s = 1 - 0.5 * sqrt(1 - 3*u)



Uber H3

 官网

            https://uber.github.io/h3/#/documentation/overview/introduction



    怎么划分空间

            假设正x多边形，y个顶点相接：360 / y = ((x-2)*180) / x 

     正整数解只有（3,6、4,4、6,3)

  正六多边形优点

                    相邻单元距离相等



                    近似圆



                            自身近似圆形，贴合密度概念，很适合大多数的汇总分析场景。



                            周围相近近似圆形且等距，方便附近查找，阶梯分析等



            Uber怎么做？

                     想要的一个优点，分割后面积相同。



                    面积相同的正六边形不能构建成球形。



                    正二十面体

      基本单元

      正二十面体，交点有五个边。每一个基本单元做6边形分割

      全球被划分为12个正五边形和110个正六边形的基本单元。



                    Dymaxion map



                            戴美克森氏地图(Dymaxion map)或称富勒地图(Fuller map),由Richard Buckminster Fuller发明。建筑师。



                            dymaxion（最大限度利用能源的,以最少结构提供最大强度的），这个词来源于三个单词：Dynamic，意思是动力，Maximum，意思是最多、最大，还有ion，是一个原子或是一个电极中一组原子。



                            选择二十面体的顶点在水中，尽量避免常规应用中同时使用五边形和六边形。



                    逐级等分



                            可支持16级拆分



                            第一层基础单元格，15级（编码方式决定）的等面积拆分                        <!-- more --> 基本元素

        单元格(cell)

                普通的各级分裂的结果



        有向格

                单元格增加一个以六条边为基础的维度，可以表示从一个单元格到另一个共边单元格的意向，相当于记录两个有共边的单元格，当需要时，可以将边缘转换回原始索引或目标索引。



                分为单向格(Unidirectional Edge)和双向格(bidirectional edge)。

                

 IJK坐标系

                一种平面六边形网络中的三轴坐标系。为六边形网络中的每一个元素提供唯一路径。

 FaceIJK坐标系

                H3 核心运算使用的坐标系。



                由二十面体基本单元ID + IJK坐标系构成。有两种类型（R. Buckminster Fuller定义）：

     0层使用ClassII；逐层摇摆，交替使用。



        其他坐标系

                https://uber.github.io/h3/#/documentation/core-library/coordinate-systems



    编码方式

            使用64位，一个Long值的长度来记录一个基本类型。



            ·· 前4位表示索引模式：0：无效；1：单元格；2：单向格；3：双向格。



            ·· 3位表示共边ID（模式2和模式3有效）。



            ·· 4位表示当前索引级别（0-15）。



            ·· 7位表示基本单元格ID（0-121）。



            ·· 每3位一个层级，逐层排列（3*15）。



            ·· 队尾未被使用的位置1。



            拆分编码：（ 五边形拆分中废弃下标1）

 应用场景

                普通索引

                        高精度的数据，模糊到选定的H3粒度，作为数据的索引使用。



                附近搜

                        K环（kRing）：



                                根据指定中心点，得到指定单位距离内（K）的其他单元格，非常方便的实现附近的需要。发挥近似圆的优势。



                多边形索引

                        指定粒度切分指定多边形，得到多边形覆盖的单元格，并且提供压缩功能。

     jar使用

            groupId：com.uber



            artifactId：h3



            version：



            H3Core h3 = H3Core.newInstance();



            h3.xxx();



    性能

            普通应用场景和geohash的使用场景并无实质性的区别，但是等面积、近圆的特性，在一些场景，会降低实现算法的难度。



            多边形索引的场景，需要围栏预处理工作，然后做两个Btree的关联运算，具体性能对比，待测试。



    缺点

            上下级的不完全覆盖(蓝色区域举例)，一些应用场景要注意。

                                

 编码方式对普通索引不友好

    分割（投影）算法不完美