跳转至

四叉树与八叉树

概述

四叉树（Quadtree）和八叉树（Octree）是用于空间划分的树形数据结构。四叉树将2D空间递归划分为四个象限，八叉树将3D空间递归划分为八个卦限，广泛应用于图像处理、游戏开发、空间索引等领域。

核心思想：当节点包含的对象超过阈值时，将空间均匀分割成 2^d 个子区域（d为维度），每个子区域对应一个子节点，直到满足停止条件。

四叉树

四叉树结构可视化

空间划分过程：

原始空间

A B C D E F

第一次分裂（超过容量4）

继续分裂（左上象限超过容量）

四叉树节点结构

graph TB
    subgraph 四叉树节点结构
        root["根节点<br/>整个空间"]
        nw["NW<br/>左上"]
        ne["NE<br/>右上"]
        sw["SW<br/>左下"]
        se["SE<br/>右下"]
        
        root --> nw
        root --> ne
        root --> sw
        root --> se
    end
    
    style root fill:#4CAF50,color:#fff
    style nw fill:#2196F3,color:#fff
    style ne fill:#FF9800,color:#fff
    style sw fill:#9C27B0,color:#fff
    style se fill:#E91E63,color:#fff

象限编号：

0 (NW) 1 (NE) 2 (SW) 3 (SE)

数据结构定义

C
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
#define MAX_POINTS 4    // 节点最大点数

typedef struct {
    double x, y;
} Point2D;

typedef struct {
    double x_min, y_min;
    double x_max, y_max;
} Bounds2D;

typedef struct QuadTreeNode {
    Bounds2D bounds;                 // 节点边界
    Point2D points[MAX_POINTS];      // 存储的点
    int pointCount;                  // 点数量
    int isLeaf;                      // 是否为叶子节点
    struct QuadTreeNode *children[4]; // 四个子节点
} QuadTreeNode;

typedef struct {
    QuadTreeNode *root;
} QuadTree;

创建四叉树

C
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
QuadTreeNode* createQuadNode(Bounds2D bounds) {
    QuadTreeNode *node = (QuadTreeNode*)malloc(sizeof(QuadTreeNode));
    node->bounds = bounds;
    node->pointCount = 0;
    node->isLeaf = 1;
    
    for (int i = 0; i < 4; i++) {
        node->children[i] = NULL;
    }
    
    return node;
}

QuadTree* createQuadTree(double x_min, double y_min, double x_max, double y_max) {
    QuadTree *tree = (QuadTree*)malloc(sizeof(QuadTree));
    Bounds2D bounds = {x_min, y_min, x_max, y_max};
    tree->root = createQuadNode(bounds);
    return tree;
}

分裂节点

C
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
void subdivide(QuadTreeNode *node) {
    double x_mid = (node->bounds.x_min + node->bounds.x_max) / 2;
    double y_mid = (node->bounds.y_min + node->bounds.y_max) / 2;
    
    // 创建四个子节点的边界
    Bounds2D bounds[4] = {
        {node->bounds.x_min, node->bounds.y_min, x_mid, y_mid},      // SW (左下)
        {x_mid, node->bounds.y_min, node->bounds.x_max, y_mid},      // SE (右下)
        {node->bounds.x_min, y_mid, x_mid, node->bounds.y_max},      // NW (左上)
        {x_mid, y_mid, node->bounds.x_max, node->bounds.y_max}       // NE (右上)
    };
    
    // 创建四个子节点
    for (int i = 0; i < 4; i++) {
        node->children[i] = createQuadNode(bounds[i]);
    }
    
    node->isLeaf = 0;
    
    // 将现有点重新分配到子节点
    for (int i = 0; i < node->pointCount; i++) {
        Point2D p = node->points[i];
        int quadrant = 0;
        if (p.x >= x_mid) quadrant += 1;
        if (p.y >= y_mid) quadrant += 2;
        
        node->children[quadrant]->points[node->children[quadrant]->pointCount++] = p;
    }
    
    node->pointCount = 0;
}

分裂过程可视化：

flowchart TD
    A["节点点数 > MAX"]
    B["计算中心点"]
    C["创建4个子节点"]
    D["重新分配点到子节点"]
    E["标记为非叶子节点"]
    
    A --> B --> C --> D --> E
    
    style A fill:#FFEBEE
    style E fill:#E8F5E9

