Google S2 中的四叉樹求 LCA 最近公共祖先

一. 尋找父親節(jié)點(diǎn)和孩子節(jié)點(diǎn)

首先需要回顧一下希爾伯特曲線的生成方式，具體代碼見筆者上篇文章的分析，在這個(gè)分析中，有4個(gè)方向比較重要，接下來的分析需要，所以把這4個(gè)方向的圖搬過來。

在舉例之前還需要說明一點(diǎn)，有些網(wǎng)站提供的二進(jìn)制轉(zhuǎn)換，并沒有標(biāo)明有符號(hào)還是無符號(hào)的轉(zhuǎn)換，這樣就會(huì)導(dǎo)致使用者的一些誤解。筆者開始并沒有發(fā)現(xiàn)這個(gè)問題，導(dǎo)致掉入了這個(gè)坑，好一會(huì)才轉(zhuǎn)過彎來。筆者在網(wǎng)上查詢了很多在線轉(zhuǎn)換計(jì)算器的工具，都發(fā)現(xiàn)了這個(gè)問題。比如常見的在線進(jìn)制轉(zhuǎn)換http://tool.oschina.net/hexconvert，隨便找兩個(gè)64位的二進(jìn)制數(shù)，有符號(hào)的和無符號(hào)的分別轉(zhuǎn)換成十進(jìn)制，或者反過來轉(zhuǎn)換，你會(huì)驚喜的發(fā)現(xiàn)，兩次結(jié)果居然相同！例如你輸入 3932700003016900608 和 3932700003016900600，你會(huì)發(fā)現(xiàn)轉(zhuǎn)換成二進(jìn)制以后結(jié)果都是 11011010010011110000011101000100000000000000000000000000000000。但是很明顯這兩個(gè)數(shù)不同。

假如 3932700003016900608 是無符號(hào)的，3932700003016900600 是有符號(hào)的，正確的結(jié)果應(yīng)該如下：


// 3932700003016900608
11011010010011110000011101000100000000000000000000000000000000

// 3932700003016900600
11011010010011110000011101000011111111111111111111111111111000

差距明顯很大。這種例子其實(shí)還有很多，隨便再舉出幾組：無符號(hào)的 3932700011606835200 和有符號(hào)的 3932700011606835000；無符號(hào)的 3932700020196769792 和有符號(hào)的 3932700020196770000；無符號(hào)的 3932700028786704384 和有符號(hào)的 3932700028786704400……可以舉的例子很多，這里就不再舉了。

利用網(wǎng)上的這個(gè)工具，十進(jìn)制轉(zhuǎn)二進(jìn)制是無符號(hào)的轉(zhuǎn)換，二進(jìn)制轉(zhuǎn)十進(jìn)制就會(huì)變成有符號(hào)的轉(zhuǎn)換了。而 Google S2 默認(rèn)是無符號(hào)的 CellID，所以用有符號(hào)的 CellID 會(huì)出現(xiàn)錯(cuò)誤。所以轉(zhuǎn)換中需要注意一下。筆者之前沒有發(fā)現(xiàn)這一點(diǎn)的時(shí)候出現(xiàn)了一些問題，后來突然發(fā)現(xiàn)了這一點(diǎn)，茅塞頓開。

好了，進(jìn)入正題。接下來直接看一個(gè)例子，筆者用例子來說明每個(gè) Cell 之間的關(guān)系，以及如何查找父親節(jié)點(diǎn)的。

假設(shè)有上圖這4個(gè)連在一起的 Cell。先根據(jù)經(jīng)緯度把 CellID 計(jì)算出來。

對(duì)應(yīng)的4個(gè) CellID 分別是：


由于前兩位都是0，所以其實(shí)可以省略，但是為了讀者看的更清晰，筆者還是補(bǔ)全了64位，前面2個(gè)0還是補(bǔ)上

// 3932700003016900608 右上
0011011010010011110000011101000100000000000000000000000000000000      

// 3932700011606835200 左上
0011011010010011110000011101001100000000000000000000000000000000 

// 3932700020196769792 左下
0011011010010011110000011101010100000000000000000000000000000000

// 3932700028786704384 右下
0011011010010011110000011101011100000000000000000000000000000000

在前篇文章里面我們也分析了 Cell 64位的結(jié)構(gòu)，這里是4個(gè) Level 14的 Cell，所以末尾有 64 - 3 - 1 - 14 * 2 = 32 個(gè) 0 。從末尾往前的第33位是一個(gè)1，第34位，第35位是我們重點(diǎn)需要關(guān)注的?？梢钥吹椒謩e是00，01，10，11 。正好是連續(xù)的4個(gè)二進(jìn)制。

