三维散乱点集Voronoi图快速生成算法研究

提出了一种高效的三维散乱点集Voronoi图的生成算法。该算法采用点-面-体数据结构存储Voronoi单元,初始化首点Voronoi单元,通过单元分裂与单元重组快速生成新增点的Voronoi单元,并完成其相邻单元的维护。实验证明,该算法可快速准确地生成任意三维散乱点集的Voronoi图。基于该算法可有效地解决逆向工程中三维散乱数据点拓扑近邻的快速准确查询问题,对产品模型的曲面重建具有重要意义。     

基于球面投影的散乱点云三维建模算法实现与效果分析

介绍基于球面投影的散乱点云三维建模算法步骤,运用VC++编程语言结合OpenGL图形接口实现该算法,并结合实例说明球面投影法相对于圆柱面投影法、椭球面投影法在三维建模中的优势.     

海量散乱点云快速压缩算法

提出基于切片的海量散乱点云快速压缩方法,对点云进行分层生成切片点云,对每层切片点云使用弦高差法筛选利于表现形状的重要点,实现快速压缩。通过实验讨论参数对压缩结果的影响,并给出最佳参数值选择依据。对本方法和传统方法的压缩效果进行对比,证实本方法在实现高效压缩的同时能保留大量的特征细节。     

基于kd-tree的建筑物散乱点云平面分割

应用kd-tree快速确定散乱点云数据中某一个点的邻域,不需要先验地知道点云数据之间的拓扑(邻接)关系,使得建筑物点云平面分割算法更一般化,应用面更广。根据建筑物平面特征的先验信息,并采用高效数据结构,优化了平面分割算法,给出了散乱点云平面分割的实现和相应结果,说明了基于kd-tree的建筑物散乱点云平面分割算法的有效性。     

基于PCL的点云数据空间管理及近邻搜索

由三维激光扫描技术获取的点云数据仅包含点的三维坐标,缺乏点对应的几何拓扑信息,同时为了在计算机中更高效的管理和处理点云数据,本文结合PCL开源库为点云数据建立K-D树和八叉树两种数据结构,并实现基于K-D树和八叉树的快速邻域搜索。     

K-近邻长方体的点云特征提取压缩算法

针对海量点云数据存在大量冗余问题,该文提出基于K-近邻长方体的点云压缩算法。利用目标点的K近邻在非特征点云与特征点云之间的不同分布特性,基于该文算法将点云集合分为特征及非特征点集。该方法先对目标点近邻点进行坐标转换并构建K-近邻长方体,建立压缩准则,对长方体进行扁平程度筛选,结合分段采样去除大量冗余点及少量密集特征点,实现保留原始特征的点云压缩。该文方法涉及K、α、采样率β_(all)3个参数,在实验分析中,采用体积偏差、表面积偏差和Hausdorff距离对该文方法涉及的3个参数进行精度影响分析,结果表明,该方法能保留大量原始特征,在最优K值条件下β_(all)为0.4,α为0.9,此时体积偏差百分比为0.27%,表面积偏差百分比为0.5%,具有较高的压缩精度。     

一种平面散乱点集的自适应空间划分算法

针对平面散乱点集空间划分问题,提出了一种基于栅格统计的自适应空间划分算法。以栅格场为辅助手段为散乱点集建立空间索引,即判断各点与栅格的归属关系;统计各个栅格内包含点的数量;以栅格为基本统计单元对空间进行划分。划分过程中借助了二叉树结构,同时引入迭代次数作为划分终止的参数。该方法可灵活地将点集划分为数据量相对均衡的若干组,且各组的空间范围较合理。实验与分析表明,该算法具有较高的计算效率,也不需占用太多额外的存储空间。     

八叉树索引的三维点云数据压缩算法

针对现有的三维点云简化算法普遍存在运行效率较低、内存消耗大、处理时间过长等问题,该文利用八叉树索引的速度优势和点云数据空间分割的逻辑结构,并结合三维点云网格简化算法高效的优势,提出一种基于八叉树索引的三维点云简化算法。该算法基本满足点云简化的理想标准,计算快速、运行时间短。利用实测大雁塔数据对各种三维点云压缩算法进行比较,结果表明该文提出的新算法对点云数据的压缩简化效率和压缩率较现有算法均有较大提高。     

潜在连接点集下拓扑推进三维建模算法研究

