| 词条 | CIF四叉树 |
| 释义 | CIF(Caltech Intermediate Form)四叉树。CIF 四叉树是针对表示 VLSI (Very LargeScale Integration)应用中的小矩形而提出的，它可以用于索引空间矩形及其它形体。采用 CIF 四叉树索引结构时，资料空间被递归地细分直至产生的子象限不再包含任何矩形。在分解的过程中，所有与任一划分线相交的矩形与该划分线对应的象限相关联，属于一个象限的矩形不能属于任何祖先象限，也就是说，矩形只属于完全包围它的最小象限。下图 是一颗传统四叉树和 CIF 四叉树的例子。在CIF四叉树中待分区域被递归的分成最小区域不再包含任何空间对象，而且空间对象只属于完全包含它的一个最小区域，没有数据的冗余现象。在具体的算法实现过程中当空间对象与任何一个切割线相交，这个空间对象就属于包含这条切割线的区域，空间对象被存储在区域对应的四叉树结点中。这点也是CIF四叉树和传统的 四叉树最明显的一个区别，CIF四叉树解决了传统四叉树结构索引空间复杂形体数据冗余的不足。图4-6是CIF四叉树的结构示意图。 CIF四叉树插入一个空间对象时从根结点开始搜索，若空间对象与根结点对应的切割线相交就直接把空间对象存储在根结点上，如果不相交就检查完全包含空间对象的子区域，直到空间对象与某一切割线相交，如此递归循环下去。若搜索到了叶子结点也没有任何一切割与空间对象相交，就把叶子结点对应的子区域重新切割，重新递归上述过程直到空间对象与某一条切割线相交。 CIF删除一个空间对象，需要查询存储待删除空间对象的结点，直接从该结点中删除空间对象的信息。如果删除空间对象后导致该结点为空，需要一起删除该结点。在删除子结点的操作完成后，如果它的父结点同样不再存储任何空间对象则需要删除该父结点。上述过程可以看成插入对象的逆过程。在CIF四叉树上进行空间相交查询同样从根结点开始搜索，查询存储在根结点所有空间对象，看是否满足要求。然后再搜索与查询区域相交的子结点空间，如此循环下去，遇到叶子节点时搜索停止。 相比其他几种四叉树，CIF四叉树可以索引空间折线，空间面等复杂的空间形体，不需要进行近似技术。因此CIF四叉树在区域查询的效率比其他的四叉树索引都要高。但是当CIF四叉树面对海量的空间数据时，空间索引量非常大使得CIF四叉树空间索引的外存I/O开销很高。 详细介绍请参考 《基于改进四叉树空间索引的优化研究与应用》 《基於四叉树的线状实体拓扑规则检查演算法》 |
| 随便看 |
百科全书收录4421916条中文百科知识，基本涵盖了大多数领域的百科知识，是一部内容开放、自由的电子版百科全书。