QuadTree是什么

QuadTree（四叉树）是一种将二维空间递归划分成四个子区域的空间索引结构。

简单来说：

QuadTree就是不断把一个空间区域分成四块，用树形结构管理空间数据。

例如：

一个区域
    ↓
分成4个区域
    ↓
需要时继续分成4个
    ↓
形成树形空间索引

QuadTree常用于：

GIS空间索引
地图渲染
附近搜索
碰撞检测
点数据查询
地图瓦片管理
大规模空间数据处理

QuadTree的核心思想

普通数据结构通常按照：

数组
链表
树

组织数据。

QuadTree则按照：

空间位置
    ↓
区域划分
    ↓
树形结构

组织二维空间数据。

例如一个地图区域：

┌───────────────┐
│               │
│               │
│      ●        │
│               │
│               │
└───────────────┘

可以划分成：

┌───────┬───────┐
│       │       │
│   ●   │       │
│       │       │
├───────┼───────┤
│       │       │
│       │       │
│       │       │
└───────┴───────┘

也就是：

一个区域
    ↓
左上
右上
左下
右下

四个子区域。

QuadTree为什么叫四叉树

Quad的意思是：

Quad
 ↓
Four
 ↓
四

Tree：

Tree
 ↓
树

所以：

QuadTree
    ↓
四叉树

每个空间节点最多拥有4个子节点：

              Root
          /    |    |    \
        NW     NE   SW    SE

通常可以理解为：

NW = North West
NE = North East
SW = South West
SE = South East

即：

左上
右上
左下
右下

QuadTree的空间结构

最简单的QuadTree只有一个根节点：

Root

当数据量超过阈值后：

Root
  ↓
Split

变成：

          Root
       /   |   |   \
     NW   NE  SW   SE

如果某个子区域仍然包含大量数据：

NW
 ↓
Split

继续变成：

             Root
        ┌─────┼─────┐
       NW    NE    SW    SE
       ↓
   ┌───┼───┐
  NW  NE  SW  SE

如此递归下去。

QuadTree的层级

QuadTree具有明显的层级结构：

Level 0
    ↓
Root

Level 1
    ↓
4个区域

Level 2
    ↓
16个区域

Level 3
    ↓
64个区域

可以看到：

Level 0 = 1
Level 1 = 4
Level 2 = 16
Level 3 = 64
Level 4 = 256

理论上第 n 层最多有：

4^n

个空间节点。

QuadTree的数据存储

假设地图中有很多Point：

● ● ● ●
  ● ●
●   ● ●
    ●

QuadTree会根据Point所在位置将它们放入不同区域：

┌─────────┬─────────┐
│ ● ●     │ ●       │
│   ●     │     ●   │
├─────────┼─────────┤
│ ●       │ ● ●     │
│         │   ●     │
└─────────┴─────────┘

这样查询某个区域时：

查询区域
    ↓
找到对应QuadTree节点
    ↓
只检查相关区域

而不是扫描所有Point。

QuadTree的容量阈值

QuadTree通常会设置一个节点容量。

例如：

capacity = 4

表示：

一个节点最多保存4个对象。

例如：

Node
├── Point 1
├── Point 2
├── Point 3
└── Point 4

当加入第5个Point：

Point 5
    ↓
超过capacity
    ↓
节点分裂

变成：

             Node
       ┌──────┼──────┐
      NW     NE     SW     SE

然后重新分配数据。

QuadTree的分裂

QuadTree最核心的操作之一就是Split。

例如：

┌────────────────┐
│                │
│  ● ● ● ● ●     │
│                │
└────────────────┘

假设容量是4：

5个Point
    ↓
超过容量
    ↓
Split

变成：

┌────────┬────────┐
│ ● ●    │ ●      │
│        │        │
├────────┼────────┤
│        │ ● ●    │
│        │        │
└────────┴────────┘

之后每个区域独立管理自己的数据。

QuadTree的查询

假设需要查询：

某个矩形区域

普通方法可能：

所有Point
    ↓
逐个判断

例如：

100万个Point
    ↓
检查100万个Point

QuadTree可以：

查询区域
    ↓
Root
    ↓
判断哪些子区域相交
    ↓
只进入相关节点
    ↓
检查少量Point

因此可以减少无意义的数据检查。

Range Query

QuadTree非常适合矩形范围查询。

例如：

查询：

x1 < x < x2
y1 < y < y2

地图上可以表示为：

