筆者在《高效的多維空間點索引算法 — Geohash 和 Google S2》文章中詳細的分析了 Google S2 的算法實現(xiàn)思想领曼。文章發(fā)出來以后虱朵，一部分讀者對它的實現(xiàn)產(chǎn)生了好奇。本文算是對上篇文章的補充豌拙，將從代碼實現(xiàn)的角度來看看 Google S2 的算法具體實現(xiàn)陕悬。建議先讀完上篇文章里面的算法思想，再看本篇的代碼實現(xiàn)會更好理解一些按傅。

一. 什么是 Cell 捉超？

Google S2 中定義了一個將單位球體分解成單元格層次結(jié)構(gòu)的框架。每個 Cell 的單元格是由四個測地線限定的四邊形唯绍。通過將立方體的六個面投影到單位球上來獲得層級的頂層拼岳，通過遞歸地將每個單元細分為四個子層來獲得較低層。例如况芒，下面的圖片顯示了六個 face 中 Cell 的兩個惜纸，其中一個已經(jīng)細分了幾次：

注意 Cell 邊緣似乎是彎曲的，這是因為它們是球形測地線绝骚，即球體上的直線（類似于飛機飛行的路線）

S2 Level 對于空間索引和將區(qū)域逼近為單元集合非常有用耐版。Cell 可用于表示點和區(qū)域：點通常表示為葉子節(jié)點，而區(qū)域表示為任何 Level 的 Cell 的集合压汪。例如粪牲，下面是夏威夷近似的22個單元的集合：

二. S(lat,lng) -> f(x,y,z)

緯度 Latitude 的取值范圍在 [-90°,90°] 之間。
經(jīng)度 Longitude 的取值范圍在 [-180°,180°] 之間止剖。

第一步轉(zhuǎn)換腺阳，將球面坐標轉(zhuǎn)換成三維直角坐標

func makeCell() {
    latlng := s2.LatLngFromDegrees(30.64964508, 104.12343895)
    cellID := s2.CellIDFromLatLng(latlng)
}

上面短短兩句話就構(gòu)造了一個 64 位的CellID。

func LatLngFromDegrees(lat, lng float64) LatLng {
    return LatLng{s1.Angle(lat) * s1.Degree, s1.Angle(lng) * s1.Degree}
}

上面這一步是把經(jīng)緯度轉(zhuǎn)換成弧度穿香。由于經(jīng)緯度是角度亭引，弧度轉(zhuǎn)角度乘以 π / 180° 即可。

const (
    Radian Angle = 1
    Degree       = (math.Pi / 180) * Radian
}

LatLngFromDegrees 就是把經(jīng)緯度轉(zhuǎn)換成 LatLng 結(jié)構(gòu)體扔水。LatLng 結(jié)構(gòu)體定義如下：

type LatLng struct {
    Lat, Lng s1.Angle
}

得到了 LatLng 結(jié)構(gòu)體以后痛侍，就可以通過 CellIDFromLatLng 方法把經(jīng)緯度弧度轉(zhuǎn)成 64 位的 CellID 了。

func CellIDFromLatLng(ll LatLng) CellID {
    return cellIDFromPoint(PointFromLatLng(ll))
}

上述方法也分了2步完成，先把經(jīng)緯度轉(zhuǎn)換成坐標系上的一個點主届，再把坐標系上的這個點轉(zhuǎn)換成 CellID赵哲。

關(guān)于經(jīng)緯度如何轉(zhuǎn)換成坐標系上的一個點，這部分的大體思路分析見筆者的這篇文章君丁，這篇文章告訴你從代碼實現(xiàn)的角度如何把球面坐標系上的一個點轉(zhuǎn)換到四叉樹上對應(yīng)的希爾伯特曲線點枫夺。

func PointFromLatLng(ll LatLng) Point {
    phi := ll.Lat.Radians()
    theta := ll.Lng.Radians()
    cosphi := math.Cos(phi)
    return Point{r3.Vector{math.Cos(theta) * cosphi, math.Sin(theta) * cosphi, math.Sin(phi)}}
}

上面這個函數(shù)就是把經(jīng)緯度轉(zhuǎn)換成三維坐標系中的一個向量點，向量的起點是三維坐標的原點绘闷，終點為球面上轉(zhuǎn)換過來的點橡庞。轉(zhuǎn)換的關(guān)系如下圖：

θ 即為經(jīng)緯度的緯度，也就是上面代碼中的 phi 印蔗，φ 即為經(jīng)緯度的經(jīng)度扒最，也就是上面代碼的 theta 。根據(jù)三角函數(shù)就可以得到這個向量的三維坐標：

