四叉树(Quadtree)

定义

四叉树(Quadtree)是一种每个内部节点恰有四个子节点的树,由 Finkel 和 Bentley 于 1974 年提出,用于把二维空间递归划分为四个象限,直到每个区域内的对象数或细分深度满足阈值。

类型

常见变体包括:点四叉树(以数据点为分割中心)、区域四叉树(固定几何四等分,常用于图像)、PR 四叉树(点数据的规则划分)以及松散四叉树(游戏中缓解对象跨界问题)。

应用

地理信息系统用四叉树做空间索引与瓦片金字塔组织;游戏引擎用它加速二维碰撞检测,只需检测同区域及邻近区域的对象;图像处理领域用区域四叉树表示与压缩二值图像;地图服务的瓦片编号方案本质上也是四叉树编码。

优缺点

优点是结构直观、自适应数据密度、构建简单;缺点是数据分布极不均匀时树会很深,且相邻对象可能被边界切开,需要跨节点合并查询结果。