我相信，很多人看到這個(gè)都是對google-s2有了解的，所以我在這里廢話就不多說了，直接進(jìn)入正題。

首先我們先看下目前都有什么資源

（1）GO源碼：github.com/golang/geo

（2）java源碼：github.com/google/s2-geometry-library-java

（3）唯一的pdf：pan.baidu.com/s/1gfxJB0J

然后我們理解一個(gè)概念：希爾伯特曲線（能夠連續(xù)的把平面填滿）

我們可以直觀的看到該曲線到底是什么，不理解的去

維基百科

轉(zhuǎn)轉(zhuǎn)吧。

下面，讓我們直觀的感受一下，google-s2是如何把空間地理位置進(jìn)行編碼的，如何映射到一位空間的編碼上的：bit-player.org/extras/hilbert/hilbert-mapping.html

請打開連接，隨便點(diǎn)點(diǎn)吧，你會(huì)感覺很神奇。

不用懷疑了，你猜對了，原圖都在這里：blog.christianperone.com/2015/08/googles-s2-geometry-on-the-sphere-cells-and-hilbert-curve/

到這點(diǎn)，我覺得是時(shí)候你去拜讀一下這個(gè)連接了。

到現(xiàn)在，也許會(huì)有人問，為什么不用geohash而搞這玩意干啥？

你可以到這里看一下是為什么：www.tuicool.com/articles/UnEZvm

Why not Geohash?

（1）Geohash is a great solution to perform geo coordinates queries but the way it works can sometimes be an issue with your data.

（2）Remember geohashes are cells of 12 different widths from 5000km to 3.7cm, when you perform a lookup around a position, if your position is close to a cell’s edge you could miss some points from the adjacent cell, that’s why you have to query for the 8 neightbour cells, it means 9 range queries into your DB to find all the closest points from your location.

（3）If your lookup does not fit in level439km by 19.5km, the next level is 156km by 156km!

（4）The query is not performed around your coordinates, you search for the cell you are in then you query for the adjacent cells at the same level/radius, based on your needs, it means it works very approximately and you can only perform ‘circles’ lookup around the cell you are in.

（5）The most precise geohash needs 12 bytes storage.

（6）-90 +90 and +180 -180, -0 +0 are not sides by sides prefixes.

Why S2?

（1）S2 cells have a level ranging from30~0.7cm2 to0~85,000,000km2.

（2）S2 cells are encoded on an uint64, easy to store.

（3）The main advantage is the?region coverer algorithm, give it a region and the maximum number of cells you want, S2 will return some cells atdifferent levels that cover the region you asked for, remember one cell corresponds to a range lookup you’ll have to perform in your database.

（4）The coverage is more accurate it means less read from the DB, less objects unmarshalling…

看到這里，你是不是很想知道，google-s2的來龍去脈，那就跟我一塊解開里邊神秘的面紗吧。

首先就是經(jīng)緯度如何轉(zhuǎn)換成三圍空間坐標(biāo)即：Point(lat, lng) ==> (x, y, z)

轉(zhuǎn)化成如下：

如果看不懂，補(bǔ)一下數(shù)學(xué)吧。

找不到的話我就給你提供一個(gè)地方：球坐標(biāo)系

其實(shí)，在我們現(xiàn)在討論的問題大可不考慮 r 因?yàn)檫@個(gè)就是地球的半徑，是個(gè)常量，不考慮就可以

那么，x, y, z就被局限在一個(gè)立方體里邊了（[-1, 1], [-1, 1], [-1, 1]）

說到這里，我想你應(yīng)該明白了吧？

如果你還不明白，請繼續(xù)往下看吧

NOW ： 讓我們閉上眼睛，想象你的前方有一個(gè)地球，地球外表有個(gè)正立方體，剛好與地球外切。

然后，請你想想一下，你右手就是一把快刀，從中間劈下去！對，狠狠的劈下去

讓我們來看一下你的成果，你的切面

不錯(cuò)，地球成了兩半，我們只看被你傷過的切面