x = r * cos θ * cos φ
y = r * cos θ * sin φ 
z = r * sin θ

圖中球面的半徑 r = 1 华嘹。所以最終構(gòu)造出來的向量即為：

r3.Vector{math.Cos(theta) * cosphi, math.Sin(theta) * cosphi, math.Sin(phi)}

(x, y, z) 為方向向量吧趣，它們并不要求是單位向量。(x, y, z) 的取值范圍在 [-1,+1] x [-1,+1] x [-1,+1] 這樣的立方體三維空間中耙厚。它們可以被標準化以使得在單位球上獲得對應(yīng)的點强挫。

至此，已經(jīng)完成了球面上的點S(lat,lng) -> f(x,y,z) 的轉(zhuǎn)換薛躬。

三. f(x,y,z) -> g(face,u,v)

接下來進行 f(x,y,z) -> g(face,u,v) 的轉(zhuǎn)換

func xyzToFaceUV(r r3.Vector) (f int, u, v float64) {
    f = face(r)
    u, v = validFaceXYZToUV(f, r)
    return f, u, v
}

這里的思路是進行投影俯渤。

先從 x，y型宝，z 三個軸上選擇一個最長的軸八匠，作為主軸。

func (v Vector) LargestComponent() Axis {
    t := v.Abs()

    if t.X > t.Y {
        if t.X > t.Z {
            return XAxis
        }
        return ZAxis
    }
    if t.Y > t.Z {
        return YAxis
    }
    return ZAxis
}

默認定義 x 軸為0趴酣，y軸為1臀叙，z軸為2 。

const (
    XAxis Axis = iota
    YAxis
    ZAxis
)

最后 face 的值就是三個軸里面最長的軸价卤，注意這里限定了他們?nèi)叨荚?[0,5] 之間劝萤，所以如果是負軸就需要 + 3 進行修正。實現(xiàn)代碼如下慎璧。

func face(r r3.Vector) int {
    f := r.LargestComponent()
    switch {
    case f == r3.XAxis && r.X < 0:
        f += 3
    case f == r3.YAxis && r.Y < 0:
        f += 3
    case f == r3.ZAxis && r.Z < 0:
        f += 3
    }
    return int(f)
}

所以 face 的6個面上的值就確定下來了床嫌。主軸為 x 正半軸，face = 0胸私；主軸為 y 正半軸厌处，face = 1；主軸為 z 正半軸岁疼，face = 2阔涉；主軸為 x 負半軸缆娃，face = 3；主軸為 y 負半軸瑰排，face = 4贯要；主軸為 z 負半軸，face = 5 椭住。

選定主軸以后就要把另外2個軸上的坐標點投影到這個面上崇渗，具體做法就是投影或者坐標系轉(zhuǎn)換。

func validFaceXYZToUV(face int, r r3.Vector) (float64, float64) {
    switch face {
    case 0:
        return r.Y / r.X, r.Z / r.X
    case 1:
        return -r.X / r.Y, r.Z / r.Y
    case 2:
        return -r.X / r.Z, -r.Y / r.Z
    case 3:
        return r.Z / r.X, r.Y / r.X
    case 4:
        return r.Z / r.Y, -r.X / r.Y
    }
    return -r.Y / r.Z, -r.X / r.Z
}

上述就是 face 6個面上的坐標系轉(zhuǎn)換京郑。如果直觀的對應(yīng)一個外切立方體的哪6個面宅广，那就是 face = 0 對應(yīng)的是前面，face = 1 對應(yīng)的是右面些举，face = 2 對應(yīng)的是上面跟狱，face = 3 對應(yīng)的是后面，face = 4 對應(yīng)的是左面户魏，face = 5 對應(yīng)的是下面兽肤。

注意這里的三維坐標軸是符合右手坐標系的。即 右手4個手指沿著從 x 軸旋轉(zhuǎn)到 y 軸的方向绪抛，大拇指的指向就是另外一個面的正方向。

比如立方體的前面电禀，右手從 y 軸的正方向旋轉(zhuǎn)到 z 軸的正方向幢码，大拇指指向的是 x 軸的正方向，所以對應(yīng)的就是前面尖飞。再舉個例子症副，立方體的下面??，右手從 y 軸的負方向旋轉(zhuǎn)到 x 軸的負方向政基，大拇指指向的是 z 軸負方向贞铣，所以對應(yīng)的是下面??。