根據(jù)這個(gè)順序，我們可以匹配到當(dāng)前這4個(gè) Level 14 的 Cell 對(duì)應(yīng)的順序是上圖圖中的圖0 。只不過當(dāng)前方向旋轉(zhuǎn)了45°左右。

右上的 CellID 是 3932700003016900608 ，從右往左的第34位和第35位是00，從右上這個(gè) Cell 想找到希爾伯特曲線的下一個(gè) Cell，由于它目前方向是圖0的方向，所以右上的 Cell 的下一個(gè) Cell 是左上那個(gè) Cell，那么第34位和第35位就應(yīng)該是01，變換成01以后，就3932700011606835200，這也就是對(duì)應(yīng)的 CellID。右數(shù)第34位增加了一個(gè)1，對(duì)應(yīng)十進(jìn)制就增加了 233 = 8589934592，算一下兩個(gè) CellID 對(duì)應(yīng)十進(jìn)制的差值，也正好是這個(gè)數(shù)。目前一切都是正確的。

同理可得，左上的 Cell 的下一個(gè) Cell 就是左下的 Cell，也是相同的第34位和第35位上變成10，對(duì)應(yīng)十進(jìn)制增加 233 = 8589934592，得到左下的 CellID 為 3932700020196769792。繼續(xù)同理可以得到最后一個(gè) CellID，右下的 CellID，為 3932700028786704384。

看到這里，讀者應(yīng)該對(duì)查找同 Level 的兄弟節(jié)點(diǎn)的方法清清楚楚了?？赡苡腥擞幸蓡柫?，要查找父親節(jié)點(diǎn)和孩子節(jié)點(diǎn)和兄弟有啥關(guān)系？他們之間的聯(lián)系就在這一章節(jié)開頭說的4個(gè)方向圖上面。

回顧一下希爾伯特曲線的生成方式，在遞歸生成希爾伯特曲線的時(shí)候，保存了一個(gè) posToIJ 數(shù)組，這個(gè)數(shù)組里面記錄著4個(gè)方向。希爾伯特曲線生成的形式和這4個(gè)方向是密切相關(guān)的。如果忘記了這部分，還請(qǐng)回看之前筆者的文章分析。

所以同一級(jí)的 Level 想查找孩子節(jié)點(diǎn)，首先要找到在這一級(jí)中，當(dāng)前 Cell 所處的位置以及當(dāng)前 Cell 所在的4個(gè)方向中的哪一個(gè)方向。這個(gè)方向決定了要查找孩子位于下一級(jí)或者下幾級(jí)的哪個(gè)位置。因?yàn)橄柌厍€相當(dāng)于是一個(gè)顆四叉樹，每個(gè)根節(jié)點(diǎn)有4個(gè)孩子，雖然按層可以很輕松的遍歷到孩子所在的層級(jí)，但是同一個(gè)根節(jié)點(diǎn)的孩子有4個(gè)，究竟要選哪一個(gè)就需要父親節(jié)點(diǎn)的方向一級(jí)級(jí)的來判斷了。

舉個(gè)例子來說明這個(gè)問題：


func testS2() {

    latlng := s2.LatLngFromDegrees(29.323773, 107.727194)
    cellID := s2.CellIDFromLatLng(latlng)
    cell := s2.CellFromCellID(cellID) //9279882742634381312

    // cell.Level()
    fmt.Println("latlng = ", latlng)
    fmt.Println("cell level = ", cellID.Level())
    fmt.Printf("cell = %d %b\n", cellID, cellID)
    smallCell := s2.CellFromCellID(cellID.Parent(13))
    fmt.Printf("smallCell level = %d\n", smallCell.Level())
    fmt.Printf("smallCell id = %d / cellID = %d /smallCell(14).Parent = %d (level = %d)/smallCell(15).Parent = %d (level = %d)/cellID(13).Parent = %d (level = %d)/cellID(14).Parent = %d (level = %d)/cellID(15).Parent = %d (level = %d)/ %b \n", smallCell.ID(), cellID, smallCell.ID().Parent(14), (smallCell.ID().Parent(14).Level()), smallCell.ID().Parent(15), (smallCell.ID().Parent(15).Level()), cellID.Parent(13), (cellID.Parent(13)).Level(), cellID.Parent(14), (cellID.Parent(14)).Level(), cellID.Parent(15), (cellID.Parent(15)).Level(), smallCell.ID())

}

