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

《基于四叉树的LiDAR点云数据组织研究》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、文章编号：0494-0911(2008)11X)021-03中图分类号:P237文献标识码』基于四叉树的LiDAR点云数据组织研究陈冈9,张芯，张明，石宏斌(中国地质大学(武汉)信息工程学院，湖北武汉430074)StudyoftheOrganizationofLiDARPointsCloudDataBasedonQuadtreeCHENGang,ZHANGXin,ZHANGMing,SHIHong-bin摘要：针对传统的数据读取方法不能満足LiDAR点云数据尿大的待点，塔于WindowH的内存映射机制•研究LiDAR点

2、心数据组织，利用四义树对LiDAR点云数据进行索引管理，并在LiDAR点云的三维场駅绘制中对点公数据进行的裁•碱轻CPU的负帆捉薛氏运第的效率。关键词:UDAR；PMX树；内“映射四叉树是一种常见的空间索引，它是基于空间划分组织索引结构的索引机制。如果将(2知范碉的空间划成四个相等的齐空间，若帶耍叮以将每个或英中儿个子空间继续划分下去，这样就形成了一个基于四叉树的空间划分⑴。目前国内比较成熟的软件SuperMap,MapGIS均是采用四义树作为索引方法对数据进行组织的。机载激光雷达(LiDAR)是一种主动式的对地观测系统

3、。通过HDAR传感器发射的激光脉冲，能直接连续自动获取高箱度三维地表地形数据。尽管LiDAR硕件系统发展迅速，但数据后处理过程中的许多算法和模型冇待完善⑺。本文的冃标就是要研究IJDAR点云数据组织，针对传统的数据读取方法不能满足UDAR点云数据疑大的特点，研究基于Windows的内存映射机制，利用四叉树对IJDAK点云数据进行索引管理，并在LiDAR点云的三维场景绘制中对点云数据进行剪裁。!1!四叉树有线性四叉树和链式四叉树，本文只讨论链式四叉树。在数据结构中，树用来表达一对多的非线性数据关系。在n(n>0)个结点的有

4、限集合中，它或为空树(n=0),或是由一个根结点加上四棵称为子树的、互不相交的四叉树组成。四叉树是一种递归的方法，其中每个结点的度不大于4。其数据结构如下：structQuardTreeI〃结点所表示的数据范围DOUBLEx_Min,x_Max；DOUBLEy_Min,y_Max；intm」^intCount；//点云链表structPointlD*pointhead;//指向头结点的IDstructPointlD*pointCurrent；//指向当前结点的ID〃指向四个孩子结点structQuardTree*tree

5、4J；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

6、++)收稿日期：200809-22作者简介：陈刚(197】・)男■湖北咸宁人，博士，副教授，研究方向为“3S"技术在资源与环境遥感中的应用。ni_QuardTree->tree：i]=EDGEPOINT；m_QuardTree->pRoot=NULL；m_QuardTree->m_PointCount=0；m_QuardTree->pointhead=NULL；m_QuardTree->pointCurrent=NULL；根结点创建之后，需要读数据文件，每读入一个点，创建一个点类(CDot)对象,为其赋予一个ID号，这个

7、ID信息存储在点类对象中，并把这个对象保存在对象数组中，然后根据该点所属的区域，将该II)插入到四叉树中,其插入的过程是个递归调用的过程。其实现原理为:将一个ID插入根结点,首先判断该树是否为空，然后判断该ID所标识的点是否属于该四叉树所表达的区域，如果是判断根结点是否为叶结点,如杲为叶子结点,将该点插入根结点，继续读文件。当在根结点插入点数大于某限定值(一般不大于1啤2厲)，四叉树进行四均分，将父结点的点按照所屈于的沪区域撒播，并将父布点中的点云链表赋空。在插入的过程中主要涉及叶子结点的判断及点与矩形关系的判断，是否为

8、叶子结点主要看该结点的四个子结点是否为空，如果为空,则为叶结点。点与矩形关系的判断主要看大』是否在该区域兀』的最小最大值中，如果同时满足，则在矩形区域中。其实现代码如下：〃叶子结点的判断BOOLCOpenGL：：Isl^a£

9、unction(QuardTree*T)IintFLAG=0；for(inti=0；i<4；