p呢，就是地球上的一個(gè)點(diǎn)，p的坐標(biāo)呢我們可以表示成三圍坐標(biāo)系的空間坐標(biāo)（x,y,z）不信，你就再看看上邊吧，誰讓你數(shù)學(xué)不好呢。

到這里，我們可不可以瘋狂的想想一下吧，發(fā)散你的思維

假如說我們能把地球上的經(jīng)緯度，能夠放到外切立方體上那該多好，那么，立方體可以這樣

玩過拼圖嗎？我們可以拼拼，最后我們拼成一個(gè)矩形

到這里，你應(yīng)該自豪一下，整個(gè)世界的每個(gè)坐標(biāo)都被你撕成了一個(gè)平面

不懂？

那我們回頭去看那個(gè)p和那個(gè)紅線，p點(diǎn)通過紅線是不是可以映射到到正立方體的一個(gè)面上？

想象一下，整個(gè)地球的所有坐標(biāo)是不是都能夠按照這個(gè)方式映射到這個(gè)神奇的立方體的面上，

所以，這樣我們就能把地球上的每個(gè)坐標(biāo)與立方體面上的每個(gè)點(diǎn)做一一映射。

然而、、、、、、（是不是感覺為什么會(huì)有然而？）

我們，還是看看為什么說然而吧，我們知道

那么問題就來了，我們把地球上每個(gè)方格映射到一個(gè)立方體面上很可能就會(huì)出現(xiàn)如下的情況

大概是這樣字，畫的不好，將就著看吧。

也就是每個(gè)被映射過來的方格的面積是不均勻的。為了讓他們均勻，我們要對每個(gè)地球上的坐標(biāo)做一次空間變換

在google-s2中提供了三種變換形式( -1 < u < 1)

（1）線性變換，就是不做任何處理，就是跟上圖差不多

（2）針對（x,y）每個(gè)值u，做

（3）針對（x,y）每個(gè)值u，做

如果u > 0

如果u < 0

到這里你會(huì)想，為什么google會(huì)選這兩個(gè)函數(shù)

那就讓我們看一下這兩個(gè)函數(shù)在[-1,1]上的圖形吧

上邊是（2）下邊是（3）

看曲線的走勢，中間斜率大，兩端斜率區(qū)域平緩，轉(zhuǎn)換以后就是把邊緣的方格縮小，把中間的小的方格放大，當(dāng)然也不是無限放大，只是略微的調(diào)整，使得，影射在立方體面上的方格盡量的均勻化。（當(dāng)然，優(yōu)化的映射過程你也可以找到一個(gè)更好的，這也是一個(gè)優(yōu)化的方向）

到這里，我們完成了把地球上畫的方格全部映射到了外切立方體的面上了

下面就是如何給每個(gè)方格編碼了

總共有六個(gè)面，不難想到，編碼肯定跟面也有關(guān)系

其實(shí)在這個(gè)過程中就隱含了把點(diǎn)映射到希爾伯特曲線的邏輯

下面就介紹一下如何把點(diǎn)映射到希爾伯特曲線上

為了更好的理解這個(gè)問題，我們借鑒一下：blog.jobbole.com/81106/（版權(quán)歸原創(chuàng)所有）

原文核心觀點(diǎn)：曲線規(guī)定了平面上點(diǎn)的順序。如果我們用這順序來表達(dá)希爾伯特曲線，畫曲線就不

值一提了。

希爾伯特曲線規(guī)定了二維平面上的點(diǎn)的順序

在根這一層，列舉點(diǎn)很簡單：選定一個(gè)方向和一個(gè)起始點(diǎn)，環(huán)繞四個(gè)象限，用0到3給他們編號(hào)。當(dāng)

我們要確定訪問子象限的順序同時(shí)維護(hù)總體的鄰接屬性，困難就來了。通過檢查我們發(fā)現(xiàn)，子象限

的曲線是原曲線的簡單變換，而且只有四種變換。自然地，這個(gè)結(jié)論也適用于子子象限，等等。對

于一個(gè)給定的象限，我們在其中畫出的曲線是由象限所在大的方形的曲線以及該象限的位置決定