┌────────────────────────┐
│                        │
│     ┌──────────┐       │
│     │ 查询区域 │       │
│     │          │       │
│     └──────────┘       │
│                        │
└────────────────────────┘

QuadTree可以快速找到与查询区域相关的节点。

典型流程：

Query Rectangle
       ↓
QuadTree
       ↓
相交节点
       ↓
候选Point
       ↓
精确判断
       ↓
返回结果

QuadTree与附近搜索

QuadTree也可以用于附近搜索。

例如：

用户位置
    ●

需要查询：

500米范围内的POI

可以先构造查询范围：

        ┌───────┐
        │       │
        │   ●   │
        │       │
        └───────┘

然后：

附近范围
    ↓
QuadTree
    ↓
候选对象
    ↓
精确距离计算

因此：

QuadTree
    ↓
空间粗筛

再使用：

Distance
    ↓
精确距离

这是一种非常常见的空间查询优化思路。

QuadTree与Geometry

QuadTree可以索引不同类型的空间对象。

例如：

Point
LineString
Polygon

但实际实现时通常不是直接比较复杂Geometry，而是使用它们的：

Bounding Box

即：

Geometry
    ↓
Bounding Box
    ↓
QuadTree

例如：

Polygon
   ↓
┌──────────┐
│          │
│ Polygon  │
│          │
└──────────┘

用外接矩形参与空间索引。

Bounding Box

Bounding Box简称：

BBox

例如一个Point：

●

可以表示成：

┌───┐
│ ● │
└───┘

一个Polygon：

     /────\
    /      \
   /        \
   \        /
    \______/

对应：

┌──────────┐
│  Polygon │
└──────────┘

QuadTree通常通过BBox判断对象是否属于某个空间节点。

QuadTree与空间相交

例如查询：

┌─────────────┐
│ Query       │
│             │
└─────────────┘

QuadTree节点：

┌───────┬───────┐
│   A   │   B   │
├───────┼───────┤
│   C   │   D   │
└───────┴───────┘

如果查询区域只与A、B相交：

Query
 ↓
A
B

就不需要检查：

C
D

这就是空间索引减少搜索范围的核心原理。

QuadTree与地图渲染

WebGIS中经常需要显示大量对象。

例如：

100000个Point

如果全部渲染：

地图
 ↓
100000个Marker

会造成较大的：

CPU压力
GPU压力
DOM压力
网络数据压力

QuadTree可以帮助判断：

当前地图视口
    ↓
QuadTree
    ↓
可见区域
    ↓
只加载可见对象

例如：

整个地图
┌────────────────────┐
│                    │
│                    │
│      ┌──────┐      │
│      │ View │      │
│      └──────┘      │
│                    │
└────────────────────┘

只查询View范围内的数据。

QuadTree与LOD

LOD表示：

Level of Detail

即：

不同缩放级别使用不同精细程度的数据。

QuadTree天然具有层级结构：

Root
 ↓
Level 1
 ↓
Level 2
 ↓
Level 3

可以配合地图缩放：

缩小地图
    ↓
低层级数据
    ↓
少量对象

放大地图
    ↓
高层级数据
    ↓
更多细节

因此：

QuadTree
+
LOD

非常适合地图渲染优化。

QuadTree与瓦片

地图瓦片通常按照：

Zoom
X
Y

组织。

QuadTree也可以理解为一种空间递归划分方式：

Zoom 0
    ↓
1个区域

Zoom 1
    ↓
4个区域

Zoom 2
    ↓
16个区域

Zoom 3
    ↓
64个区域

这种结构与瓦片金字塔非常相似。

因此很多地图系统都可以使用类似四叉树的空间层级思想管理：

地图瓦片
地形数据
影像数据
3D Tiles

QuadTree与地图瓦片

一个简单的关系可以表示为：

World
  ↓
Tile
  ↓
4个子Tile
  ↓
每个Tile继续分成4个

例如：

        World
          ↓
    ┌─────┬─────┐
    │     │     │
    ├─────┼─────┤
    │     │     │
    └─────┴─────┘

继续：

每个Tile
    ↓
4个子Tile

形成：

Tile Pyramid

QuadTree与R-Tree

QuadTree和R-Tree都属于空间索引结构。

但两者思路不同。

QuadTree：

固定空间
    ↓
递归划分
    ↓
四个子区域

R-Tree：

空间对象
    ↓
Bounding Box
    ↓
层级组织

简单对比：