(face,u,v) 表示一個立方空間坐標系沮明，三個軸的值域都是 [-1,1] 之間辕坝。為了使得每個 cell 的大小都一樣，就要進行變換荐健，具體變換規(guī)則就在下一步轉(zhuǎn)換中酱畅。

四. g(face,u,v) -> h(face,s,t)

從 u颓鲜、v 轉(zhuǎn)換到 s透绩、t 用的是二次變換缤言。在 C ++ 的版本中有三種變換锦积，至于為何最后選了這種二次變換既琴，原因見這里散怖。

// 線性轉(zhuǎn)換
u = 0.5 * ( u + 1)

// tan() 變換
u = 2 / pi * (atan(u) + pi / 4) = 2 * atan(u) / pi + 0.5

// 二次變換
u >= 0急但，u = 0.5 * sqrt(1 + 3*u)
u < 0,    u = 1 - 0.5 * sqrt(1 - 3*u)

在 Go 中恕稠，轉(zhuǎn)換直接就只有二次變換了，其他兩種變換在 Go 的實現(xiàn)版本中就直接沒有相應(yīng)的代碼樊诺。

func uvToST(u float64) float64 {
    if u >= 0 {
        return 0.5 * math.Sqrt(1+3*u)
    }
    return 1 - 0.5*math.Sqrt(1-3*u)
}

(face,s,t) 表示一個 cell 空間坐標系仗考，s，t 的值域都是 [0,1] 之間啄骇。它們代表了一個 face 上的一個 point痴鳄。例如，點 (s,t) = (0.5,0.5) 代表的是在這個 face 面上的中心點缸夹。這個點也是當前這個面上再細分成4個小 cell 的頂點痪寻。

五. h(face,s,t) -> H(face,i,j)

這一部分是坐標系的轉(zhuǎn)換，具體思想見這里虽惭。

將 s橡类、t 上的點轉(zhuǎn)換成坐標系 i、j 上的點芽唇。

func stToIJ(s float64) int {
    return clamp(int(math.Floor(maxSize*s)), 0, maxSize-1)
}

s顾画，t的值域是[0,1]，現(xiàn)在值域要擴大到[0,2³⁰-1]匆笤。這里只是其中一個面研侣。

六. H(face,i,j) -> CellID

在進行最后的轉(zhuǎn)換之前，先回顧一下到目前為止的轉(zhuǎn)換流程炮捧。

func CellIDFromLatLng(ll LatLng) CellID {
    return cellIDFromPoint(PointFromLatLng(ll))
}

func cellIDFromPoint(p Point) CellID {
    f, u, v := xyzToFaceUV(r3.Vector{p.X, p.Y, p.Z})
    i := stToIJ(uvToST(u))
    j := stToIJ(uvToST(v))
    return cellIDFromFaceIJ(f, i, j)
}

S(lat,lng) -> f(x,y,z) -> g(face,u,v) -> h(face,s,t) -> H(face,i,j) -> CellID 總共有5步轉(zhuǎn)換庶诡。

經(jīng)過上面5步轉(zhuǎn)換以后，等效于把地球上的經(jīng)緯度的點都轉(zhuǎn)換到了希爾伯特曲線上的點了咆课。

在解釋最后一步轉(zhuǎn)換 CellID 之前末誓，先說明一下方向的問題。

有2個存了常量的數(shù)組：

    ijToPos = [4][4]int{
        {0, 1, 3, 2}, // canonical order
        {0, 3, 1, 2}, // axes swapped
        {2, 3, 1, 0}, // bits inverted
        {2, 1, 3, 0}, // swapped & inverted
    }
    posToIJ = [4][4]int{
        {0, 1, 3, 2}, // canonical order:    (0,0), (0,1), (1,1), (1,0)
        {0, 2, 3, 1}, // axes swapped:       (0,0), (1,0), (1,1), (0,1)
        {3, 2, 0, 1}, // bits inverted:      (1,1), (1,0), (0,0), (0,1)
        {3, 1, 0, 2}, // swapped & inverted: (1,1), (0,1), (0,0), (1,0)
    }

這兩個二維數(shù)組里面的值用圖表示出來如下兩個圖：

上圖是 posToIJ 书蚪，注意這里的 i喇澡，j 指的是坐標值，如上圖殊校。這里是一階的希爾伯特曲線晴玖，所以 i，j 就等于坐標軸上的值为流。posToIJ[0] = {0, 1, 3, 2} 表示的就是上圖中圖0的樣子窜醉。同理，posToIJ[1] 表示的是圖1艺谆，posToIJ[2] 表示的是圖2榨惰，posToIJ[3] 表示的是圖3 。

