關(guān)于鄰居的定義顿锰，相鄰即為鄰居，那么鄰居分為2種启搂，邊相鄰和點相鄰硼控。邊相鄰的有4個方向，上下左右胳赌。點相鄰的也有4個方向牢撼，即4個頂點相鄰的。
如上圖疑苫，綠色的區(qū)域是一顆四叉樹表示的范圍熏版，四叉樹上面有一個點，圖中黃色區(qū)域標(biāo)明的點『床簦現(xiàn)在想求四叉樹上黃色的點的希爾伯特曲線鄰居撼短。圖中黑色的線就是一顆穿過四叉樹的希爾伯特曲線。希爾伯特曲線的起點0在左上角的方格中乡小，終點63在右上角的方格中阔加。
紅色的四個格子是黃色格子邊相鄰鄰居，藍色的四個格子是黃色格子的頂點相鄰的鄰居满钟，所以黃色格子的鄰居為8個格子胜榔，分別表示的點是8，9湃番，54夭织，11，53吠撮，30尊惰，31，32 泥兰∨牛可以看出來這些鄰居在表示的點上面并不是相鄰的。
那么怎么求四叉樹上任意一點的希爾伯特曲線鄰居呢鞋诗？
一. 邊鄰居
邊鄰居最直接的想法就是 先拿到中心點的坐標(biāo) (i膀捷，j) ，然后通過坐標(biāo)系的關(guān)系削彬，拿到與它邊相鄰的 Cell 的坐標(biāo) (i + 1全庸，j) 秀仲， (i - 1，j) 壶笼， (i神僵，j - 1) ， (i覆劈，j + 1) 保礼。
實際做法也是如此。不過這里涉及到需要轉(zhuǎn)換的地方墩崩。這里需要把希爾伯特曲線上的點轉(zhuǎn)換成坐標(biāo)以后才能按照上面的思路來計算邊鄰居氓英。
關(guān)于 CellID 的生成與數(shù)據(jù)結(jié)構(gòu)侯勉，見筆者這篇《Google S2 中的 CellID 是如何生成的 鹦筹？》
按照上述的思路，實現(xiàn)出來的代碼如下：
func (ci CellID) EdgeNeighbors() [4]CellID {
level := ci.Level()
size := sizeIJ(level)
f, i, j, _ := ci.faceIJOrientation()
return [4]CellID{
cellIDFromFaceIJWrap(f, i, j-size).Parent(level),
cellIDFromFaceIJWrap(f, i+size, j).Parent(level),
cellIDFromFaceIJWrap(f, i, j+size).Parent(level),
cellIDFromFaceIJWrap(f, i-size, j).Parent(level),
}
}
邊按照址貌，下邊铐拐，右邊，上邊练对，左邊遍蟋，逆時針的方向依次編號0，1螟凭，2虚青，3 。
接下來具體分析一下里面的實現(xiàn)螺男。
func sizeIJ(level int) int {
return 1 << uint(maxLevel-level)
}
sizeIJ 保存的是當(dāng)前 Level 的格子邊長大小棒厘。這個大小是相對于 Level 30 來說的。比如 level = 29下隧，那么它的 sizeIJ 就是2奢人，代表 Level 29 的一個格子邊長是由2個 Level 30 的格子組成的，那么也就是22=4個小格子組成的淆院。如果是 level = 28何乎，那么邊長就是4，由16個小格子組成土辩。其他都以此類推支救。
func (ci CellID) faceIJOrientation() (f, i, j, orientation int) {
f = ci.Face()
orientation = f & swapMask
nbits := maxLevel - 7*lookupBits // first iteration
for k := 7; k >= 0; k-- {
orientation += (int(uint64(ci)>>uint64(k*2*lookupBits+1)) & ((1 << uint((2 * nbits))) - 1)) << 2
orientation = lookupIJ[orientation]
i += (orientation >> (lookupBits + 2)) << uint(k*lookupBits)
j += ((orientation >> 2) & ((1 << lookupBits) - 1)) << uint(k*lookupBits)
orientation &= (swapMask | invertMask)
nbits = lookupBits // following iterations
}
// 下面這個判斷詳細解釋
if ci.lsb()&0x1111111111111110 != 0 {
orientation ^= swapMask
}
return
}
這個方法就是把 CellID 再分解回原來的 i 和 j。這里具體的過程在筆者這篇《Google S2 中的 CellID 是如何生成的 拷淘？》里面的 cellIDFromFaceIJ 方法里面有詳細的敘述各墨，這里就不再贅述了。cellIDFromFaceIJ 方法和 faceIJOrientation 方法是互為逆方法辕棚。
cellIDFromFaceIJ 是把 face欲主，i邓厕，j 這個當(dāng)入?yún)鬟M去，返回值是 CellID扁瓢，faceIJOrientation 是把 CellID 分解成 face详恼，i，j引几，orientation昧互。faceIJOrientation 比 cellIDFromFaceIJ 分解出來多一個 orientation。
這里需要重點解釋的是 orientation 怎么計算出來的伟桅。
我們知道 CellID 的數(shù)據(jù)結(jié)構(gòu)是 3位 face + 60位 position + 1位標(biāo)志位。那么對于 Level - n 的非葉子節(jié)點楣铁，3位 face 之后玖雁，一定是有 2 * n 位二進制位，然后緊接著 2*(maxLevel - n) + 1 位以1開頭的盖腕，末尾都是0的二進制位赫冬。maxLevel = 30 。
例如 Level - 16溃列，中間一定是有32位二進制位劲厌，然后緊接著 2*(30 - 16) + 1 = 29位。這29位是首位為1听隐，末尾為0組成的补鼻。3 + 32 + 29 = 64 位。64位 CellID 就這樣組成的雅任。
當(dāng) n = 30风范，3 + 60 + 1 = 64，所以末尾的1并沒有起任何作用椿访。當(dāng) n = 29乌企，3 + 58 + 3 = 64，于是末尾一定是 100 組成的成玫。10對方向并不起任何作用加酵，最后多的一個0也對方向不起任何作用。關(guān)鍵就是看10和0之間有多少個00 哭当。當(dāng) n = 28猪腕，3 + 56 + 5 = 64，末尾5位是 10000钦勘，在10和0之間有一個“00”陋葡。“00”是會對方向產(chǎn)生影響彻采，初始的方向應(yīng)該再異或 01 才能得到腐缤。
關(guān)于 “00” 會對原始的方向產(chǎn)生影響捌归，這點其實比較好理解。CellID 從最先開始的方向進行四分岭粤，每次四分都將帶來一次方向的變換惜索。直到變換到最后一個4個小格子的時候，方向就不會變化了剃浇，因為在4個小格子之間就可以唯一確定是哪一個 Cell 被選中巾兆。所以這也是上面看到了， Level - 30 和 Level - 29 的方向是不變的虎囚，除此以外的 Level 是需要再異或一次 01 角塑，變換以后得到原始的 orientation。
最后進行轉(zhuǎn)換淘讥，具體代碼實現(xiàn)如下：
func cellIDFromFaceIJWrap(f, i, j int) CellID {
// 1.
i = clamp(i, -1, maxSize)
j = clamp(j, -1, maxSize)
// 2.
const scale = 1.0 / maxSize
limit := math.Nextafter(1, 2)
u := math.Max(-limit, math.Min(limit, scale*float64((i<<1)+1-maxSize)))
v := math.Max(-limit, math.Min(limit, scale*float64((j<<1)+1-maxSize)))
// 3.
f, u, v = xyzToFaceUV(faceUVToXYZ(f, u, v))
return cellIDFromFaceIJ(f, stToIJ(0.5*(u+1)), stToIJ(0.5*(v+1)))
}
轉(zhuǎn)換過程總共分為三步圃伶。第一步先處理 i，j 邊界的問題适揉。第二步留攒，將 i，j 轉(zhuǎn)換成 u嫉嘀，v 。第三步魄揉，u剪侮，v 轉(zhuǎn) xyz，再轉(zhuǎn)回 u洛退，v瓣俯，最后轉(zhuǎn)回 CellID 。
第一步：
func clamp(x, min, max int) int {
if x < min {
return min
}
if x > max {
return max
}
return x
}
clamp 函數(shù)就是用來限定 i 兵怯， j 的范圍的彩匕。i，j 的范圍始終限定在 [-1媒区，maxSize] 之間驼仪。
第二步：
最簡單的想法是將（i，j）坐標(biāo)轉(zhuǎn)換為（x袜漩，y绪爸，z）（這個點不在邊界上），然后調(diào)用 xyzToFaceUV 方法投影到對應(yīng)的 face 上宙攻。
我們知道在生成 CellID 的時候奠货，stToUV 的時候，用的是一個二次變換：
func stToUV(s float64) float64 {
if s >= 0.5 {
return (1 / 3.) * (4*s*s - 1)
}
return (1 / 3.) * (1 - 4*(1-s)*(1-s))
}
但是此處座掘，我們用的變換就簡單一點递惋，用的是線性變換柔滔。
u = 2 * s - 1
v = 2 * t - 1
u，v 的取值范圍都被限定在 [-1萍虽，1] 之間廊遍。具體代碼實現(xiàn)：
const scale = 1.0 / maxSize
limit := math.Nextafter(1, 2)
u := math.Max(-limit, math.Min(limit, scale*float64((i<<1)+1-maxSize)))
v := math.Max(-limit, math.Min(limit, scale*float64((j<<1)+1-maxSize)))
第三步：找到葉子節(jié)點，把 u贩挣，v 轉(zhuǎn)成 對應(yīng) Level 的 CellID喉前。
f, u, v = xyzToFaceUV(faceUVToXYZ(f, u, v))
return cellIDFromFaceIJ(f, stToIJ(0.5*(u+1)), stToIJ(0.5*(v+1)))
這樣就求得了一個 CellID 。
由于邊有4條邊王财，所以邊鄰居有4個卵迂。
return [4]CellID{
cellIDFromFaceIJWrap(f, i, j-size).Parent(level),
cellIDFromFaceIJWrap(f, i+size, j).Parent(level),
cellIDFromFaceIJWrap(f, i, j+size).Parent(level),
cellIDFromFaceIJWrap(f, i-size, j).Parent(level),
}
上面數(shù)組里面分別會裝入當(dāng)前 CellID 的下邊鄰居，右邊鄰居绒净，上邊鄰居见咒，左邊鄰居。
如果在地圖上顯示出來的話挂疆，就是下圖的這樣子改览。
中間方格的 CellID = 3958610196388904960 , Level 10 。按照上面的方法求出來的邊鄰居缤言，分別是：
3958603599319138304 // 下邊鄰居
3958607997365649408 // 右邊鄰居
3958612395412160512 // 上邊鄰居
3958599201272627200 // 左邊鄰居
在地圖上展示出來：
二. 共頂點鄰居
這里的共頂點鄰居和文章開始講的頂點鄰居有點區(qū)別宝当。并且下面還會有一些看似奇怪的例子，也是筆者在實際編碼中踩過的坑胆萧，分享一下庆揩。
這里先說明一種特殊情況，即 Cell 正好在地球的外切立方體的8個頂點上跌穗。那么這個點的頂點鄰居只有3個订晌，而不是4個。因為這8個頂點每個點只有3個面與其連接蚌吸，所以每個面上有且只有一個 Cell 是它們的頂點鄰居锈拨。除去這8個點以外的 Cell 的頂點鄰居都有4個！
j
|
| (0,1) (1,1)
| (0,0) (1,0)
|
---------------> i
在上述的坐標(biāo)軸中羹唠，i 軸方向如果為1奕枢，就落在4個象限的右邊一列上。如果 j 軸方向如果為肉迫，就落在4個象限的上面一行上验辞。
假設(shè) Cell Level 不等于 30，即末尾標(biāo)志位1后面還有0喊衫，那么這種 Cell 轉(zhuǎn)換成 i跌造，j 以后，i，j 的末尾就都是1 壳贪。
上面的結(jié)論可以證明的陵珍，因為在 faceIJOrientation 函數(shù)拆分 Cell 的時候，如果遇到了都是0的情況违施，比如 orientation = 11互纯，Cell 末尾都是0，那么取出末尾8位加上orientation磕蒲，00000000 11留潦，經(jīng)過 lookupIJ 轉(zhuǎn)換以后得到 1111111111 ，于是 i = 1111辣往，j = 1111 兔院，方向還是 11。Cell 末尾的00還是繼續(xù)循環(huán)上述的過程站削，于是 i坊萝，j 末尾全是1111 了。
所以我們只需要根據(jù) i许起，j 判斷入?yún)⒔o的 Level 在哪個象限十偶，就可以把共頂點的鄰居都找到。
假設(shè)入?yún)⒔o定的 Level 小园细，即 Cell 的面積大惦积，那么就需要判斷當(dāng)前 Cell (函數(shù)調(diào)用者) 的共頂點是位于入?yún)?Cell 的4個頂點的哪個頂點上。Cell 是一個矩形珊肃，有4個頂點荣刑。當(dāng)前 Cell (函數(shù)調(diào)用者) 離哪個頂點近，就選那個頂點為公共頂點伦乔。再依次求出以公共頂點周圍的4個 Cell 即可。
假設(shè)入?yún)⒔o定的 Level 大董习，即 Cell 的面積小烈和，那么也需要判斷入?yún)?Cell 的共頂點是位于當(dāng)前 Cell (函數(shù)調(diào)用者)的4個頂點的哪個頂點上。Cell 是一個矩形皿淋，有4個頂點招刹。入?yún)?Cell 離哪個頂點近，就選那個頂點為公共頂點窝趣。再依次求出以公共頂點周圍的4個 Cell 即可疯暑。
由于需要判斷位于一個 Cell 的四等分的哪一個幽歼，所以需要判斷它的4個孩子的位置情況鹦牛。即判斷 Level - 1 的孩子的相對位置情況誉察。
halfSize := sizeIJ(level + 1)
size := halfSize << 1
f, i, j, _ := ci.faceIJOrientation()
var isame, jsame bool
var ioffset, joffset int
這里需要拿到 halfSize 蓖捶，halfSize 其實就是入?yún)?Cell 的孩子的格子的 size 绞吁。
if i&halfSize != 0 {
// 位于后邊一列，所以偏移量要加上一個格子
ioffset = size
isame = (i + size) < maxSize
} else {
// 位于左邊一列绍些，所以偏移量要減去一個格子
ioffset = -size
isame = (i - size) >= 0
}
這里我們根據(jù) halfSize 那一位是否為1來判斷距離矩形的4個頂點哪個頂點近可训。這里還需要注意的是，如果 i + size 不能超過 maxSize甘凭，如果超過了稀拐，就不在同一個 face 上了。同理丹弱， i - size 也不能小于 0德撬，小于0頁不在同一個 face 上了。
j 軸判斷原理和 i 完全一致躲胳。
if j&halfSize != 0 {
// 位于上邊一行蜓洪，所以偏移量要加上一個格子
joffset = size
jsame = (j + size) < maxSize
} else {
// 位于下邊一行，所以偏移量要減去一個格子
joffset = -size
jsame = (j - size) >= 0
}
最后計算結(jié)果泛鸟，先把入?yún)⒌?Cell 先計算出來蝠咆，然后在把它周圍2個軸上的 Cell 計算出來。
results := []CellID{
ci.Parent(level),
cellIDFromFaceIJSame(f, i+ioffset, j, isame).Parent(level),
cellIDFromFaceIJSame(f, i, j+joffset, jsame).Parent(level),
}
如果 i北滥，j 都在同一個 face 上刚操，那么共頂點就肯定不是位于外切立方體的8個頂點上了。那么就可以再把第四個共頂點的 Cell 計算出來再芋。
if isame || jsame {
results = append(results, cellIDFromFaceIJSame(f, i+ioffset, j+joffset, isame && jsame).Parent(level))
}
綜上菊霜，完整的計算共頂點鄰居的代碼實現(xiàn)如下：
func (ci CellID) VertexNeighbors(level int) []CellID {
halfSize := sizeIJ(level + 1)
size := halfSize << 1
f, i, j, _ := ci.faceIJOrientation()
fmt.Printf("halfsize 原始的值 = %v-%b\n", halfSize, halfSize)
var isame, jsame bool
var ioffset, joffset int
if i&halfSize != 0 {
// 位于后邊一列，所以偏移量要加上一個格子
ioffset = size
isame = (i + size) < maxSize
} else {
// 位于左邊一列济赎，所以偏移量要減去一個格子
ioffset = -size
isame = (i - size) >= 0
}
if j&halfSize != 0 {
// 位于上邊一行鉴逞，所以偏移量要加上一個格子
joffset = size
jsame = (j + size) < maxSize
} else {
// 位于下邊一行，所以偏移量要減去一個格子
joffset = -size
jsame = (j - size) >= 0
}
results := []CellID{
ci.Parent(level),
cellIDFromFaceIJSame(f, i+ioffset, j, isame).Parent(level),
cellIDFromFaceIJSame(f, i, j+joffset, jsame).Parent(level),
}
if isame || jsame {
results = append(results, cellIDFromFaceIJSame(f, i+ioffset, j+joffset, isame && jsame).Parent(level))
}
return results
}
下面來舉幾個例子司训。
第一個例子是相同大小 Cell 构捡。入?yún)⒑驼{(diào)用者 Cell 都是相同 Level - 10 的。
VertexNeighbors := cellID.Parent(10).VertexNeighbors(10)
// 11011011101111110011110000000000000000000000000000000000000000
3958610196388904960 // 右上角
3958599201272627200 // 左上角
3958603599319138304 // 右下角
3958601400295882752 // 左下角
第二個例子是不是大小的 Cell 壳猜。調(diào)用者 Cell 是默認 Level - 30 的勾徽。
VertexNeighbors := cellID.VertexNeighbors(10)
// 11011011101111110011110000000000000000000000000000000000000000
3958610196388904960 // 右下角
3958599201272627200 // 左下角
3958612395412160512 // 右上角
3958623390528438272 // 左上角
上面兩個例子可以說明一個問題，同樣是調(diào)用 VertexNeighbors(10) 得到的 Cell 都是 Level - 10 的统扳，但是方向和位置是不同的喘帚。本質(zhì)在它們共的頂點是不同的，所以生成出來的4個Cell生成方向也就不同咒钟。
在 C++ 的版本中吹由，查找頂點鄰居有一個限制：
DCHECK_LT(level, this->level());
入?yún)⒌?Level 必須嚴(yán)格的比要找的 Cell 的 Level 小才行。也就是說入?yún)⒌?Cell 的格子面積大小要比 Cell 格子大小更小才行朱嘴。但是在 Go 的版本實現(xiàn)中并沒有這個要求倾鲫，入?yún)⒒虼蠡蛐《伎梢浴?/p>
下面這個舉例，入?yún)⒈?Cell 的 Level 小。（可以看到成都市已經(jīng)小成一個點了）
VertexNeighbors := cellID.Parent(10).VertexNeighbors(5)
3957538172551823360 // 右下角
3955286372738138112 // 左下角
3959789972365508608 // 右上角
3962041772179193856 // 左上角
下面這個舉例级乍，入?yún)⒈?Cell 的 Level 大舌劳。（可以看到 Level 15 的面積已經(jīng)很小了）
VertexNeighbors := cellID.Parent(10).VertexNeighbors(15)
3958610197462646784 // 左下角
3958610195315163136 // 右下角
3958610929754570752 // 左上角
3958609463023239168 // 右上角
三. 全鄰居
最后回來文章開頭問的那個問題中。如何在四叉樹上如何求希爾伯特曲線的鄰居 玫荣？經(jīng)過前文的一些鋪墊甚淡，再來看這個問題，也許讀者心里已經(jīng)明白該怎么做了捅厂。
查找全鄰居有一個要求贯卦，就是入?yún)⒌?Level 的面積必須要比調(diào)用者 Cell 的小或者相等。即入?yún)?Level 值不能比調(diào)用者的 Level 小焙贷。因為一旦小了以后撵割，鄰居的 Cell 的面積變得巨大，很可能一個鄰居的 Cell 里面就裝滿了原來 Cell 的所有鄰居辙芍，那這樣的查找并沒有任何意義啡彬。
舉個例子，如果入?yún)⒌?Level 比調(diào)用者 Cell 的 Level 小故硅。那么查找它的全鄰居的時候庶灿，查出來會出現(xiàn)如下的情況：
AllNeighbors := cellID.Parent(10).AllNeighbors(5)
這個時候是可以查找到全鄰居的，但是可能會出現(xiàn)重疊 Cell 的情況吃衅，為何會出現(xiàn)這樣的現(xiàn)象往踢，下面再分析。
如果入?yún)⒑驼{(diào)用者 Cell 的 Level 是相同的徘层，那么查找到的全鄰居就是文章開頭說到的問題了峻呕。理想狀態(tài)如下：
具體實現(xiàn)如下：
func (ci CellID) AllNeighbors(level int) []CellID {
var neighbors []CellID
face, i, j, _ := ci.faceIJOrientation()
// 尋找最左下角的葉子節(jié)點的坐標(biāo)。我們需要規(guī)范 i趣效，j 的坐標(biāo)瘦癌。因為入?yún)?Level 有可能比調(diào)用者 Cell 的 Level 要大。
size := sizeIJ(ci.Level())
i &= -size
j &= -size
nbrSize := sizeIJ(level)
for k := -nbrSize; ; k += nbrSize {
var sameFace bool
if k < 0 {
sameFace = (j+k >= 0)
} else if k >= size {
sameFace = (j+k < maxSize)
} else {
sameFace = true
// 上邊鄰居 和 下邊鄰居
neighbors = append(neighbors, cellIDFromFaceIJSame(face, i+k, j-nbrSize,
j-size >= 0).Parent(level))
neighbors = append(neighbors, cellIDFromFaceIJSame(face, i+k, j+size,
j+size < maxSize).Parent(level))
}
// 左邊鄰居跷敬，右邊鄰居佩憾，以及2個對角線上的頂點鄰居
neighbors = append(neighbors, cellIDFromFaceIJSame(face, i-nbrSize, j+k,
sameFace && i-size >= 0).Parent(level))
neighbors = append(neighbors, cellIDFromFaceIJSame(face, i+size, j+k,
sameFace && i+size < maxSize).Parent(level))
// 這里的判斷條件有2個用途，一是防止32-bit溢出干花，二是循環(huán)的退出條件，大于size以后也就不用再找了
if k >= size {
break
}
}
return neighbors
}
上述代碼簡單的思路用注釋寫了楞黄。需要講解的部分現(xiàn)在來講解池凄。
首先需要理解的是 nbrSize 和 size 的關(guān)系。為何會有 nbrSize 鬼廓？ 因為入?yún)?Level 是可以和調(diào)用者 Cell 的 Level 不一樣的肿仑。入?yún)⒌?Level 代表的 Cell 可大可小也可能相等。最終結(jié)果是以 nbrSize 格子大小來表示的，所以循環(huán)中需要用 nbrSize 來控制格子的大小尤慰。而 size 只是原來調(diào)用者 Cell 的格子大小馏锡。
循環(huán)中 K 的變化，當(dāng) K = -nbrSize 的時候伟端，這個時候循環(huán)只會計算左邊和右邊的鄰居杯道。對角線上的頂點鄰居其實也是左邊鄰居和右邊鄰居的一種特殊情況。接下來 K = 0责蝠，就會開始計算上邊鄰居和下邊鄰居了党巾。K 不斷增加，直到最后 K >= size 霜医，最后一次循環(huán)內(nèi)齿拂，會先計算一次左邊和右邊鄰居，再 break 退出肴敛。
調(diào)用者的 Cell 在中間位置署海，所以想要跳過這個 Cell 到達另外一邊(上下，或者左右)医男，那么就需要跳過 size 的大小砸狞。具體代碼實現(xiàn)是 i + size 和 j + size 。
先看左右鄰居的循環(huán)掃描方式昨登。
左鄰居是 i - nbrSize趾代，j + k，k 在循環(huán)丰辣。這表示的就是左鄰居的生成方式撒强。它生成了左鄰居一列。從左下角開始生成笙什，一直往上生成到左上角飘哨。
右鄰居是 i + size，j + k琐凭，k 在循環(huán)芽隆。這表示的就是右鄰居的生成方式。它生成了右鄰居一列统屈。從右下角開始生成胚吁，一直往上生成到右上角。
再看上下鄰居的循環(huán)掃描方式愁憔。
下鄰居是 i + k腕扶，j - nbrSize，k 在循環(huán)吨掌。這表示的就是下鄰居的生成方式半抱。它生成了下鄰居一行脓恕。從下鄰居最左邊開始生成，一直往上生成到下鄰居最右邊窿侈。
上鄰居是 i + k炼幔，j + size，k 在循環(huán)史简。這表示的就是上鄰居的生成方式乃秀。它生成了上鄰居一行。從上鄰居最左邊開始生成乘瓤，一直往上生成到上鄰居最右邊环形。
舉例：
中間 Cell 的周圍的全鄰居是上圖的 8 的相同 Level 的 Cell。
生成順序用需要標(biāo)識出來了衙傀。1抬吟，2，5统抬，6火本，7，8 都是左右鄰居生成出來的聪建。3钙畔，4 是上下鄰居生成出來的。
上面這個例子是都是 Level - 10 的 Cell 生成出來的金麸。全鄰居正好是8個擎析。
AllNeighbors := cellID.Parent(10).AllNeighbors(10)
3958601400295882752,
3958605798342393856,
3958603599319138304,
3958612395412160512,
3958599201272627200,
3958607997365649408,
3958623390528438272,
3958614594435416064
再舉一個 Level 比調(diào)用者 Cell 的 Level 大的例子。
AllNeighbors := cellID.Parent(10).AllNeighbors(11)
3958600575662161920,
3958606622976114688,
3958603324441231360,
3958611570778439680,
3958600025906348032,
3958607172731928576,
3958603874197045248,
3958613220045881344,
3958599476150534144,
3958608821999370240,
3958623115650531328,
3958613769801695232
它的全鄰居生成順序如下：
1挥下，2揍魂，5，6棚瘟，9现斋，10，11偎蘸，12 都是左右鄰居庄蹋，3，4迷雪，7限书，8 是上下鄰居。我們可以看到左右鄰居是從下往上生成的章咧。上下鄰居是從左往右生成的蔗包。
如果 Level 更大，比如 Level - 15 慧邮，就會生成更多的鄰居：
現(xiàn)在在解釋一下如果入?yún)?Level 比調(diào)用者 Cell 的 Level 小的情況调限。
舉例，入?yún)?Level = 9 误澳。
AllNeighbors := cellID.Parent(10).AllNeighbors(9)
3958589305667977216,
3958580509574955008,
3958580509574955008,
3958615693947043840,
3958598101760999424,
3958606897854021632,
3958624490040066048,
3958615693947043840
生成的全鄰居如下：
可以看到本來有8個鄰居的耻矮，現(xiàn)在只有6個了。其實生成出來的還是8個忆谓，只不過有2個重復(fù)了裆装。重復(fù)的見圖中深紅色的兩個 Cell。
為何會重疊倡缠？
中間調(diào)用者的 Level - 10 的 Cell 先畫出來哨免。
因為是 Level - 9 的，所以它是中間那個 Cell 的四分之一昙沦。
我們把 Level - 10 的兩個上鄰居也畫出來琢唾。
可以看到上鄰居 Up 和頂點鄰居 up-right 都位于同一個 Level - 9 的 Cell 內(nèi)了。所以上鄰居和右上角的頂點鄰居就都是同一個 Level - 9 的 Cell 盾饮。所以重疊了采桃。同理，下鄰居和右下的頂點鄰居也重疊了丘损。所以就會出現(xiàn)2個 Cell 重疊的情況普办。
而且中間也沒有空出調(diào)用者 Cell 的位置。因為 i + size 以后徘钥，范圍還在同一個 Level - 9 的 Cell 內(nèi)衔蹲。
如果 Level 更小，重疊情況又會發(fā)生變化呈础。比如 Level - 5 舆驶。
AllNeighbors := cellID.Parent(10).AllNeighbors(5)
3953034572924452864,
3946279173483397120,
3946279173483397120,
3957538172551823360,
3955286372738138112,
3957538172551823360,
3962041772179193856,
3959789972365508608
畫在地圖上就是
重疊的位置也發(fā)生了變化。
至此猪落，查找鄰居相關(guān)的算法都介紹完了贞远。
空間搜索系列文章：
如何理解 n 維空間和 n 維時空
高效的多維空間點索引算法 — Geohash 和 Google S2
Google S2 中的 CellID 是如何生成的 ？
Google S2 中的四叉樹求 LCA 最近公共祖先
神奇的德布魯因序列
四叉樹上如何求希爾伯特曲線的鄰居 笨忌？
GitHub Repo：Halfrost-Field
Follow: halfrost · GitHub