插入操作

C
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
int inBounds(Bounds2D bounds, Point2D p) {
    return p.x >= bounds.x_min && p.x <= bounds.x_max &&
           p.y >= bounds.y_min && p.y <= bounds.y_max;
}

void insertQuad(QuadTreeNode *node, Point2D point) {
    // 检查点是否在边界内
    if (!inBounds(node->bounds, point)) return;
    
    if (node->isLeaf) {
        // 如果未满，直接添加
        if (node->pointCount < MAX_POINTS) {
            node->points[node->pointCount++] = point;
            return;
        }
        
        // 已满，分裂节点
        subdivide(node);
    }
    
    // 确定所属象限
    double x_mid = (node->bounds.x_min + node->bounds.x_max) / 2;
    double y_mid = (node->bounds.y_min + node->bounds.y_max) / 2;
    
    int quadrant = 0;
    if (point.x >= x_mid) quadrant += 1;
    if (point.y >= y_mid) quadrant += 2;
    
    // 递归插入到子节点
    insertQuad(node->children[quadrant], point);
}

范围查询

C
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void rangeQueryQuad(QuadTreeNode *node, Bounds2D query, 
                    Point2D results[], int *count) {
    // 边界不相交，直接返回
    if (node->bounds.x_max < query.x_min || node->bounds.x_min > query.x_max ||
        node->bounds.y_max < query.y_min || node->bounds.y_min > query.y_max) {
        return;
    }
    
    if (node->isLeaf) {
        // 叶子节点：检查每个点
        for (int i = 0; i < node->pointCount; i++) {
            Point2D p = node->points[i];
            if (p.x >= query.x_min && p.x <= query.x_max &&
                p.y >= query.y_min && p.y <= query.y_max) {
                results[(*count)++] = p;
            }
        }
    } else {
        // 非叶子节点：递归查询子节点
        for (int i = 0; i < 4; i++) {
            rangeQueryQuad(node->children[i], query, results, count);
        }
    }
}

范围查询示意：

查询区域（虚线框）

A B C E D F
结果: A, B, C （查询区域内的点）

八叉树

八叉树结构可视化

3D空间划分：

3D空间分裂与卦限编号

0 1 2 3 4 5 6 7
0: 左下后 (x<mid, y<mid, z<mid)
1: 左下前 (x<mid, y<mid, z>mid)
2: 右下后 (x>mid, y<mid, z<mid)
3: 右下前 (x>mid, y<mid, z>mid)
4: 左上后 (x<mid, y>mid, z<mid)
5: 左上前 (x<mid, y>mid, z>mid)
6: 右上后 (x>mid, y>mid, z<mid)
7: 右上前 (x>mid, y>mid, z>mid)

数据结构定义

C
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
typedef struct {
    double x, y, z;
} Point3D;

typedef struct {
    double x_min, y_min, z_min;
    double x_max, y_max, z_max;
} Bounds3D;

typedef struct OctTreeNode {
    Bounds3D bounds;                 // 节点边界
    Point3D points[MAX_POINTS];      // 存储的点
    int pointCount;                  // 点数量
    int isLeaf;                      // 是否为叶子节点
    struct OctTreeNode *children[8]; // 八个子节点
} OctTreeNode;

typedef struct {
    OctTreeNode *root;
} OctTree;

创建八叉树节点

C
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
OctTreeNode* createOctNode(Bounds3D bounds) {
    OctTreeNode *node = (OctTreeNode*)malloc(sizeof(OctTreeNode));
    node->bounds = bounds;
    node->pointCount = 0;
    node->isLeaf = 1;
    
    for (int i = 0; i < 8; i++) {
        node->children[i] = NULL;
    }
    
    return node;
}

OctTree* createOctTree(double x_min, double y_min, double z_min,
                       double x_max, double y_max, double z_max) {
    OctTree *tree = (OctTree*)malloc(sizeof(OctTree));
    Bounds3D bounds = {x_min, y_min, z_min, x_max, y_max, z_max};
    tree->root = createOctNode(bounds);
    return tree;
}

分裂八叉树节点

