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

## 一. 寻找父亲节点和孩子节点

```// 3932700003016900608
11011010010011110000011101000100000000000000000000000000000000

// 3932700003016900600
11011010010011110000011101000011111111111111111111111111111000复制代码```

```由于前两位都是0，所以其实可以省略，但是为了读者看的更清晰，笔者还是补全了64位，前面2个0还是补上

// 3932700003016900608 右上
0011011010010011110000011101000100000000000000000000000000000000

// 3932700011606835200 左上
0011011010010011110000011101001100000000000000000000000000000000

// 3932700020196769792 左下
0011011010010011110000011101010100000000000000000000000000000000

// 3932700028786704384 右下
0011011010010011110000011101011100000000000000000000000000000000复制代码```

```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())

}复制代码```

```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复制代码```

### 1. 查找孩子节点

```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)/复制代码```

```11011010010011110000011101010000000000000000000000000000000000   13
11011010010011110000011101010100000000000000000000000000000000   14复制代码```

```11011010010011110000011101010100000000000000000000000000000000   14
11011010010011110000011101010001000000000000000000000000000000   15复制代码```

```11011010010011110000011101010001000000000000000000000000000000   15
11011010010011110000011101010000010000000000000000000000000000   16复制代码```

```11011010010011110000011101010000010000000000000000000000000000   16
11011010010011110000011101010000000100000000000000000000000000   17复制代码```

```11011010010011110000011101010000000000000000000000000000000000   13 3932700015901802496
11011010010011110000011101011100000000000000000000000000000000   14 3932700028786704384复制代码```

Level 14 对应的方向是图3，当前选择3号位置，就可以得到 Level 15，所以 Level 15 的末尾标志位1前面的两位是 11 。于是就可以从 Level 14 变换到 Level 15 。

```11011010010011110000011101011100000000000000000000000000000000   14 3932700028786704384
11011010010011110000011101011111000000000000000000000000000000   15 3932700032007929856复制代码```

Level 15 对应的方向是图0，当前选择0号位置，就可以得到 Level 16，所以 Level 16 的末尾标志位1前面的两位是 00 。于是就可以从 Level 15 变换到 Level 16 。

```11011010010011110000011101011111000000000000000000000000000000   15 3932700032007929856
11011010010011110000011101011110010000000000000000000000000000   16 3932700031202623488复制代码```

Level 16 对应的方向是图1，当前选择1号位置，就可以得到 Level 17，所以 Level 17 的末尾标志位1前面的两位是 01 。于是就可以从 Level 16 变换到 Level 17 。

```11011010010011110000011101011110010000000000000000000000000000   16 3932700031202623488
11011010010011110000011101011110001100000000000000000000000000   17 3932700031135514624复制代码```

```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
}复制代码```

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

`11011010010011110000011101011110010000000000000000000000000000   16 3932700031202623488复制代码`

`ch[0] = ci - lsb + lsb>>2复制代码`

0号孩子找到以后接下来就很好办了。lsb 往右移动一位以后，不断的加上这个值，就可以得到剩下的4个孩子了。如下图：

### 2. 判断是否是叶子节点

`func (ci CellID) IsLeaf() bool { return uint64(ci)&1 != 0 }复制代码`

### 3. 查找当前孩子位置关系

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

### 4. 查找父亲节点

`func lsbForLevel(level int) uint64 { return 1 << uint64(2*(maxLevel-level)) }复制代码`

`(uint64(ci) & -lsb)复制代码`

```func (ci CellID) Parent(level int) CellID {
lsb := lsbForLevel(level)
return CellID((uint64(ci) & -lsb) | lsb)
}复制代码```

## 二. LCA 查找最近公共祖先

`    bits := uint64(ci ^ other)复制代码`

```    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)
}复制代码```

```    msbPos := findMSBSetNonZero64(bits)
if msbPos > 60 {
return 0, false
}
return (60 - msbPos) >> 1, true复制代码```

```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
}复制代码```

```11011010010011110000011101010000000100000000000000000000000000   17
11011010010011110000011101011111000000000000000000000000000000   15复制代码```

`1101101001001111000001110101复制代码`

`11011010010011110000011101010000000000000000000000000000000000复制代码`

GitHub Repo：Halfrost-Field Follow: halfrost · GitHub Source: halfrost.com/go_s2_lowes…

61 篇文章18 人订阅

0 条评论

## 相关文章

### EntityFramework 元数据 设计分析

由于之前已经尝试使用过 EF CodeFirst CTP4，所以这次在EF4.1发布的第三天，在 OEA 框架中已经支持使用它来实现数据访问层。而且，我...

20180

49280

66970

13020

8310

407140

### 深入理解 Laravel Eloquent（三）——模型间关系（关联）

Eloquent 是一个 ORM，全称为 Object Relational Mapping，翻译为 “对象关系映射”（如果只把它当成 Database A...

14830

35510

57780

### Python中被忽略的else

else, 我们再熟悉不过了。对于一个python程序员来说，else往往都是配合if来使用的，像这样：

13920