讀者考慮一下上述的程序會(huì)輸出什么呢？或者這樣問，同一個(gè)節(jié)點(diǎn)，先找它的 Level 13 的父親節(jié)點(diǎn)，再通過 Level 13 的這個(gè)節(jié)點(diǎn)再找它的 Level 15 的父親節(jié)點(diǎn)得到的 Level 15 的節(jié)點(diǎn)，和，直接找它的 Level 15 的父親節(jié)點(diǎn)，最終結(jié)果一樣么？

當(dāng)然，這里先找 Level 13，再找 Level 15，得到的結(jié)果不是 Level 28，這里不是相加的關(guān)系，結(jié)果還是 Level 15 的父親節(jié)點(diǎn)。所以上面兩種方式得到的結(jié)果都是 Level 15的。那么兩種做法得到的結(jié)果是一樣的么？讀者可以先猜一猜。

實(shí)際得到的結(jié)果如下：



latlng =  [29.3237730, 107.7271940]
cell level =  30
cell = 3932700032807325499 11011010010011110000011101011111101111101001011100111100111011
smallCell level = 13
smallCell id = 3932700015901802496 / cellID = 3932700032807325499 /smallCell(14).Parent = 3932700020196769792 (level = 14)/smallCell(15).Parent = 3932700016975544320 (level = 15)/cellID(13).Parent = 3932700015901802496 (level = 13)/cellID(14).Parent = 3932700028786704384 (level = 14)/cellID(15).Parent = 3932700032007929856 (level = 15)/ 11011010010011110000011101010000000000000000000000000000000000

可以看到，兩種做法得到的結(jié)果是不同的。但是究竟哪里不同呢？直接看 CellID 不夠直觀，那把它們倆畫出來看看。

可以看到兩者雖然 Level 是相同的，但是位置是不同的，為何會(huì)這樣呢？原因就是之前說的，四叉樹4個(gè)孩子，究竟選擇哪一個(gè)，是由于父親節(jié)點(diǎn)所在方向決定的。

1. 查找孩子節(jié)點(diǎn)

還是繼續(xù)按照上面程序舉的例子，看看如何查找孩子節(jié)點(diǎn)的。

我們把 Level 13 - Level 17 的節(jié)點(diǎn)都打印出來。


smallCell id = 3932700015901802496 (level = 13)/
smallCell(14).Parent = 3932700020196769792 (level = 14)/ 
smallCell(15).Parent = 3932700016975544320 (level = 15)/
smallCell(16).Parent = 3932700016170237952 (level = 16)/
smallCell(17).Parent = 3932700015968911360 (level = 17)/

畫在圖上，

從 Level 13 是如何變換到 Level 14 的呢？我們知道當(dāng)前選擇的是圖0的方向。那么當(dāng)前 Level 14是圖0 中的2號(hào)的位置。

所以從右往左數(shù) 64 - 3 - 1 - 13 * 2 = 34位和35位，應(yīng)該分別填上01，從前往后就是10，對(duì)應(yīng)的就是上圖中的2的位置，并且末尾的那個(gè)標(biāo)志位1往后再挪2位。


11011010010011110000011101010000000000000000000000000000000000   13
11011010010011110000011101010100000000000000000000000000000000   14

即可從 Level 13 變換到 Level 14 。這就是從父親節(jié)點(diǎn)到孩子節(jié)點(diǎn)的變換方法。

同理在看看 Level 15，Level 16，Level 17 的變換方法。

前面說過，查看孩子節(jié)點(diǎn)的時(shí)候需要知道當(dāng)前節(jié)點(diǎn)的其他3個(gè)兄弟節(jié)點(diǎn)的方向。

根據(jù)下圖，Level 14 對(duì)應(yīng)的是圖0，并且當(dāng)前選擇了2號(hào)位置，從下圖中可以看到圖0中的2號(hào)位置的下一級(jí)的圖是“U”形的，說明還是圖0的樣子。

所以可以知道當(dāng)前 Level 14 所處的方向依舊是圖0 。按照方向標(biāo)識(shí)在圖上，如下圖。

所以如果還是選擇上圖中0號(hào)的位置，那么 Level 15 的從右往左數(shù) 64 - 3 - 1 - 14 * 2 = 32位和第33位上填入00 。


11011010010011110000011101010100000000000000000000000000000000   14 
11011010010011110000011101010001000000000000000000000000000000   15