的。只需要費(fèi)一點(diǎn)力，我們就能構(gòu)建出如下概況所有情況的表。

不同根順序的子象限的循序列舉

假設(shè)我們想用這個(gè)表來確定某個(gè)點(diǎn)在第三層希爾伯特曲線上的位置。在這個(gè)例子中，假設(shè)點(diǎn)的坐標(biāo)

是(5,2)。（譯者注：請參照下圖）從上圖的第一個(gè)方形開始，找到你的點(diǎn)所在的象限。在這個(gè)例子

中，是在右上方的象限。那么點(diǎn)在希爾伯特曲線上的位置的第一部分是3（二進(jìn)制是11）。接著我們

進(jìn)入象限3里面的方塊，在這個(gè)例子中，它是（上圖中的）第二個(gè)方塊。重復(fù)剛才的過程：我們的點(diǎn)

落在哪個(gè)子象限？這次是左下角，意味著位置的下一部分是1（二進(jìn)制01），我們將進(jìn)入的小方塊又

是第二個(gè)。最后一次重復(fù)這個(gè)過程，發(fā)現(xiàn)點(diǎn)落在右上角的子子象限，因此位置的最后部分是3（二進(jìn)

制11）。把這些位置連接起來，我們得到點(diǎn)在曲線上的位置是二進(jìn)制的110111，或者十進(jìn)制的55。

三階希爾伯特曲線

就這樣我們也知道了點(diǎn)如何映射在希爾伯俄曲線上了。

那么問題又來了，我們?nèi)绾未_定x,y兩個(gè)邊上的方格編號(hào)呢？

在google-s2源碼中，是這樣確認(rèn)的

首先我們拿到最后映射到立方體面上的一個(gè)點(diǎn)(s , t)已經(jīng)經(jīng)過均勻化變化的

默認(rèn)的，我們先進(jìn)入30層的曲線填充，把平面每個(gè)緯度分成2^30 - 1個(gè)方格

平面方格分割

現(xiàn)在我們就是為了找到那個(gè)（i, j）來確認(rèn)方格所在位置，假設(shè)粉紅色的就是p點(diǎn)映射的方格

p是（s, t） 其中 -1 < s , t< 1

為了找到方格的位置源碼中是這樣做的

Math.max(0,Math.min(2*m-1,Math.round(m*s+(m-0.5))))

其中MAX_SIZE = 2^30

其實(shí)這段代碼就是為了計(jì)算（s, t）==>（i, j）即方格的位置，可以配合下圖進(jìn)行理解

方格坐標(biāo)計(jì)算參考圖

其實(shí)m就可以理解為被黃線坐標(biāo)系分割后某一個(gè)區(qū)域在橫向或者縱向的緯度上的方格個(gè)數(shù)

比如說計(jì)算i 的值，首先需要s 的值，s就是在[-1, 1]上的一種坐標(biāo)，現(xiàn)在要映射到[0, 2^30-1]上

也就是[0, 1] 被映射到 [（2^30-1）/2, ?2^30-1] 即 [m-0.5, 2m-1]

為了計(jì)算p 的i 拿m*s + （2^30-1）/2也就是m*s + （m-0.5）就是i 的坐標(biāo)

并其整個(gè)過程就是從地位連續(xù)空間向高維離散空間的一種離散化，這樣也就是任意點(diǎn)到希爾伯特曲線上映射的過程

最后，就讓我們一塊了解一下，編碼是如何做的

我們都知道，geohash的編碼方式是經(jīng)緯度交叉進(jìn)行的，那么，s2的呢？

見證奇跡的時(shí)候到了

秀色可餐的美食

燒了半天腦，是不是覺得無法抵抗這種誘惑？

其實(shí)，我也是、、、

但是，革命尚未成功，我們豈能糾結(jié)于美食？

編碼：

編碼框架圖

給出一個(gè)level=2的案例

編碼考慮了面的屬性，和希爾伯特曲線，具體的實(shí)現(xiàn)可以看下源碼，這里不再過多贅述。

最后總結(jié)一下，只發(fā)圖，不多說