基于四叉树的LiDAR点云数据组织研究.doc

基于四叉树的LiDAR点云数据组织研究.doc文章编号:0494-0911(2008)11X)021-03中图分类号:P237文献标识码』基于四叉树的LiDAR点云数据组织研究陈冈9,张芯,张明,石宏斌(中国地质大学(武汉)信息工程学院,湖北武汉430074)anizationofLiDARPointsCloudDataBasedonQuadtreeCHENGang,ZHANGXin,ZHANGMing,SHIHong-bin摘要:针对传统的数据读取方法不能満足LiDAR点云数据尿大的待点,塔于WindowH的内存映射机制•研究LiDAR点心数据组织,利用四义树对LiDAR点云数据进行索引管理,并在LiDAR点云的三维场駅绘制中对点公数据进行的裁•碱轻CPU的负帆捉薛氏运第的效率。关键词:UDAR;PMX树;内“映射四叉树是一种常见的空间索引,它是基于空间划分组织索引结构的索引机制。如果将(2知范碉的空间划成四个相等的齐空间,若帶耍叮以将每个或英中儿个子空间继续划分下去,这样就形成了一个基于四叉树的空间划分⑴。目前国内比较成熟的软件SuperMap,MapGIS均是采用四义树作为索引方法对数据进行组织的。机载激光雷达(LiDAR)是一种主动式的对地观测系统。通过HDAR传感器发射的激光脉冲,能直接连续自动获取高箱度三维地表地形数据。尽管LiDAR硕件系统发展迅速,但数据后处理过程中的许多算法和模型冇待完善⑺。本文的冃标就是要研究IJDAR点云数据组织,针对传统的数据读取方法不能满足UDAR点云数据疑大的特点,研究基于Windows的内存映射机制,利用四叉树对IJDAK点云数据进行索引管理,并在LiDAR点云的三维场景绘制中对点云数据进行剪裁。!1!四叉树有线性四叉树和链式四叉树,本文只讨论链式四叉树。在数据结构中,树用来表达一对多的非线性数据关系。在n(n>0)个结点的有限集合中,它或为空树(n=0),或是由一个根结点加上四棵称为子树的、互不相交的四叉树组成。四叉树是一种递归的方法,其中每个结点的度不大于4。其数据结构如下:structQuardTreeI〃结点所表示的数据范围DOUBLEx_Min,x_Max;DOUBLEy_Min,y_Max;intm」^intCount;//点云链表structPointlD*pointhead;//指向头结点的IDstructPointlD*pointCurrent;//指向当前结点的ID〃指向四个孩子结点structQuardTree*tree4J;I;二、四叉树的建立当读取数据文件的时候,需要获取数据文件的的放大瑕小值,用于建立四叉树的根结点,获取最人最小值后,将最大最小值赋给对应的变量,并对四个子结点赋空,用于将其标识为叶子结点,根结点的实现过程如下:structQuardTree*m_QuardTree=newQuardTree();m_QuardIree->x_Max=xMax;m_QuardTree->x_Min=xMin;m_QuardTree->y_Max=yMax;m_QuanlTree->y_Min=yMin;for(inti=0;i<4;i++)收稿日期:200809-22作者简介:陈刚(197】・)男■湖北咸宁人,博士,副教授,研究方向为“3S"技术在资源与环境遥感中的应用。ni_QuardTree->tree:i]=EDGEPO