從上面這四張圖我們可以看出：
posToIJ 的四張圖其實是“ U ” 字形逆時針分別旋轉(zhuǎn)90°得到的静汤。這里我們只能看出四張圖相互之間的聯(lián)系琅催，即兄弟之間的聯(lián)系居凶，但是看不到父子圖相互之間的聯(lián)系。

posToIJ[0] = {0, 1, 3, 2} 里面存的值是 ij 合在一起表示的值藤抡。posToIJ[0][0] = 0侠碧，指的是 i = 0，j = 0 的那個方格缠黍，ij 合在一起是00弄兜，即0。posToIJ[0][1] = 1瓷式，指的是 i = 0替饿，j = 1 的那個方格，ij 合在一起是01贸典，即1视卢。posToIJ[0][2] = 1，指的是 i = 1廊驼，j = 1 的那個方格据过，ij 合在一起是11，即3妒挎。posToIJ[0][3] = 2绳锅，指的是 i = 1，j = 0 的那個方格酝掩，ij 合在一起是10鳞芙，即2。數(shù)組里面的順序是 “ U ” 字形畫的順序庸队。所以 posToIJ[0] = {0, 1, 3, 2} 表示的是圖0中的樣子。其他圖形同理闯割。

這上面的四張圖是 ijToPos 數(shù)組彻消。這個數(shù)組在整個庫中也沒有被用到，這里不用關(guān)系它對應(yīng)的關(guān)系宙拉。

初始化 lookupPos 數(shù)組和 lookupIJ 數(shù)組 由如下的代碼實現(xiàn)的宾尚。

func init() {
    initLookupCell(0, 0, 0, 0, 0, 0)
    initLookupCell(0, 0, 0, swapMask, 0, swapMask)
    initLookupCell(0, 0, 0, invertMask, 0, invertMask)
    initLookupCell(0, 0, 0, swapMask|invertMask, 0, swapMask|invertMask)
}

我們把變量的值都代進去，代碼就會變成下面的樣子：

func init() {
    initLookupCell(0, 0, 0, 0, 0, 0)
    initLookupCell(0, 0, 0, 1, 0, 1)
    initLookupCell(0, 0, 0, 2, 0, 2)
    initLookupCell(0, 0, 0, 3, 0, 3)
}

initLookupCell 入?yún)⒂?個參數(shù)谢澈，有4個參數(shù)都是0煌贴，我們需要重點關(guān)注的是第四個參數(shù)和第六個參數(shù)。第四個參數(shù)是 origOrientation锥忿，第六個參數(shù)是 orientation牛郑。

進入到 initLookupCell 方法中，有如下的4行：

initLookupCell(level, i+(r[0]>>1), j+(r[0]&1), origOrientation, pos, orientation^posToOrientation[0])
initLookupCell(level, i+(r[1]>>1), j+(r[1]&1), origOrientation, pos+1, orientation^posToOrientation[1])
initLookupCell(level, i+(r[2]>>1), j+(r[2]&1), origOrientation, pos+2, orientation^posToOrientation[2])
initLookupCell(level, i+(r[3]>>1), j+(r[3]&1), origOrientation, pos+3, orientation^posToOrientation[3])

這里順帶說一下 r[0]>>1 和 r[0]&1 究竟做了什么敬鬓。

    r := posToIJ[orientation]

r 數(shù)組來自于 posToIJ 數(shù)組淹朋。posToIJ 數(shù)組上面說過了笙各，它里面裝的其實是4個不同方向的“ U ”字。相當于表示了當前四個小方格兄弟相互之間的方向础芍。r[0]杈抢、r[1]、r[2]仑性、r[3] 取出的其實就是 00惶楼，01，10诊杆，11 這4個數(shù)歼捐。那么 r[0]>>1 操作就是取出二位二進制位的前一位，即 i 位刽辙。r[0]&1 操作就是取出二位二進制位的后一位窥岩，即 j 位。r[1]宰缤、r[2]颂翼、r[3] 同理。

再回到方向的問題上來慨灭。需要優(yōu)先說明的是下面4行干了什么朦乏。

orientation^posToOrientation[0]
orientation^posToOrientation[1]
orientation^posToOrientation[2]
orientation^posToOrientation[3]

再解釋之前，先讓我們看看 posToOrientation 數(shù)組：

posToOrientation = [4]int{swapMask, 0, 0, invertMask | swapMask}

把數(shù)值代入到上面數(shù)組中：

posToOrientation = [4]int{1, 0, 0, 3}

