地圖瓦片與四叉樹（二）

02-11

說到四叉樹，這裡又要插出一個話題說一說z order曲線。

在上圖中的黑色折線展示了一種遍歷瓦片的順序，仔細觀察這個折線的形狀可以發現類似於英文字母「z」，所以這種折線又叫做z order曲線或者morton order曲線，是空間填充曲線中的一種，基本上可以用來建四叉樹。

同時z order曲線也具有自相似的特點，例如上圖的節點遍歷順序為（1-00-00-->1-00-01-->1-00-10-->1-00-11）是一個「z」字形，他們的父節點順序為（1-00-->1-01-->1-10-->1-11）也是一個「z」字形，這就是所謂的分形曲線，是個很有意思的圖形，這裡不詳細說了。

z order也可以把一個位置點的經緯度編譯進去，這個編碼方式叫做morton code或者z code。比如下面的這個例子：

(x,y,z) = (5,9,1) = (0101,1001,0001)

坐標點p的xyz值分別為（5,9,1）以及對應的二進位數。

該點坐標的morton code就如下：

010-001-000-111

這串數字分別取x,y,z值（二進位數情況下）的每一位依次排序而成，這串數字轉換為十進位數為1095。

此外要注意的是，在常見的計算機系統中，最長的整型是64個bit，所以morton code也是64個bit，也就是說morton code是xy值組成的，x和y不要超過32個bit，如果是由xyz組成的，那麼x,y,z不要超過21個bit。

通常我們用經緯度來表示地球上的任意一個位置，緯度+-90度，經度+-180度，所以緯度用31個bit表示，經度用32個bit表示。

如 $x=x_{31}x_{30}…x_{0}$

$y=y_{30}y_{29}…y_{0}$

morton code為 $x_{31}y_{30}x_{30}…y_{1}x_{1}y_{0}x_{0}$

這個morton code一共是63個bit，剩下最後一個符號位為0，因此morton code就都是正數了。

世界著名景點的一些morton code

//生成morton codeunsigned short x; // Interleave bits of x and y, so that all of theunsigned short y; // bits of x are in the even positions and y in the odd;unsigned int z = 0; // z gets the resulting Morton Number.for (int i = 0; i < sizeof(x) * CHAR_BIT; i++) // unroll for more speed...{ z |= (x & 1U << i) << i | (y & 1U << i) << (i + 1);}

說了半天，morton code到底有什麼作用呢，morton code實際上提供了一種線性化空間坐標的方法，也就是說可以把空間坐標xy或xyz融合到一個整型數中去，因此廣泛的應用於空間檢索。下一個章節中我將詳細說一說用morton code做空間檢索。