通过三维激光扫描仪可以获取到表示空间对象的点云数据。通过设置仪器的采样间隔可以获取到表示对象不同精密程度的点集。但是由于离散点之间缺乏相应的拓扑关系,限制了以点为基本图元的模型的应用。以空间离散特征点集为研究对象,研究了一种三维建模算法。算法基于距离较近的点之间比距离较远的点之间存在拓扑连接的可能性更大的前提,对点集进行预处理,然后在此基础上进行快速建模,最终获取到以三角形为基本面片的格网模型。所建立的模型易于进行各项空间分析和操作。该算法也能够有效地应用于更为复杂的建模任务中,以达到一体化建模的目的。     

基于点集拓扑学的三维拓扑空间关系形式化描述

本文阐明了研究空间关系理论的必要性，分析了拓扑空间关系描述方法的研究进展及存在问题，以点集拓扑理论为基础，运用维数扩展的方法，提出三维拓扑空间关系完善和形式化的描述框架，在此基础上，对三维空间目标中存在着的拓扑空间关系进行了分类，定义了五种基本的拓扑空间关系，并且给出了三维拓扑空间关系最小集的互斥性与完备性证明。     

三维Voronoi图在三维方向关系计算中的应用

提出一种基于三维Voronoi图的三维方向关系计算方法。在分析二维方向关系的基础上,提出一种三维空间中的\     

一种基于立方体小栅格的K邻域快速搜索算法

提出了一种新的基于立方体小栅格的K邻域搜索算法。首先,采用二次划分的方法将点云划分到相应的立方体小栅格中;然后,为采样点所在的立方体小栅格确定最终子空间、内子空间和外子空间,结合采样点的球空间,就能很快确定该采样点的K邻域的搜索范围。与已有方法相比,该算法具有更高的搜索效率。     

利用空间微分块与动态球策略的k近邻搜索算法研究

提出了一种基于空间微分块与动态球判定策略的k近邻快速搜索算法。该算法以空间包围盒为基础,首先对空间进行微分块,将离散点分配到子空间;然后,以计算点为球心建立动态球,确定k近邻候选点。球半径可根据空间包围盒的大小、离散点数量和k近邻点数进行估算和优化。实验结果表明,该算法可快速完成k近邻搜索,运行稳定可靠。     

利用3D Voronoi图的兔子点云聚类分割

利用基于3D Voronoi多面体分割三维空间,并将其应用于具有典型三维特征的点云数据的聚类分割。通过对点云数据的离散体元表示,透过Voronoi单元的特征参数实现了三维点集的度量、提取和结构分析,揭示了点集间存在的相互关系,并通过3D Voronoi图所确定的空间邻近关系完成点集间相似度的测度和聚类。以三维兔子点云为样本数据的实验分析表明,本文所提出的思路聚类分割特征明显。     

空间体对象间三维拓扑构建研究

根据三维拓扑的研究现状以及特定应用领域对三维拓扑的需求,分析了这些特定应用领域的拓扑关系,提出了两种三维拓扑构建方法。这两种方法在兼顾内拓扑的同时主要构建体之间的外拓扑关系。第一种方法是在体单独构建完毕后建立体之间的拓扑关系;第二种方法考虑到当前成熟三维建模软件或CAD软件中的数据大多以离散面方式组织,设计了自动寻体算法,同时构建体之间的外拓扑关系。利用深圳典型地籍数据和建筑设计图生成的三维数据进行实验,验证了此算法的可行性。     

三维空间实体间拓扑关系的矩阵描述

三维空间实体及其间拓扑关系的语义描述和形式化表达是三维GIS空间数据建模的重要理论基础。在k-维流形的三维空间实体形式化描述方法的基础上,根据三维空间实体的可剖分性,采用顾及维数的九元组描述框架,研究用于构成三维实体的k-单纯形(0≤k≤3)之间的拓扑空间关系,继而研究三维实体间的拓扑空间关系。     

基于航空立体影像对的复杂房屋三维拓扑重建

对利用航空影像对重建复杂房屋三维模型进行了研究,提出了拓扑链、外拓扑和内拓扑的概念,分析了复杂房屋的内拓扑和外拓扑的三维重建,构造了复杂房屋的三维拓扑数据模型。基于此模型设计了双向搜索算法,用于自动构建复杂房屋的三维拓扑面,从而实现了复杂房屋的自动三维拓扑重建。实验证明,本文提出的双向搜索算法是很稳健、高效的。     

基于流形拓扑的三维空间实体形式化描述

阐述了三维空间实体语义概念及空间实体之间拓扑性质形式化描述的意义,以组合及点集拓扑理论为基础,给出了基于k-维伪流形的三维空间实体的语义定义。将单纯同调理论用于流形,通过单纯形和单纯复形间的几何构造关系,揭示出三维空间实体的拓扑性质并给出三维空间实体的形式化描述方法。