特性	QuadTree	R-Tree
基本思想	划分空间	组织BBox
子节点	通常4个	数量可变
空间划分	规则	不规则
Point数据	很适合	适合
Polygon数据	适合	很适合
GIS数据库	常见	非常常见
实现复杂度	较低	较高

QuadTree与KD-Tree

KD-Tree也是空间索引结构。

KD-Tree：

一次沿一个维度切分

例如：

X方向
    ↓
Y方向
    ↓
X方向
    ↓
Y方向

QuadTree：

一次同时切成4个区域

例如：

       Root
    ↙  ↘
   ↘    ↙
  四个区域

简单理解：

KD-Tree
    ↓
逐维切分

QuadTree
    ↓
二维空间四分

QuadTree与H3

H3和QuadTree都可以用于空间索引，但设计思想不同。

QuadTree：

空间
 ↓
四叉递归划分
 ↓
矩形区域

H3：

地球
 ↓
六边形网格
 ↓
H3 Index

对比：

特性	QuadTree	H3
空间结构	四叉树	六边形网格
网格形状	矩形	六边形
层级	有	有
邻居关系	由节点关系确定	原生支持
空间聚合	支持	很适合
动态数据	很适合	很适合
Web地图	很适合	很适合
全球网格	不强调	核心能力

可以简单记住：

QuadTree强调递归空间划分，H3强调层级六边形网格。

QuadTree与GeoHash

GeoHash：

经纬度
 ↓
字符串编码
 ↓
矩形网格

QuadTree：

空间
 ↓
递归四分
 ↓
树结构

两者实际上存在一定联系。

GeoHash的空间编码过程本身就具有类似递归二分空间的思想。

可以简单理解为：

GeoHash
    ↓
空间编码

QuadTree
    ↓
空间树索引

QuadTree的深度

QuadTree通常需要设置最大深度。

例如：

maxDepth = 10

表示最多划分：

Root
 ↓
Level 1
 ↓
Level 2
 ↓
...
 ↓
Level 10

为什么需要最大深度？

因为如果某个区域中存在大量位置非常接近的数据：

●●●●●●●●●●

QuadTree可能不断分裂。

设置最大深度可以避免：

无限递归

QuadTree的停止条件

常见的停止条件包括：

节点数量 <= capacity

或者：

depth >= maxDepth

因此一个节点是否继续分裂通常判断：

对象数量 > capacity
AND
当前深度 < maxDepth

如果不满足：

停止分裂

QuadTree的基本操作

一个典型QuadTree通常包含：

insert()
query()
remove()
subdivide()
clear()

其中：

insert

插入空间对象：

Point
 ↓
QuadTree

query

查询区域：

BBox
 ↓
QuadTree
 ↓
Objects

remove

删除对象：

Object
 ↓
QuadTree
 ↓
Remove

subdivide

将节点划分成四个子节点：

Node
 ↓
4 Children

QuadTree插入流程

例如插入一个Point：

Point
 ↓
Root

判断Point是否在Root范围内：

是
 ↓
节点是否已满？

如果没有：

直接存储

如果已满：

Subdivide
 ↓
4个子节点
 ↓
判断Point属于哪个子区域
 ↓
递归Insert

流程可以表示为：

insert(Point)
     ↓
   Root
     ↓
是否超过容量？
  ↙       ↘
否         是
↓           ↓
存储       Subdivide
             ↓
        4个子节点
             ↓
          Insert

QuadTree查询流程

查询一个区域：

query(BBox)

首先判断：

BBox是否与当前节点相交？

如果不相交：

直接跳过

如果相交：

检查当前节点对象
    ↓
继续检查子节点

流程：

Query
  ↓
Root
  ↓
是否相交？
 ↙      ↘
否       是
↓         ↓
跳过     检查对象
           ↓
       子节点Query

QuadTree的优点

1. 查询速度快

可以避免扫描整个数据集：

全部数据
    ↓
空间索引
    ↓
候选数据

2. 结构简单

QuadTree的实现相对直观：

Node
├── Bounds
├── Objects
├── NW
├── NE
├── SW
└── SE

3. 适合二维空间

尤其适合：

Point
二维坐标
地图对象

4. 支持动态插入

数据可以不断：

insert
remove

因此适合动态地图数据。

5. 适合视口查询

例如：

当前地图Viewport
    ↓
QuadTree
    ↓
可见对象

非常适合WebGIS。

QuadTree的缺点

1. 数据分布不均会影响效率

例如所有数据都集中在一个角落：

┌───────────────┐
│               │
│               │
│         ●●●●● │
│         ●●●●● │
└───────────────┘