posToOrientation 數(shù)組里面裝的原始的值是 [01氧骤，00呻疹，00，11]筹陵，這個4個數(shù)值并不是隨便初始化的刽锤。

其實這個對應(yīng)的就是 圖0 中4個小方塊接下來再劃分的方向。圖0 中0號的位置下一個圖的方向應(yīng)該是圖1朦佩，即01并思；圖0 中1號的位置下一個圖的方向應(yīng)該是圖0，即00语稠；圖0 中2號的位置下一個圖的方向應(yīng)該是圖0宋彼，即00；圖0 中3號的位置下一個圖的方向應(yīng)該是圖3仙畦，即11 输涕。這就是初始化 posToOrientation 數(shù)組里面的玄機了。

posToIJ 的四張圖我們只能看出兄弟之間的關(guān)系慨畸，那么 posToOrientation 的四張圖讓我們知道了父子之間的關(guān)系莱坎。

回到上面說的代碼：

orientation^posToOrientation[0]
orientation^posToOrientation[1]
orientation^posToOrientation[2]
orientation^posToOrientation[3]

每次 orientation 都異或 posToOrientation 數(shù)組。這樣就能保證每次都能根據(jù)上一次的原始的方向推算出當前的 pos 所在的方向寸士。即計算父子之間關(guān)系型奥。

還是回到這張圖上來瞳收。兄弟之間的關(guān)系是逆時針旋轉(zhuǎn)90°的關(guān)系。那這4個兄弟都作為父親厢汹，分別和各自的4個孩子之間什么關(guān)系呢螟深？結(jié)論是，父子之間的關(guān)系都是 01烫葬，00界弧，00，11 的關(guān)系搭综。從圖上我們也可以看出這一點垢箕，圖1中，“ U ” 字形雖然逆時針旋轉(zhuǎn)了90°兑巾，但是它們的孩子也跟著旋轉(zhuǎn)了90°(相對于圖0來說)条获。圖2，圖3也都如此蒋歌。

用代碼表示這種關(guān)系帅掘，就是下面這4行代碼

orientation^posToOrientation[0]
orientation^posToOrientation[1]
orientation^posToOrientation[2]
orientation^posToOrientation[3]

舉個例子，假設(shè) orientation = 0堂油，即圖0修档，那么：

00 ^ 01 = 01
00 ^ 00 = 00
00 ^ 00 = 00
00 ^ 11 = 11

圖0 的四個孩子的方向就被我們算出來了，01府框，00吱窝，00，11迫靖，1003 院峡。和上面圖片中圖0展示的是一致的。

orientation = 1系宜，orientation = 2照激，orientation = 3，都是同理的：

01 ^ 01 = 00
01 ^ 00 = 01
01 ^ 00 = 01
01 ^ 11 = 10


10 ^ 01 = 11
10 ^ 00 = 10
10 ^ 00 = 10
10 ^ 11 = 01

11 ^ 01 = 10
11 ^ 00 = 11
11 ^ 00 = 11
11 ^ 11 = 00

圖1孩子的方向是0蜈首，1实抡，1欠母，2 欢策。圖2孩子的方向是3，2赏淌，2踩寇，1 。圖3孩子的方向是2六水，3俺孙，3辣卒，0 。和圖上畫的是完全一致的睛榄。

所以上面的轉(zhuǎn)換是很關(guān)鍵的荣茫。這里就是針對希爾伯特曲線的父子方向進行換算的。

最后會有讀者有疑問场靴，origOrientation 和 orientation 是啥關(guān)系啡莉？

lookupPos[(ij<<2)+origOrientation] = (pos << 2) + orientation
lookupIJ[(pos<<2)+origOrientation] = (ij << 2) + orientation

數(shù)組下標里面存的都是 origOrientation，下標里面存的值都是 orientation旨剥。

解釋完希爾伯特曲線方向的問題之后咧欣，接下來可以再仔細說說 55 的坐標轉(zhuǎn)換的問題。前一篇文章《高效的多維空間點索引算法 — Geohash 和 Google S2》里面有談到這個問題轨帜，讀者有些疑惑點魄咕，這里再最終解釋一遍。

在 Google S2 中蚌父，初始化 initLookupCell 的時候哮兰，會初始化2個數(shù)組，一個是 lookupPos 數(shù)組梢什，一個是 lookupIJ 數(shù)組奠蹬。中間還會用到 i ， j 嗡午， pos 和 orientation 四個關(guān)鍵的變量囤躁。orientation 這個之前說過了，這里就不再贅述了荔睹。需要詳細說明的 i 狸演，j 和 pos 的關(guān)系。