由于選擇了圖0的0號(hào)位置，所以下一級(jí)的方向?qū)?yīng)的是圖1 。(注意整個(gè)圖的方向是向左旋轉(zhuǎn)了90°) 。

圖1中繼續(xù)選擇0號(hào)的位置，所以 Level 16 的從右往左數(shù) 64 - 3 - 1 - 15 * 2 = 30位和31位填上00 。那么就可以得到 Level 16 。



11011010010011110000011101010001000000000000000000000000000000   15
11011010010011110000011101010000010000000000000000000000000000   16

由于選擇了圖1的0號(hào)位置，所以下一級(jí)的方向?qū)?yīng)的是還是圖0。

圖0中繼續(xù)選擇0號(hào)的位置，所以 Level 17 的從右往左數(shù) 64 - 3 - 1 - 16 * 2 = 28位和第29位填上00 。那么就可以得到 Level 17 。


11011010010011110000011101010000010000000000000000000000000000   16
11011010010011110000011101010000000100000000000000000000000000   17

同理，其他的孩子節(jié)點(diǎn)都可以按照這個(gè)方法推算得到。

從 Level 13 開始，由于 Level 13 對(duì)應(yīng)的方向是圖0，當(dāng)前選擇3號(hào)位置，就可以得到 Level 14，所以 Level 14 的末尾標(biāo)志位1前面的兩位是 11 。于是就可以從 Level 13 變換到 Level 14 。


11011010010011110000011101010000000000000000000000000000000000   13 3932700015901802496
11011010010011110000011101011100000000000000000000000000000000   14 3932700028786704384

由于圖0選擇了3號(hào)位置，那么 Level 14 的方向就是圖3 。

Level 14 對(duì)應(yīng)的方向是圖3，當(dāng)前選擇3號(hào)位置，就可以得到 Level 15，所以 Level 15 的末尾標(biāo)志位1前面的兩位是 11 。于是就可以從 Level 14 變換到 Level 15 。


11011010010011110000011101011100000000000000000000000000000000   14 3932700028786704384
11011010010011110000011101011111000000000000000000000000000000   15 3932700032007929856

由于圖3選擇了3號(hào)位置，那么 Level 15 的方向就是圖0。

Level 15 對(duì)應(yīng)的方向是圖0，當(dāng)前選擇0號(hào)位置，就可以得到 Level 16，所以 Level 16 的末尾標(biāo)志位1前面的兩位是 00 。于是就可以從 Level 15 變換到 Level 16 。


11011010010011110000011101011111000000000000000000000000000000   15 3932700032007929856
11011010010011110000011101011110010000000000000000000000000000   16 3932700031202623488

由于圖0選擇了0號(hào)位置，那么 Level 16 的方向就是圖1。

Level 16 對(duì)應(yīng)的方向是圖1，當(dāng)前選擇1號(hào)位置，就可以得到 Level 17，所以 Level 17 的末尾標(biāo)志位1前面的兩位是 01 。于是就可以從 Level 16 變換到 Level 17 。


11011010010011110000011101011110010000000000000000000000000000   16 3932700031202623488
11011010010011110000011101011110001100000000000000000000000000   17 3932700031135514624

由于圖1選擇了1號(hào)位置，那么 Level 18 的方向還是圖1。

到此讀者應(yīng)該對(duì)查找 CellID 孩子節(jié)點(diǎn)的流程了然于心了。在 Google S2 中，查找孩子節(jié)點(diǎn)的具體實(shí)現(xiàn)代碼如下。


func (ci CellID) Children() [4]CellID {
    var ch [4]CellID
    lsb := CellID(ci.lsb())
    ch[0] = ci - lsb + lsb>>2
    lsb >>= 1
    ch[1] = ch[0] + lsb
    ch[2] = ch[1] + lsb
    ch[3] = ch[2] + lsb
    return ch
}

現(xiàn)在在來看這段代碼應(yīng)該毫無壓力了吧。

這里比較重要的位運(yùn)算的操作就是 lsb 了。從名字上其實(shí)也可以知道它是做什么的。


// lsb 返回最低有效位
func (ci CellID) lsb() uint64 { return uint64(ci) & -uint64(ci) }

這里需要注意的一點(diǎn)就是負(fù)數(shù)的存儲(chǔ)方式是以原碼的補(bǔ)碼，即符號(hào)位不變，每位取反再加1 。

舉個(gè)例子，Level 16 的某個(gè) CellID 如下：


11011010010011110000011101011110010000000000000000000000000000   16 3932700031202623488

