四叉树上如何求希尔伯特曲线的邻居 ？

关于邻居的定义，相邻即为邻居，那么邻居分为2种，边相邻和点相邻。边相邻的有4个方向，上下左右。点相邻的也有4...

作者|一缕殇流化隐半边冰霜

关于邻居的定义，相邻即为邻居，那么邻居分为2种，边相邻和点相邻。边相邻的有4个方向，上下左右。点相邻的也有4个方向，即4个顶点相邻的。如上图，绿色的区域是一颗四叉树表示的范围，四叉树上面有一个点，图中黄色区域标明的点。现在想求四叉树上黄色的点的希尔伯特曲线邻居。图中黑色的线就是一颗穿过四叉树的希尔伯特曲线。希尔伯特曲线的起点0在左上角的方格中，终点63在右上角的方格中。

红色的四个格子是黄色格子边相邻邻居，蓝色的四个格子是黄色格子的顶点相邻的邻居，所以黄色格子的邻居为8个格子，分别表示的点是8，9，54，11，53，30，31，32 。可以看出来这些邻居在表示的点上面并不是相邻的。

那么怎么求四叉树上任意一点的希尔伯特曲线邻居呢？

边邻居最直接的想法就是 先拿到中心点的坐标 (i，j) ，然后通过坐标系的关系，拿到与它边相邻的 Cell 的坐标 (i + 1，j) ， (i - 1，j) ， (i，j - 1) ， (i，j + 1) 。

实际做法也是如此。不过这里涉及到需要转换的地方。这里需要把希尔伯特曲线上的点转换成坐标以后才能按照上面的思路来计算边邻居。

关于 CellID 的生成与数据结构，见笔者这篇《Google S2 中的 CellID 是如何生成的 ？》

按照上述的思路，实现出来的代码如下：

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 。

接下来具体分析一下里面的实现。

func sizeIJ(level int) int {

return 1 = 0; k-- {

orientation += (int(uint64(ci)>>uint64(k*2*lookupBits+1)) & ((1

(lookupBits + 2)) > 2) & ((1 = 0).Parent(level))

neighbors = append(neighbors, cellIDFromFaceIJSame(face, i+size, j+k,

sameFace && i+size < maxSize).Parent(level))

// 这里的判断条件有2个用途，一是防止32-bit溢出，二是循环的退出条件，大于size以后也就不用再找了

if k >= size {

break

}

}

return neighbors

}

上述代码简单的思路用注释写了。需要讲解的部分现在来讲解。

首先需要理解的是 nbrSize 和 size 的关系。为何会有 nbrSize ？ 因为入参 Level 是可以和调用者 Cell 的 Level 不一样的。入参的 Level 代表的 Cell 可大可小也可能相等。最终结果是以 nbrSize 格子大小来表示的，所以循环中需要用 nbrSize 来控制格子的大小。而 size 只是原来调用者 Cell 的格子大小。

循环中 K 的变化，当 K = -nbrSize 的时候，这个时候循环只会计算左边和右边的邻居。对角线上的顶点邻居其实也是左边邻居和右边邻居的一种特殊情况。接下来 K = 0，就会开始计算上边邻居和下边邻居了。K 不断增加，直到最后 K >= size ，最后一次循环内，会先计算一次左边和右边邻居，再 break 退出。

调用者的 Cell 在中间位置，所以想要跳过这个 Cell 到达另外一边(上下，或者左右)，那么就需要跳过 size 的大小。具体代码实现是 i + size 和 j + size 。

先看左右邻居的循环扫描方式。

左邻居是 i - nbrSize，j + k，k 在循环。这表示的就是左邻居的生成方式。它生成了左邻居一列。从左下角开始生成，一直往上生成到左上角。

右邻居是 i + size，j + k，k 在循环。这表示的就是右邻居的生成方式。它生成了右邻居一列。从右下角开始生成，一直往上生成到右上角。

再看上下邻居的循环扫描方式。

下邻居是 i + k，j - nbrSize，k 在循环。这表示的就是下邻居的生成方式。它生成了下邻居一行。从下邻居最左边开始生成，一直往上生成到下邻居最右边。

上邻居是 i + k，j + size，k 在循环。这表示的就是上邻居的生成方式。它生成了上邻居一行。从上邻居最左边开始生成，一直往上生成到上邻居最右边。

举例：中间 Cell 的周围的全邻居是上图的 8 的相同 Level 的 Cell。

生成顺序用需要标识出来了。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 比调用者 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 ，就会生成更多的邻居：现在再解释一下如果入参 Level 比调用者 Cell 的 Level 小的情况。

举例，入参 Level = 9 。

AllNeighbors := cellID.Parent(10).AllNeighbors(9)

3958589305667977216,

3958580509574955008,

3958580509574955008,

3958615693947043840,

3958598101760999424,

3958606897854021632,

3958624490040066048,

3958615693947043840

生成的全邻居如下：可以看到本来有8个邻居的，现在只有6个了。其实生成出来的还是8个，只不过有2个重复了。重复的见图中深红色的两个 Cell。

为何会重叠？

中间调用者的 Level - 10 的 Cell 先画出来。因为是 Level - 9 的，所以它是中间那个 Cell 的四分之一。

我们把 Level - 10 的两个上邻居也画出来。

可以看到上邻居 Up 和顶点邻居 up-right 都位于同一个 Level - 9 的 Cell 内了。所以上邻居和右上角的顶点邻居就都是同一个 Level - 9 的 Cell 。所以重叠了。同理，下邻居和右下的顶点邻居也重叠了。所以就会出现2个 Cell 重叠的情况。

而且中间也没有空出调用者 Cell 的位置。因为 i + size 以后，范围还在同一个 Level - 9 的 Cell 内。

如果 Level 更小，重叠情况又会发生变化。比如 Level - 5 。

AllNeighbors := cellID.Parent(10).AllNeighbors(5)

3953034572924452864,

3946279173483397120,

3946279173483397120,

3957538172551823360,

3955286372738138112,

3957538172551823360,

3962041772179193856,

3959789972365508608

画在地图上就是重叠的位置也发生了变化。

至此，查找邻居相关的算法都介绍完了。

空间搜索系列文章：

• 如何理解 n 维空间和 n 维时空
• 高效的多维空间点索引算法 — Geohash 和 Google S2
• Google S2 中的 CellID 是如何生成的 ？
• Google S2 中的四叉树求 LCA 最近公共祖先
• 神奇的德布鲁因序列
• 四叉树上如何求希尔伯特曲线的邻居 ？

GitHub Repo：Halfrost-Field

Follow: halfrost · GitHub

Source: https://halfrost.com/go_s2_Hilbert_neighbor/

    关注 Cocoa开发者社区