pos 指的是在 希爾伯特曲線上的位置僻他。這個位置是從 希爾伯特 曲線的起點開始算的宵距。從起點開始數(shù)，到當前是第幾塊方塊吨拗。注意這個方塊是由 4 個小方塊組成的大方塊满哪。因為 orientation 是選擇4個方塊中的哪一個。

在 55 的這個例子里劝篷，pos 其實是等于 13 的哨鸭。代表當前4塊小方塊組成的大方塊是距離起點的第13塊大方塊。由于每個大方塊是由4個小方塊組成的娇妓。所以當前這個大方塊的第一個數(shù)字是 13 * 4 = 52 像鸡。代碼實現(xiàn)就是左移2位，等價于乘以 4 哈恰。再加上 55 的偏移的 orientation = 11只估，再加 3 志群，所以 52 + 3 = 55 。

再說說 i 和 j 的問題蛔钙，在 55 的這個例子里面 i = 14锌云，1110，j = 13吁脱，1101 宾抓。如果直觀的看坐標系，其實 55 是在 (5豫喧，2) 的坐標上石洗。但是現(xiàn)在為何 i = 14，j = 13 呢 紧显？這里容易弄混的就是 i 讲衫，j 和 pos 的關(guān)系。

注意：
i孵班，j 并不是直接對應(yīng)的 希爾伯特曲線 坐標系上的坐標涉兽。因為初始化需要生成的是五階希爾伯特曲線。在 posToIJ 數(shù)組表示的一階希爾伯特曲線篙程，所以 i枷畏，j 才直接對應(yīng)的 希爾伯特曲線 坐標系上的坐標。

讀者到這里就會疑問了虱饿，那是什么參數(shù)對應(yīng)的是希爾伯特曲線坐標系上的坐標呢拥诡？

pos 參數(shù)對應(yīng)的就是希爾伯特曲線坐標系上的坐標。一旦一個希爾伯特曲線的起始點和階數(shù)確定以后氮发，四個小方塊組成的一個大方塊的 pos 位置確定以后渴肉，那么它的坐標其實就已經(jīng)確定了。希爾伯特曲線上的坐標并不依賴 i爽冕，j仇祭，完全是由曲線的性質(zhì)和 pos 位置決定的。

我們并不關(guān)心希爾伯特曲線上小方塊的坐標颈畸，我們關(guān)心的是 pos 和 i乌奇，j 的轉(zhuǎn)換關(guān)系！

疑問又來了眯娱，那 i礁苗，j 對應(yīng)的是什么坐標系上的坐標呢？

i困乒，j 對應(yīng)的是一個經(jīng)過坐標變換以后的坐標系坐標寂屏。

我們知道贰谣，在進行 ( u娜搂，v ) -> ( i迁霎，j ) 變換的時候，u百宇，v 的值域是 [0考廉，1] 之間，然后經(jīng)過變換要變到 [ 0, 2³⁰-1 ] 之間携御。i昌粤，j 就是變換以后坐標系上的坐標值涮坐，i誓军，j 的值域變成了 [ 0, 2³⁰-1 ] 袱讹。

那初始化計算 lookupPos 數(shù)組和 lookupIJ 數(shù)組有什么用呢昵时？這兩個數(shù)組就是把 i，j 和 pos 聯(lián)系起來的數(shù)組壹甥。知道 pos 以后可以立即找到對應(yīng)的 i救巷，j句柠。知道 i，j 以后可以立即找到對應(yīng)的 pos管怠。

i缸榄，j 和 pos 互相轉(zhuǎn)換之間的橋梁就是生成希爾伯特曲線的方式甚带。這種方式可以類比 Z - index 曲線的生成方式。

Z - index 曲線的生成方式是把經(jīng)緯度坐標分別進行區(qū)間二分晴氨，在左區(qū)間的記為0籽前，在右區(qū)間的記為1 。將這兩串二進制字符串偶數(shù)位放經(jīng)度肄梨，奇數(shù)位放緯度众羡，最終組合成新的二進制串蓖租，這個串再經(jīng)過 base-32 編碼以后蓖宦，最終就生成了 geohash 。