對(duì)它進(jìn)行 lsb 計(jì)算：

得到的結(jié)果就是最低有效位為1，其他每位都為0 。


ch[0] = ci - lsb + lsb>>2

這一行實(shí)際是把 Level 對(duì)應(yīng)的下一級(jí) Level 的末尾標(biāo)志位1移動(dòng)到位。即往后挪2位。并且標(biāo)志位前面2位都為0，所以這步操作完成以后就是0號(hào)的孩子。

0號(hào)孩子找到以后接下來就很好辦了。lsb 往右移動(dòng)一位以后，不斷的加上這個(gè)值，就可以得到剩下的4個(gè)孩子了。如下圖：

這樣就可以得到4個(gè)孩子，上面這一小段程序挺簡(jiǎn)單的，比前面從地圖上解釋的更簡(jiǎn)單，原因是因?yàn)闆]有可視化的4個(gè)孩子的相互位置關(guān)系，這個(gè)關(guān)系需要從當(dāng)前所在的方向來決定。前面地圖上也一再強(qiáng)調(diào)每一級(jí)的方向位置關(guān)系也是為了可視化展現(xiàn)在地圖上是符合希爾伯特曲線的相對(duì)位置。

2. 判斷是否是葉子節(jié)點(diǎn)

如果對(duì) CellID 的數(shù)據(jù)結(jié)構(gòu)很了解，這個(gè)判斷就很簡(jiǎn)單了。


func (ci CellID) IsLeaf() bool { return uint64(ci)&1 != 0 }

由于 CellID 是64位的，末尾有一個(gè)1的標(biāo)志位，如果這個(gè)標(biāo)志位到了最后一位，那么就肯定是葉子節(jié)點(diǎn)了，也就是 Level 30 的 Cell。

3. 查找當(dāng)前孩子位置關(guān)系

在前面講解查找孩子節(jié)點(diǎn)的時(shí)候，由于是四叉樹，每個(gè)父親下面對(duì)應(yīng)4個(gè)孩子，00，01，10，11，所以判斷4個(gè)孩子之間相對(duì)的位置關(guān)系只需要判斷這兩個(gè)二進(jìn)制位就可以了。


func (ci CellID) ChildPosition(level int) int {
    return int(uint64(ci)>>uint64(2*(maxLevel-level)+1)) & 3
}

上面這個(gè)函數(shù)入?yún)⑹且粋€(gè)父親節(jié)點(diǎn)的 Level 等級(jí)，返回的是這個(gè)父親節(jié)點(diǎn)下面孩子節(jié)點(diǎn)的位置信息。即是 00，01，10，11 中的一個(gè)。

4. 查找父親節(jié)點(diǎn)

在 Google S2 中，由于默認(rèn)生成出來的 Cell 就是 Level 30 的，也就是 Level 最低的，位于樹的最下層的葉子節(jié)點(diǎn)。所以生成 Level 比較低的 Cell 必須只能查找父親節(jié)點(diǎn)。

由于前面講解了如何查找孩子節(jié)點(diǎn)，查找父親節(jié)點(diǎn)就是逆向的過程。


func lsbForLevel(level int) uint64 { return 1 << uint64(2*(maxLevel-level)) }

第一步就是先找到最右邊的標(biāo)志位，它決定了 Level 的值。


(uint64(ci) & -lsb)

第二步是保留住標(biāo)志位前面所有的二進(jìn)制位上的值。這里對(duì)第一步的 lsb 的相反數(shù)進(jìn)行按位與操作就可以實(shí)現(xiàn)。lsb 的相反數(shù)其實(shí)就是 lsb 低位往左的高位都為1 ，相當(dāng)于一個(gè)掩碼。

最后一步將標(biāo)志位1放好就可以了。


func (ci CellID) Parent(level int) CellID {
    lsb := lsbForLevel(level)
    return CellID((uint64(ci) & -lsb) | lsb)
}

以上就是查找父親節(jié)點(diǎn)的具體實(shí)現(xiàn)。

二. LCA 查找最近公共祖先

關(guān)于 CellID 的計(jì)算，還有很關(guān)鍵的一部分就是查找最近公共祖先的問題。問題背景：給定一棵四叉樹中任意兩個(gè) Level 的 CellID ，如何查詢兩者的最近公共祖先。

由 CellID 的數(shù)據(jù)結(jié)構(gòu)我們知道，想查找兩個(gè) Level 的最近公共祖先的問題可以轉(zhuǎn)化為從左往右查找兩個(gè)二進(jìn)制串最長(zhǎng)公共序列，最長(zhǎng)的即是從根節(jié)點(diǎn)開始最遠(yuǎn)的公共祖先，也就是最近公共祖先。