C
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
void subdivideOct(OctTreeNode *node) {
    double x_mid = (node->bounds.x_min + node->bounds.x_max) / 2;
    double y_mid = (node->bounds.y_min + node->bounds.y_max) / 2;
    double z_mid = (node->bounds.z_min + node->bounds.z_max) / 2;
    
    // 创建八个子节点
    for (int i = 0; i < 8; i++) {
        Bounds3D b;
        b.x_min = (i & 1) ? x_mid : node->bounds.x_min;
        b.x_max = (i & 1) ? node->bounds.x_max : x_mid;
        b.y_min = (i & 2) ? y_mid : node->bounds.y_min;
        b.y_max = (i & 2) ? node->bounds.y_max : y_mid;
        b.z_min = (i & 4) ? z_mid : node->bounds.z_min;
        b.z_max = (i & 4) ? node->bounds.z_max : z_mid;
        
        node->children[i] = createOctNode(b);
    }
    
    node->isLeaf = 0;
    
    // 重新分配点到子节点
    for (int i = 0; i < node->pointCount; i++) {
        Point3D p = node->points[i];
        int octant = 0;
        if (p.x >= x_mid) octant |= 1;
        if (p.y >= y_mid) octant |= 2;
        if (p.z >= z_mid) octant |= 4;
        
        node->children[octant]->points[node->children[octant]->pointCount++] = p;
    }
    
    node->pointCount = 0;
}

八叉树插入

C
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
void insertOct(OctTreeNode *node, Point3D point) {
    if (!inBounds3D(node->bounds, point)) return;
    
    if (node->isLeaf) {
        if (node->pointCount < MAX_POINTS) {
            node->points[node->pointCount++] = point;
            return;
        }
        subdivideOct(node);
    }
    
    double x_mid = (node->bounds.x_min + node->bounds.x_max) / 2;
    double y_mid = (node->bounds.y_min + node->bounds.y_max) / 2;
    double z_mid = (node->bounds.z_min + node->bounds.z_max) / 2;
    
    int octant = 0;
    if (point.x >= x_mid) octant |= 1;
    if (point.y >= y_mid) octant |= 2;
    if (point.z >= z_mid) octant |= 4;
    
    insertOct(node->children[octant], point);
}

C++ 实现

C++
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
#include <vector>
#include <memory>
#include <array>

class QuadTree {
private:
    static const int MAX_POINTS = 4;
    
    struct Point { double x, y; };
    struct Bounds { double x_min, y_min, x_max, y_max; };
    
    struct Node {
        Bounds bounds;
        std::vector<Point> points;
        std::array<std::unique_ptr<Node>, 4> children;
        bool isLeaf;
        
        Node(Bounds b) : bounds(b), isLeaf(true) {}
    };
    
    std::unique_ptr<Node> root;
    
    void subdivide(Node* node) {
        double x_mid = (node->bounds.x_min + node->bounds.x_max) / 2;
        double y_mid = (node->bounds.y_min + node->bounds.y_max) / 2;
        
        std::array<Bounds, 4> bounds = {{
            {node->bounds.x_min, node->bounds.y_min, x_mid, y_mid},
            {x_mid, node->bounds.y_min, node->bounds.x_max, y_mid},
            {node->bounds.x_min, y_mid, x_mid, node->bounds.y_max},
            {x_mid, y_mid, node->bounds.x_max, node->bounds.y_max}
        }};
        
        for (int i = 0; i < 4; i++) {
            node->children[i] = std::make_unique<Node>(bounds[i]);
        }
        
        node->isLeaf = false;
        
        for (const auto& p : node->points) {
            int quadrant = 0;
            if (p.x >= x_mid) quadrant |= 1;
            if (p.y >= y_mid) quadrant |= 2;
            node->children[quadrant]->points.push_back(p);
        }
        
        node->points.clear();
    }
    
    void insert(Node* node, const Point& point) {
        if (!inBounds(node->bounds, point)) return;
        
        if (node->isLeaf) {
            if (node->points.size() < MAX_POINTS) {
                node->points.push_back(point);
                return;
            }
            subdivide(node);
        }
        
        double x_mid = (node->bounds.x_min + node->bounds.x_max) / 2;
        double y_mid = (node->bounds.y_min + node->bounds.y_max) / 2;
        
        int quadrant = 0;
        if (point.x >= x_mid) quadrant |= 1;
        if (point.y >= y_mid) quadrant |= 2;
        
        insert(node->children[quadrant].get(), point);
    }
    
