Quadtree

释义 Definition

四叉树：一种用于二维空间划分的树形数据结构。它会把一个平面区域递归地分成四个象限（四个子区域），常用于图像处理、地理信息系统（GIS）、碰撞检测、空间索引等。也常指“四叉树索引/四叉树分解”。（在不同语境下还有若干变体，如点四叉树、区域四叉树。）

发音 Pronunciation (IPA)

/ˈkwɒd.tɹiː/ , /ˈkwɑːd.tɹiː/

例句 Examples

A quadtree can speed up searching for nearby points.
四叉树可以加速查找附近点的过程。

By storing map tiles in a quadtree, the application loads only the regions needed at the current zoom level, reducing memory and rendering time.
通过用四叉树存储地图切片，应用只加载当前缩放级别所需的区域，从而减少内存占用和渲染时间。

词源 Etymology

quad- 来自拉丁语，意为“四”；tree 指“树形结构”。合起来就是“四分的树”，直观描述了它把二维空间不断分成四块并形成层级结构的特点。

相关词 Related Words

• Octree
• R-Tree
• Kd-Tree
• Spatial
• Index
• Partition
• Recursion
• Node
• Bounding

文学与著作 Literary Works

• Hanan Samet，《The Design and Analysis of Spatial Data Structures》——系统讨论四叉树等空间数据结构与检索方法。
• Hanan Samet，《Foundations of Multidimensional and Metric Data Structures》——多维数据结构框架中包含四叉树及其应用。
• Christer Ericson，《Real-Time Collision Detection》——在实时碰撞检测与空间划分章节中涉及四叉树等结构。