那么現(xiàn)在問題就轉(zhuǎn)換成從左往右找到第一個(gè)不相同的二進(jìn)制位，或者從右往左找到最后一個(gè)不相同的二進(jìn)制位。

查找過程中存在一個(gè)特殊情況，那就是要查找公共祖先的兩個(gè)節(jié)點(diǎn)本身就在一個(gè)分支上，即其中一個(gè) CellID 本來就是另外一個(gè) CellID 的祖先，那么他們倆的公共祖先就直接是 CellID 大的那個(gè)。

那么到此就可以確定出接下來查找的流程。

第一步，先對(duì)兩個(gè) CellID 進(jìn)行異或，找到不同的二進(jìn)制位分別在那些位置上。


    bits := uint64(ci ^ other)

第二步，判斷是否存在特殊情況：兩個(gè)存在祖先關(guān)系。


    if bits < ci.lsb() {
        bits = ci.lsb()
    }
    if bits < other.lsb() {
        bits = other.lsb()
    }

第三步，查找左邊最高位不同的位置。



func findMSBSetNonZero64(bits uint64) int {
    val := []uint64{0x2, 0xC, 0xF0, 0xFF00, 0xFFFF0000, 0xFFFFFFFF00000000}
    shift := []uint64{1, 2, 4, 8, 16, 32}
    var msbPos uint64
    for i := 5; i >= 0; i-- {
        if bits&val[i] != 0 {
            bits >>= shift[i]
            msbPos |= shift[i]
        }
    }
    return int(msbPos)
}

由于 CellID 是 64 位的，所以兩者不同的位數(shù)可能的范圍是 [0，63]。分別準(zhǔn)備6種掩碼，對(duì)應(yīng)的分別是0x2, 0xC, 0xF0, 0xFF00, 0xFFFF0000, 0xFFFFFFFF00000000。如下圖。

查找的過程就是利用的二分的思想。64位先查找高位32位，如果對(duì)高32位的掩碼進(jìn)行按位與運(yùn)算以后結(jié)果不為0，那么就說明高32位是存在不相同的位數(shù)的，那么最終結(jié)果 msbPos 加上32位，并把數(shù)字右移32位。因?yàn)楦?2位存在不同的數(shù)，由于我們需要求最左邊的，所以低32位就可以直接舍去了，直接右移去掉。

同理，繼續(xù)二分，16位，8位，4位，2位，1位，這樣循環(huán)完，就一定能把最左邊的不同的位數(shù)找到，并且結(jié)果位即為 msbPos。

第四步，判斷 msbPos 的合法性，并輸出最終結(jié)果。

如果 msbPos 比60還要大，那么就是非法值，直接返回 false 即可。


    msbPos := findMSBSetNonZero64(bits)
    if msbPos > 60 {
        return 0, false
    }
    return (60 - msbPos) >> 1, true

最終輸出的為最近公共祖先的 Level 值，所以 60 - msbPos 以后還需要再除以2 。

完整的算法實(shí)現(xiàn)如下：


func (ci CellID) CommonAncestorLevel(other CellID) (level int, ok bool) {
    bits := uint64(ci ^ other)
    if bits < ci.lsb() {
        bits = ci.lsb()
    }
    if bits < other.lsb() {
        bits = other.lsb()
    }

    msbPos := findMSBSetNonZero64(bits)
    if msbPos > 60 {
        return 0, false
    }
    return (60 - msbPos) >> 1, true
}

舉個(gè)例子：

在上面的例子中，我們挑選不存在祖先關(guān)系的兩個(gè) Level 的 CellID。


11011010010011110000011101010000000100000000000000000000000000   17
11011010010011110000011101011111000000000000000000000000000000   15

如果從這串二進(jìn)制里面直接找最近公共祖先，一定可以發(fā)現(xiàn)，從左往右最長(zhǎng)的公共二進(jìn)制串是：


1101101001001111000001110101

那么他們倆的最近公共祖先就是：


11011010010011110000011101010000000000000000000000000000000000

對(duì)應(yīng)的 Level 是13，CellID 是 3932700015901802496。

空間搜索系列文章：

空間搜索系列文章：

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

GitHub Repo：Halfrost-Field

Follow: halfrost · GitHub

Source: https://halfrost.com/go_s2_lowest_common_ancestor/

最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡(jiǎn)書系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容