    void rangeQuery(Node* node, const Bounds& query, std::vector<Point>& results) {
        if (!intersects(node->bounds, query)) return;
        
        if (node->isLeaf) {
            for (const auto& p : node->points) {
                if (inBounds(query, p)) {
                    results.push_back(p);
                }
            }
        } else {
            for (int i = 0; i < 4; i++) {
                rangeQuery(node->children[i].get(), query, results);
            }
        }
    }
    
public:
    QuadTree(double x_min, double y_min, double x_max, double y_max) {
        root = std::make_unique<Node>(Bounds{x_min, y_min, x_max, y_max});
    }
    
    void insert(double x, double y) {
        insert(root.get(), {x, y});
    }
    
    std::vector<Point> rangeQuery(double x_min, double y_min, double x_max, double y_max) {
        std::vector<Point> results;
        rangeQuery(root.get(), Bounds{x_min, y_min, x_max, y_max}, results);
        return results;
    }
};

四叉树/八叉树变体

变体 特点 应用
点四叉树 存储点数据 空间索引
区域四叉树 存储区域信息 图像处理
边四叉树 存储边界信息 地理信息系统
PR四叉树 点区域四叉树 数据库索引
线性四叉树 用编码表示节点 压缩存储 
graph TB
    subgraph 四叉树变体
        A["四叉树"]
        B["点四叉树"]
        C["区域四叉树"]
        D["PR四叉树"]
        E["线性四叉树"]
        
        A --> B
        A --> C
        A --> D
        A --> E
    end
    
    style A fill:#4CAF50,color:#fff

时间复杂度

四叉树

操作 平均 最坏 说明
插入 O(log n) O(n) 依赖点分布
删除 O(log n) O(n)
范围查询 O(log n + m) O(n) m为结果数
最近邻 O(log n) O(n)

八叉树

操作 平均 最坏 说明
插入 O(log n) O(n)
范围查询 O(log n + m) O(n)
最近邻 O(log n) O(n)
性能依赖：四叉树/八叉树的性能高度依赖数据分布。点均匀分布时效率最高，点聚集时可能退化为线性结构。

空间复杂度

结构 空间复杂度 说明
四叉树 O(n) n为点数
八叉树 O(n) n为点数
最大深度 O(log n) 点均匀分布

应用场景

四叉树应用

应用领域 具体场景
图像处理 图像压缩、区域分割
地形渲染 LOD（细节层次）管理
碰撞检测 2D空间物体检测
地理信息系统 空间索引、地图渲染
游戏 视锥剔除、地形管理

八叉树应用

应用领域 具体场景
点云处理 点云压缩、法向量估计
3D碰撞检测 空间划分、碰撞检测
体素渲染 体素数据管理
3D图形 视锥剔除、LOD
医学影像 CT/MRI数据处理

四叉树 vs 八叉树 vs 其他结构

结构 维度 子节点数 优势 劣势
四叉树 2D 4 简单、高效 仅限2D
八叉树 3D 8 适合3D 高维扩展差
KD树 任意 2 维度无关 动态更新难
R树 任意 M 动态更新 实现复杂
选择建议：2D空间优先选择四叉树，3D空间选择八叉树，更高维度或动态更新频繁时选择R树或KD树。

实际应用示例

图像压缩（区域四叉树）

原始图像

→

压缩后

1 0 0 0
1: 黑色区域 0: 白色区域

点云压缩（八叉树）

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
// 点云体素化
class PointCloudOctree {
    OctTree tree;
    double voxelSize;
    
public:
    void addPoint(double x, double y, double z) {
        // 体素化坐标
        int vx = floor(x / voxelSize);
        int vy = floor(y / voxelSize);
        int vz = floor(z / voxelSize);
        
        // 插入到八叉树
        tree.insert(vx * voxelSize, vy * voxelSize, vz * voxelSize);
    }
};

地形LOD（四叉树）

地形渲染LOD

近距离（高细节）

→

远距离（低细节）

参考资料

  • Finkel, R. A., Bentley, J. L. (1974). Quad Trees: A Data Structure for Retrieval on Composite Keys
  • Samet, H. (1990). The Design and Analysis of Spatial Data Structures
  • Meagher, D. (1982). Geometric Modeling Using Octree Encoding