,直到自行设定的终止条件(比如每个节点关联图元的个数不超过3个,超过3个,就再四分),最终形成一颗有层次的四叉树。定义图中有数字标识的矩形是每个图元的MBR,每个叶子节点存储了本区域所关联的图元标识列表和本区域地理范围,非叶子节点仅存储了区域的地理范围。大家可以发现,同样存在一个图元标识被多个区域所关联,相应地存储在多个叶子节点上,比如“6“所代表的图元,分别存储在四个分枝上。四叉树算法算法优化3和13分别都跨越了两个区域,要被一个最小区域完全包含,就只能是根节点所代表的区域,2,5跨越了两个区域,6跨越了四个区域,要被一个最小区域完全包含,就只能是NW区域。4从List集合中根据标识一一取出图元,先判断图元MBR与矩形有无交集,如果有,则进行下面的精确几何判断,如果没有,则不再考虑此图元。四叉树索引步骤1从四叉树的根节点开始,把根节点所关联的图元标识都加到一个List里;2比较此矩形范围与根节点的四个子节点(或者叫子区域)是否有交集(相交或者包含),如果有,则把相应的区域所关联的图元标识加到List集合中,如果没有,则以下这颗子树都不再考虑。3以上过程的递归,直到树的叶子节点终止,返回List。改进后的四叉树索引解决了线,面对象的索引冗余,具有较好的性能,而被大型空间数据库引擎所采用,如ArcSDE,OracleSpatial等,同时这种结构也适用于空间数据的磁盘索引,配合空间排序聚类,基于分形的Hilbert算法数据组织,将在空间数据格式的定义中发挥重要作用。总结
四叉树算法 来自淘豆网m.daumloan.com转载请标明出处.