可能导致某些区域不断分裂。

2. 不一定适合所有Geometry

复杂Polygon可能跨越多个节点。

例如：

┌───────┬───────┐
│       │       │
│   ┌─────────┐ │
│   │ Polygon │ │
├───┴─────────┴─┤
│               │
└───────────────┘

这时候需要使用BBox进行候选筛选。

3. 参数需要合理设置

例如：

capacity
maxDepth

设置不合理会影响性能。

QuadTree在GIS中的典型应用

QuadTree可以用于：

地图POI
    ↓
QuadTree

车辆位置
    ↓
QuadTree

GPS轨迹
    ↓
QuadTree

地图标注
    ↓
QuadTree

碰撞检测
    ↓
QuadTree

地图视口查询
    ↓
QuadTree

QuadTree在WebGIS中的应用

假设地图上有：

500000个POI

用户当前只看到：

北京某个区域

不应该：

500000个POI
    ↓
全部发送
    ↓
全部渲染

而应该：

500000个POI
      ↓
    QuadTree
      ↓
当前Viewport
      ↓
可见POI
      ↓
前端渲染

这样可以大幅减少需要处理的数据量。

QuadTree与聚类

地图缩小时：

大量Point

可以通过QuadTree快速找到空间上相近的Point：

● ● ● ●
 ● ● ●
  ● ●

然后进行：

Cluster

变成：

   ◉ 120

地图放大后：

Cluster
 ↓
展开
 ↓
Point

因此：

QuadTree
+
Point Cluster

是地图Marker聚类中常见的组合思路。

QuadTree与碰撞检测

QuadTree不仅用于GIS，也经常用于游戏和图形计算。

例如：

对象A
对象B
对象C
...

如果直接检测：

A vs B
A vs C
A vs D
...

对象数量多时计算量很大。

QuadTree可以先：

空间划分
    ↓
只比较同一区域或相邻区域对象

因此：

QuadTree
    ↓
Broad Phase
    ↓
候选对象
    ↓
精确碰撞检测

这与GIS空间查询的思想非常类似。

QuadTree知识结构

可以将QuadTree理解成：

QuadTree
├── Root
│
├── Bounds
│
├── Capacity
│
├── Subdivide
│
├── Child Nodes
│   ├── NW
│   ├── NE
│   ├── SW
│   └── SE
│
├── Insert
├── Query
├── Remove
└── Max Depth

最核心的几个概念：

空间
 ↓
四分
 ↓
递归
 ↓
树结构
 ↓
空间查询

QuadTree与GIS空间索引体系

可以把QuadTree放到GIS空间索引体系中：

GIS空间数据
      ↓
Geometry
      ↓
Bounding Box
      ↓
Spatial Index
      ↓
QuadTree
      ↓
快速空间查询

其他常见空间索引还有：

QuadTree
R-Tree
KD-Tree
GeoHash
H3

它们解决的核心问题都是：

如何快速从大量空间数据中找到与指定空间范围相关的数据。

一个完整的空间查询流程

例如查询：

查询地图当前视口中的所有POI。

可以使用：

POI数据
    ↓
建立QuadTree
    ↓
用户移动地图
    ↓
获取Viewport BBox
    ↓
QuadTree.query(BBox)
    ↓
获得候选POI
    ↓
必要时进行精确Geometry判断
    ↓
返回POI
    ↓
地图渲染

完整结构：

Viewport
    ↓
BBox
    ↓
QuadTree
    ↓
Spatial Query
    ↓
Candidate Objects
    ↓
Exact Geometry Check
    ↓
Result

总结

QuadTree（四叉树）是一种基于递归四分空间的二维空间索引结构。

它的核心过程是：

一个空间
    ↓
划分成4个区域
    ↓
继续递归划分
    ↓
形成四叉树

最重要的概念包括：

Root
Bounds
Capacity
Subdivide
NW
NE
SW
SE
Insert
Query
MaxDepth

QuadTree特别适合：

GIS空间查询
地图视口查询
POI查询
附近搜索
地图Marker聚类
大规模Point数据
地图渲染优化
碰撞检测

可以记住：

QuadTree不是一种Geometry，而是一种空间索引结构。它通过不断将二维空间划分成四个子区域，让GIS能够快速定位和查询空间数据。

最典型的GIS应用流程是：

大量空间数据
      ↓
QuadTree
      ↓
空间递归划分
      ↓
Viewport / BBox查询
      ↓
候选空间对象
      ↓
精确空间判断
      ↓
地图显示

🧰