那么 希爾伯特 曲線的生成方式是什么呢尔店？它先將經(jīng)緯度坐標轉(zhuǎn)換成了三維直角坐標系坐標主慰，然后再投影到外切立方體的6個面上嚣州，于是三維直角坐標系坐標 (x共螺，y藐不，z) 就轉(zhuǎn)換成了 (face，u涎嚼，v) 法梯。 (face立哑，u姻灶，v) 經(jīng)過一個二次變換變成 (face产喉，s，t) 鸥昏， (face疤苹，s卧土，t) 經(jīng)過坐標系變換變成了 (face尤莺，i生棍，j) 涂滴。然后將 i柔纵，j 分別4位4位的取出來，i 的4位二進制位放前面或详，j 的4位二進制位放后面霸琴。最后再加上希爾伯特曲線的方向位 orientation 的2位梧乘。組成 iiii jjjj oo 類似這樣的10位二進制位宋下。通過 lookupPos 數(shù)組這個橋梁辑莫，找到對應(yīng)的 pos 的值各吨。pos 的值就是對應(yīng)希爾伯特曲線上的位置。然后依次類推剔桨，再取出 i 的4位洒缀，j 的4位進行這樣的轉(zhuǎn)換欺冀，直到所有的 i 和 j 的二進制都取完了隐轩，最后把這些生成的 pos 值安全先生成的放在高位职车，后生成的放在低位的方式拼接成最終的 CellID悴灵。

這里可能有讀者疑問了积瞒，為何要 iiii jjjj oo 這樣設(shè)計，為何是4位4位的空厌，谷歌開發(fā)者在注釋里面這樣寫道：“我們曾經(jīng)考慮過一次組合 16 位嘲更，14位的 position + 2位的 orientation赋朦，但是代碼實際運行起來發(fā)現(xiàn)小數(shù)組擁有更好的性能宠哄，2KB 更加適合存儲到主 cache 中嗤攻「玖猓”

在 Google S2 中，i仙粱，j 每次轉(zhuǎn)換都是4位伐割，所以 i隔心，j 的有效值取值是 0 - 15透揣，所以 iiii jjjj oo 是一個十進制的數(shù)辐真，能表示的范圍是 2¹⁰ = 1024 侍咱。那么 pos 初始化值也需要計算到 1024 楔脯。由于 pos 是4個小方塊組成的大方塊昧廷，它本身就是一個一階的希爾伯特曲線偎箫。所以初始化需要生成一個五階的希爾伯特曲線淹办。

上圖是一階的希爾伯特曲線怜森。是由4個小方格組成的副硅。

上圖是二階的希爾伯特曲線伶授，是由4個 pos 方格組成的。

上圖是三階的希爾伯特曲線。

上圖是四階的希爾伯特曲線诸迟。

上圖是五階的希爾伯特曲線阵苇。pos 方格總共有1024個绅项。

至此已經(jīng)說清楚了希爾伯特曲線的方向和在 Google S2 中生成希爾伯特曲線的階數(shù)快耿，五階希爾伯特曲線掀亥。

由此也可以看出妥色，希爾伯特曲線的是由 “ U ” 字形構(gòu)成的嘹害，由4個不同方向的 “ U ” 字構(gòu)成笔呀。初始方向是開口朝上的 “ U ”凿可。

關(guān)于希爾伯特曲線生成的動畫枯跑，見上篇《高效的多維空間點索引算法 — Geohash 和 Google S2》—— 希爾伯特曲線的構(gòu)造方法 這一章節(jié)敛助。

那么現(xiàn)在我們再推算55就比較簡單了纳击。從五階希爾伯特曲線開始推，推算過程如下圖纱昧。

首先55是在上圖中每個小圖中綠色點的位置识脆。我們不斷的進行方向的判斷灼捂。第一張小圖，綠點在00的位置宫蛆。第二張小圖耀盗，綠點在00的位置袍冷。第三張小圖，綠點在11的位置淌友。第四張小圖震庭，綠點在01的位置器联。第五張小圖拨拓，綠點在11的位置渣磷。其實換算到第四步醋界，得到的數(shù)值就是 pos 的值铁蹈，即 00001101 = 13 逐样。最后2位是具體的點在 pos 方格里面的位置官研，是11戏羽，所以 13 * 4 + 3 = 55 始花。

當然直接根據(jù)方向推算到底酷宵，也可以得到 0000110111 = 55 浇垦，同樣也是55 。

七. 舉例

最后舉個具體的完整的例子：

上面完成了前4步的轉(zhuǎn)換朴摊。

最后一步轉(zhuǎn)換成 CellID 甚纲。具體實現(xiàn)代碼如下介杆。由于 CellID 是64位的春哨，除去 face 占的3位悲靴，最后一個標志位 1 占的位置癞尚，剩下 60 位浇揩。

