栅格数据的四叉树.ppt

栅格数据的四叉树编码 王成龙 邱陶 李亚飞 杜欣威 张军 曹恩溯 吕佳琪 设计思路 构建完全四叉树 从底向上合并节点 获取非象元节点的索引 将完全四叉树中的有效节点存储到Raster_Qtree中去 构建完全四叉树 栅格数据的四叉树分层，各层的节点数分别应为4、16、64、256…… 根据各层的节点数为各层分配内存 最底层的节点数正好为填充后栅格总数，根据Morton码获取象元的行列值，从Morton 为0开始填充四叉树底层。 构建的同时可以获取有效象元的总个数 从底向上合并节点 从底层开始，以每层最后一个节点起，对每四个非中间节点，判断其象元值是否相等 相等则在上一层相对位置保存其像元值，不相等，则保存像元值为-1，NextIndex为从底层最后一个开始的有效节点的个数。 获取非象元节点的索引 从最上层开始，对非叶子节点象元，其象元索引为从上层开始到此节点所对应的下层节点前所有有效节点的个数。 缺点，每次遍历有效节点，效率极低。 改进：合并象元时已存储此节点所对应的下层节点到最后的有效节点个数，用总结点减去即可得到。 A1 B1 C1 B2 B3 B4 C2 C3 C4 A2 A3 A4 节点号 B1 B2 索引值 A1→C1 -1 改进后的索引计算方法 Sum-B1的NextIndex（C4→B1） Sum-B2的NextIndex （C4→B2） 将完全四叉树中的有效节点存储到Raster_Qtree中去 根据有效节点个数分配内存 从四叉树顶层开始，顺序存储每层有效节点 算法重点 通过morton获取象元的行列值，当行列值不在原来的栅格图层范围内的时候，需要自定义一个栅格值，而没有办法从原栅格中得到。 算法难点-获取四叉树层数 for (i = 0; i 30; i++) { if ((((maxRowsColu-1) i) 0x7fffffff) == 1) { treelevel = i; break; } } treelevel++; maxRowsColu=4 将0011左移后得到0001后和11111…比较 结果是1，则层数=i=1，之后再将得到的层数加1，得到了最终的层数2。 3X4 之所以要先减1，循环结束后再加1是因为： 当既不减一下方也不加一时 若栅格为2X2时，会是1层，栅格为3X3时，也会是1层，但实际应该有2层。 但若只是在循环外加一，则当栅格为2X2时，会使层数为2。 算法难点-通过行列值获取morton值 int GetMortonIndex(int rowindex, int columnindex, int level) { int i,morton=0; for(i = 0; i level; i++) { morton |= ( ((rowindex i) 1) (i * 2) ); morton |= ( ((columnindex i) 1) ( (i * 2) + 1) ); } return morton; } 算法难点-通过morton获取行列值 void GetRowColumnIndex(int morton, int level, int* rowindex,int* columnindex) { int i; *rowindex=*columnindex=0; for(i = 0; i level; i++) { *rowindex |= ( ((morton (i * 2)) 1) i ); *columnindex |= ( ((morton ( (i * 2) + 1)) 1) i ); } } 谢谢