四叉树

2025-05-08

Algorithm

无标签

文章目录

四叉树 ：

四叉树索引的基本思想是将地理空间递归划分为不同层次的树结构。

它将已知范围的空间等分成四个相等的子空间，如此递归下去，直至树的层次达到一定深度或者满足某种要求后停止分割。

Splite#

为了灵活性，设计一个 ssf 分裂终止函数。当满足这个函数时，分裂终止；同时，这个是触发合并的对偶条件，只有当满足这个条件时，才会尝试合并。
对于一个 ssf 函数，可以这样设计：叶子结点<=4 || 节点面积<=最小的元素面积，也就是说只有叶子节点>4且节点面积>4才能触发分裂。

分裂需要满足下面的条件：

该节点是叶子节点。
!ssf

执行分裂时：

element 可以以中心坐标为准，放入四分的新的叶子节点。
对所有新的叶子节点再次尝试分裂。

Merge#

合并需要满足下面的条件：

不是根节点。
自身是叶子节点，且其兄弟节点均为叶子节点。
ssf 且父节点满足 ssf

执行分裂时：

自身及其兄弟节点的所有 element 上挪到父节点。
对父节点再次尝试合并。

When to Splite or Merge#

并非只有添加对象才会引起分裂，同样并非只有移除对象才会引起合并。

分裂和合并的触发，取决于终止分裂条件 ssf() 的设计。

举一个例子，我们希望叶子节点在下面的任一情况成立时终止分裂：

节点内没有任何管理的对象。
节点内每一个方格都是对象。

这种条件十分适合地图中的固定障碍物的管理（地形、建筑等），四叉树可以把完全空旷的、和完全都是障碍物的地方不重叠地放到不同的叶子中去。

这样可能发生：

当添加一个对象时，有可能一个大的矩形正好放满了，引起合并。
当移除一个对象时，有可能一个满的大矩形变的不满了，引起分裂。

这种情况下， 不论是添加还是移除对象，分裂和合并都有可能发生。

但是，用户的条件是稳定的，也就是说保证 分裂和合并的条件不会同时成立，一定是时刻相反的。

所以在实现中，每次添加或移除对象时，都回去尝试分裂或合并，但 二者只发生一个。

1
// 添加对象时, 先尝试分裂，否则尝试合并
2
trySplitDown(node) || tryMergeUp(node);
3
// 移除对象时，先尝试合并，否则尝试分裂
4
tryMergeUp(node) || trySplitDown(node);

Query Optimize#

对于一个宽 $w$ ，高 $h$ 的带划分平面。可以将其进行 $d$ 次二分，这样对于点 $(x,y)$ ，一定在第 $(2^dx/w,2^dy/h)$ 个小区间内。

也就是说，对于 $d$ 的节点而言，其覆盖区域内的任意一个位置 $(x,y)$ 都有：

位置 $(x,y)$ 一定位于 $x$ 轴上第 $2^dx/w$ 个、 $y$ 轴上第 $2^dy/h$ 个小矩形内。

其中 $d$ 从 $0$ 开始计算的，计数也是从 $0$ 开始的。

构造哈希函数：

可以构造一个参数为 $(d,x,y)$ 的哈希函数，这个函数输出为对于特定深度 $d$ 的某一区域内的 $(x,y)$ ，具有相同的ID。

这样，每个特定深度 $d$ 的区域可以对应四叉树的某一可能的叶子节点，都具有了唯一的ID。

接下来只需要建立从 $(d,x,y)$ 到该叶子结点指针的映射即可。

1
uint64_t pack(
2
    uint64_t d, uint64_t x, uint64_t y, uint64_t w, uint64_t h) {
3
  // 0xfc00000000000000 : 高6位全是 1, 其余是0
4
  // 0x3ffffffe0000000  : 高6位全是 0, 接下来29位全是1，其余全是0
5
  // 0x1fffffff         : 低29位全是 1，其余全是0
6
  return ((d << 58) & 0xfc00000000000000ULL) |
7
         ((((1 << d) * x / h) << 29) & 0x3ffffffe0000000ULL) |
8
         (((1 << d) * y / w) & 0x1fffffffULL);
9
}

查找位置为 $(x,y)$ 的叶子节点，关键就在于 确定深度 $d$ 。因为深度十分有限，遍历的开销十分低。但也可以通过二分进一步优化。

提前维护整棵树的高度 $maxd$ ，这样初始可行域为 $[0,maxd]$ ，设定 $l=0,r=maxd$ 。
二分猜 $m=(l+r)>>1$ ，用 pack 函数查找计算出的ID，如果查找不到任何节点，说明太大了，需要收缩上界 $r=m-1$ 。
如果哈希表中存在，那就看是不是叶子节点。如果是叶子节点，则已经命中。如果不是，说明是一个中间的非叶子节点，需要收缩下界 $l=m+1$ 。

$maxd$ 的维护：
由于支持动态合并，维护 $maxd$ 时，需要同时维护 $maxd$ 的数量，只有当最后一个 $maxd$ 被销毁时，才减少 $maxd$ 。

Region Query#

思路很简单，从根节点开始，不断 判断重叠：

如果是叶子节点，则直接收集位于查询区域范围内的对象就可以了。
若果是非叶子节点，则继续判断子节点，递归下去。

Region Query Optimize#

区域查询时，有了 Query Optimize 机制，就可以不从根节点开始查询。

这时候其实是要找到包含所有区域的最小公共节点。也就是 同时包含查询区域左上角和右下角两个点的最小的节点 。

假设查询区域左上角是 $a$ 点，右上角是 $b$ 点，同时包含这两个点的最小节点是 $Q$ ，那么：

对于 $Q$ ，及其祖先节点，一定同时包含 $a$ 和 $b$ 。
对于 $Q$ 的所有子孙节点，必然不会同时包含 $a$ 和 $b$ 。

1
Node* find_smallest_node_covering_range(int x1, int y1, int x2, int y2)
2
{
3
    int l = 0, r = maxd;
4
    Node* node = root;
5
    while (l < r)
6
    {
7
        int d = (l + r + 1) >> 1;
8
        auto id1 = pack(d, x1, y1, w, h);
9
        auto id2 = pack(d, x2, y2, w, h);
10
        if (id1 == id2)
11
        {
12
            node = id2NodeDict.find(id1);
13
            id1 = pack(d + 1, x1, y1, w, h);
14
            id2 = pack(d + 1，x2, y2, w, h);
15
            if (id1 == id2)
16
            {
17
                l = d;
18
                continue;
19
            }
20
        }
21
        // 猜得太细分了，缩小上界
22
        r = d - 1;
23
    }
24
    return node;
25
}