func cellIDFromFaceIJ(f, i, j int) CellID {
  // 1.
    n := uint64(f) << (posBits - 1)
  // 2.
    bits := f & swapMask
  // 3.
    for k := 7; k >= 0; k-- {
        mask := (1 << lookupBits) - 1
        bits += int((i>>uint(k*lookupBits))&mask) << (lookupBits + 2)
        bits += int((j>>uint(k*lookupBits))&mask) << 2
        bits = lookupPos[bits]
    // 4.
        n |= uint64(bits>>2) << (uint(k) * 2 * lookupBits)
    // 5.
        bits &= (swapMask | invertMask)
    }
  // 6.
    return CellID(n*2 + 1)
}

具體步驟如下：

1. 將 face 左移 60 位胳徽。
2. 計算初始的 origOrientation养盗。初始的 origOrientation 是 face 轉(zhuǎn)換得來的往核，face & 01 以后的結(jié)果是為了使每個面都有一個右手坐標系聂儒。
3. 循環(huán)衩婚，從頭開始依次取出 i 非春，j 的4位二進制位税娜，計算出 ij<<2 + origOrientation敬矩，然后查 lookupPos 數(shù)組找到對應(yīng)的 pos<<2 + orientation 弧岳。
4. 拼接 CellID禽炬，右移 pos<<2 + orientation 2位腹尖，只留下 pos 热幔，把pos 繼續(xù)拼接到 上次循環(huán)的 CellID 后面绎巨。
5. 計算下一個循環(huán)的 origOrientation戈锻。&= (swapMask | invertMask) 即 & 11格遭，也就是取出末尾的2位二進制位如庭。
6. 最后拼接上最后一個標志位 1 坪它。

這里說說第二步往毡，origOrientation 的轉(zhuǎn)換开瞭。

我們知道 face 是有6個面的嗤详，編號依次是 000葱色，001苍狰，010淋昭，011翔忽，100歇式，101 贬丛。想讓這6個面都具有右手坐標系的性質(zhì)额获，就必須進行轉(zhuǎn)換恭应，轉(zhuǎn)換的規(guī)則其實進行一次位運算即可：

000 & 001 = 00
001 & 001 = 01
010 & 001 = 00
011 & 001 = 01
100 & 001 = 00
101 & 001 = 01

經(jīng)過轉(zhuǎn)換以后抄邀，face & 01 的值就是初始的 origOrientation 了。

用表展示出每一步（表比較長昼榛，請右滑）：

任意取出循環(huán)中的一個情況潮秘，用圖表示如下：

注意：由于 CellID 是64位的琼开，頭三位是 face ，末尾一位是標志位枕荞，所以中間有 60 位柜候。i，j 轉(zhuǎn)換成二進制是30位的躏精。7個4位二進制位和1個2位二進制位渣刷。4*7 + 2 = 30 。iijjoo 矗烛，即 i 的頭2個二進制位和 j 的頭2個二進制位加上 origOrientation辅柴，這樣組成的是6位二進制位，最多能表示 2⁶ = 32瞭吃，轉(zhuǎn)換出來的 pos + orientation 最多也是32位的碌嘀。即轉(zhuǎn)換出來最多也是6位的二進制位，除去末尾2位 orientation 歪架，所以 pos 在這種情況下最多是 4位筏餐。iiiijjjjpppp，即 i 的4個二進制位和 j 的4個二進制位加上 origOrientation牡拇，這樣組成的是10位二進制位魁瞪，最多能表示 2¹⁰ = 1024，轉(zhuǎn)換出來的 pos + orientation 最多也是10位的惠呼。即轉(zhuǎn)換出來最多也是10位的二進制位导俘，除去末尾2位 orientation ，所以 pos 在這種情況下最多是 8位剔蹋。

由于最后 CellID 只拼接 pos 旅薄，所以 4 + 7 * 8 = 60 位。拼接完成以后泣崩，中間的60位都由 pos 組成的少梁。最后拼上頭3位，末尾的1位標志位矫付，64位的 CellID 就這樣生成了凯沪。

到此，所有的 CellID 生成過程就結(jié)束了买优。

空間搜索系列文章：

空間搜索系列文章：

如何理解 n 維空間和 n 維時空
高效的多維空間點索引算法 — Geohash 和 Google S2
Google S2 中的 CellID 是如何生成的 妨马？
Google S2 中的四叉樹求 LCA 最近公共祖先
神奇的德布魯因序列
四叉樹上如何求希爾伯特曲線的鄰居 挺举？

GitHub Repo：Halfrost-Field

Follow: halfrost · GitHub

Source: https://halfrost.com/go_s2_cellID/