四叉树编码

定义

四叉树编码是把二维空间按象限反复四等分、以四叉树结构存储空间数据的编码方法，又称四分树、四元树编码。在常见的栅格数据存储编码中，它通常与直接编码、链式编码、行程编码、块式编码并列^[2]。其处理对象多为 2^n×2^n 的像元阵列，n 为极限分割次数，n+1 即树的最大层数^[1]。

与逐行逐列记录每个格网的方式不同，这种方法让不同区域具有不同的分辨率：属性单一的大片区域用较大的方块记录，边界复杂处再细分到单个像元^[3]。因此它既是一种数据压缩手段，也是地理信息系统中组织空间数据的一种数据结构^[4]。

原理

四叉树编码的基本过程是递归分解。整个像元阵列被视为根结点，每个结点对应一个方形区域，并分出西北、东北、西南、东南四个分支^[1]。若某一分支覆盖的格网属性完全相同，或完全不属于目标区域，就不再往下分解，成为叶结点；否则继续四等分，直到每个叶结点只含一种属性^[2]。

按结点之间的联系方式，常见形式分为常规四叉树与线性四叉树。常规四叉树用指针连接父子结点，每个结点通常需要保存 4 个子结点指针、1 个父结点指针和结点值^[5]。线性四叉树则不用指针，只记录叶结点的位置编码与属性值，从而省去指针占用的存储空间^[6]。

线性四叉树的位置码常用莫顿码表示，即把行、列坐标的二进制位交错排列，得到一维编号；从根到叶的每一层，象限方向用 0、1、2、3 等数字记录，代码位数反映细分次数，也隐含了叶结点所代表区域的大小^[5]。把同样的分割思路推广到三维空间，便得到以八个子结点表示实体的八叉树。

一个根结点向四个象限分支的结构可示意如下：

graph TD

R[整个区域] --> NW[西北象限]

R --> NE[东北象限]

R --> SW[西南象限]

R --> SE[东南象限]

发展历程

四叉树这一名称由拉斐尔·芬科尔(Raphael Finkel)和 J. L. 本特利(J. L. Bentley)在 1974 年提出，他们发表于《Acta Informatica》的论文讨论了按复合键检索二维数据的存储结构，并给出了插入、区域查询和优化算法^[7][4]。

1982 年，I. 加甘蒂尼(Irene Gargantini)提出线性四叉树，用四进制整数为每个黑结点编码而不使用指针，并指出这种表示方式可节省至少 66% 的存储空间；该文还给出了像素编码、查找相邻结点、判断结点颜色以及叠加两幅图像等算法^[6]。

此后的研究提出了多种变体，例如以莫顿序列和广度优先遍历为基础的多色四叉树编码，以及用于压缩区域数据的二维行程编码(2DRE)^[8]。四叉树编码也被引入地理信息系统，用于表示区域、点和线状要素，并借助 B 树管理数量庞大的结点列表^[9]。在栅格与矢量一体化的数据结构设计中，线性四叉树编码进一步被用作基本的数据格式^[10]。

应用

在地理信息系统中，四叉树编码用于组织区域、点和线状要素，并支持集合运算、区域属性计算、地图编辑以及开窗检索等操作^[9]。

在空间数据库方面，四叉树编码可作为索引的编码方案。相关专利方案将空间对象的位置映射为一维字符串型索引编码，使原本不支持空间索引的非关系型数据库能够执行区域查询和点查询^[11]。

在图形与地形可视化中，四叉树用于多分辨率建模，即按照视点需要只绘制相应细节层次，以支持大范围数字地形模型的实时浏览。地图瓦片服务同样使用四叉树键标记瓦片，以四进制或十进制整数给出各级瓦片的地址^[12]。

局限

四叉树的树形表示不够稳定：形状和大小相同的多边形，可能因数据顺序或划分方式不同而得到不同的四叉树结构，因而不利于形状分析和模式识别^[1]。

建立和维护树结构本身也较复杂。若地图所反映的事物经常变化、多边形边界频繁修改，就需要反复刷新四叉树，耗费较多计算时间；当多边形较为零碎而分辨率要求不高时，简单的栅格结构反而更节省存储，叠合分析也更方便^[10]。

当数据分布极不均匀时，树会变得不平衡，朴素的自顶向下构造在最坏情况下时间复杂度可达平方级^[13]。另外，跨越格网边界的线状和面状目标必须上移到能够完整覆盖它的较上层结点，随着数据量增长，上层结点中的对象不断增多，会削弱索引的效率，这一困难也为其他采用硬边界切分的方法所共有^[14]。

参见

• 八叉树 —— 四叉树在三维空间的对应结构，用八个子结点分割空间。

• 莫顿码 —— 线性四叉树常用的位置编码，由坐标的二进制位交错排列得到一维编号。

• 行程编码 —— 与四叉树编码并列的一种栅格数据压缩编码方法。

• 地理信息系统 —— 四叉树编码的主要应用领域之一。

• R树 —— 面向线状和面状空间对象的另一种空间索引结构。