GIS中四叉树索引及其分类介绍麻辣GIS

1、GIS中四叉树索引及其分类介绍 麻辣GIS 正文1点四叉树(Point Quadtree) 2. PR四叉树(Point Region Quadtree) 3. MX四叉树4.基于固定网格划分的四叉树 索 引5.线性可排序四叉树索引在GIS中，四叉树索引又分 为很多种类，包括点四叉树、PR四叉树、MX四叉树等，本 文这里做一个简单的介绍。1.点四叉树(Point Quadtree)点 四叉树与KD树相似，两者的差别是在点四叉树中，空间被分割 成四个矩形。四个不同的多边形分别是：SW、NW、SE、NEo 其搜索过程和KD树相似，当一个点包含在搜索范围内时被记录下 来，当一个子树和搜索范围有交叠时

2、它将被穿过。下图：点四叉 树示意图2. PR四叉树(Point Region Quadtree) PR四叉树是 点四叉树的一个变种，它不使用数据集中的点来分割空间。在PR 四叉树中，每次分割空间时，都是将一个正方形分成四个相等的 子正方形，依次进行，直到每个正方形的内容不超过所给定的桶 量(比如一个对象)为止。下图：PR四叉树3. MX四叉树空间被 分割成四个矩形。四个不同的多边形分别是：SW、NW、SE、NEo 每 次分割空间时，都是将一个正方形分成四个相等的子正方形，依 次进行，直到每个正方形的内容不超过所给定的桶量 (比如一个对象)为止。所有的数据都处在四叉树的同一个深 度，多个点可以由

3、一个指针联接。4.基于固定网格划 分的四叉树索引先看下图：非叶结点数： MAX_NONLEAFNODE_NUM二刀 N?li=04i 叶结点数： MAX_LEAFN0DE_NUM=2AN X 2“N=4N非叶结点从四叉 树的根结点开 始编号：从0到 MAX_NONLEAFNODE_NUM-1 叶子结点则从 MAX_NONLEAFNODE_NUM 开始编号，直到 MAX_NONLEAFNODE_NUM+MAX_LEAFNODE_NUM-1 在四叉树中，空间要素标识记录在其外包络矩形所覆盖的每一个 叶结点中，但是，当同一父亲的四个兄弟结点都要记录 该空间要 素标识时，则只将该空间要素标识记录在该父

4、亲结点上，并按这 一规则向上层推进。5.线性可排序四叉树索弓I 首先将四叉树分 解为二叉树，即在父结点层与子结点层之间插入一层虚结点，虚 结点不用来记录空间要素，然后按照中序遍历树的顺序对结点进 行编码，包括加入的虚结点。假设某个结点位于四叉树的第N 层，可排序四叉树编 码为Indexo它的四个子结点位于树的第N-1 层，编码从左 到右分别为：Index_CIndex-3X4X (N-1) Index_C2=Index4X (N 1) Index_C3=Index + 4X (N 1) Index_C4=Index +3X4X (N-1)通过编码值很容易 确定结点在 树中的层数。在进行查询时，给定一个查询范围，假定为矩 形，这个矩形范围唯一的对应一个四叉树结点。通 过结点的编 码，可以快速计算出在这棵子树下的所有子结点。找子结点的范 围的程序伪代码如下：GetlndexRange (long Index, long Min , long Max) long n = GetLayerNum(Index); Min 4X 篇: 制 =Max = Index;While (n0) Min = Min 一 3X (n 1) ;