初始凸包对改进快速凸包算法效率的影响

针对目前众多采用了改进的快速凸包算法对给定的平面海量离散点集生成凸包的文献中,没有明确指出其初始凸包的形式(四边形或八边形)对算法效率的影响的问题,该文对凸包的生成过程进行了深入分析,并进行了大量的实验。通过比较这些实验的结果,发现以四边形或八边形作为初始凸包均能有效地提高算法效率,但在相同的条件下,以八边形作为初始凸包时,并不能将算法效率进一步提高,与以四边形作为初始凸包相比,其实际的执行效率不升反降。实验结果表明以四边形作为初始凸包时算法效率最佳。     

坐标排序的离散点凸包生成算法

针对传统的凸包生成方法在数据量较大情况下效率下降明显的问题,该文提出了一种基于平面离散点快速生成凸包算法。基于凸包边界单调性对平面点集分区域按X轴方向排序的方法,较好地减少了传统凸包生成算法的计算量,实现了凸包求取的高效性。实验结果表明:该算法不仅可以快速有效地生成凸包,还能够保证结果的准确性,且效率较高。     

基于二叉树的散乱点集快速凸包算法

在右壳树和左壳树概念的基础上,提出了基于二叉树的散乱点集快速凸包算法,它在查找每一个凸包顶点的同时,通过去除若干非凸包顶点来迅速、动态地减小散点集的规模,通常情况下能达到线性时间复杂度。算法省却了凸包顶点间连接关系的判断过程,适用于任何复杂的散点分布情况,并且简单,易于实现。     

基于改进凸包算法的树冠轮廓点提取与体积计算

针对城市中树木数量多、树冠结构复杂、形态多变、难以测量等特点,为解决传统凸包算法在提取树冠轮廓时误差较大的问题,并实现树冠轮廓点提取和树冠体积自动计算,提出迭代渐进的凸包算法。以三维激光扫描仪获取的点云为原始数据,基于所提出的算法获取树冠轮廓点,结合格林公式及不规则台体体积法计算树冠体积。为验证算法的准确性,采用人工交互的方式提取树冠外轮廓点计算树冠体积,以此为参照对迭代渐进的凸包算法进行相关性与均方根误差的验证,并将该算法分别与几何体模型法、体元模拟法、Graham扫描线法计算的树冠体积进行对比分析,结果表明,迭代渐进的凸包算法计算出的树冠体积更接近于树冠的真实体积,为树冠信息的精细提取与建模提供一种新的方法。     

一种用于建筑物立面边界特征点提取的凸包三角网算法

基于现存凸包算法较难提取建筑物立面点云中的边界特征点等问题,提出一种构建凸包三角网的建筑物立面边界特征点提取算法。首先利用k近邻搜索算法查找每个点的近邻点,并通过主成分分析方法估算各点的法向量。然后将各点的近邻点投影到局部拟合平面,使用罗德里格法进行旋转获得二维投影点。最后利用凸包算法在求解边界特征点的基础上构建凸包三角网,并获得各三角形中近邻点占地率并统计各三角形的顶角值,得到剩余边界特征点。采用模拟和实测点云数据进行试验,并与改进的凸包算法和基于点的算法进行对比,结果表明,该算法能够提高建筑立面边界特征点提取的准确性和完整性,具有较强的适用性。     

平面点集凸包Graham算法的改进

本文提出了一种计算平面点集最小凸包的快速算法。该算法首先对平面点集进行扫描,查找到最左、最右、最上、最下4个方向上的极值点,以此构造出一个初始凸包,并删除初始凸包内部的所有点;然后把剩余点集分组,每组运用格雷厄姆(Graham)算法生成一个新的凸包;最后将所有子集凸包的顶点看作一个新的点集,再次运用Graham算法生成最终凸包。测试结果表明,改进后的算法可较大幅度地提高执行效率。     

GIS中点集凸包的快速算法

对文献[1]的划分算法的时间复杂度进行理论分析,指出它的不适用范围.提出了一种计算凸包的O(n)的算法.     

离散点集Delaunay三角网生成算法改进与软件开发

改进了三角形生长算法，在原算法的基础上，用均匀格网来划分离散点集，建立点集的栅格索引,快速生成初始三角形，再进行扩展；引进了封闭点的概念，在扩展过程中动态删除封闭点，加快了查找点的搜索过程；软件开发中采用VC的MPC类Carry和CList来管理数据，创建了CBuildtin和Craster两个类来生成三角网和栅格索引，提高了程序的可移植性。     

基于Fuller投影的六边形球面离散格网生成算法

随着云计算、航天遥感、地理信息、导航等技术的发展,用于空间信息剖分组织的全球多分辨率离散格网模型得到了长足发展。针对已有研究成果和当前研究现状,选取性能优异的六边形作为基本格网单元,Fuller多面体投影作为投影类型,提出了一种基于正八面体构建新型六边形球面离散格网的方法。全文系统地论述了此新型离散格网的生成算法并给出了相应实验结果,最后与基于Snyder等积多面体投影的格网进行比较,得出其特点和应用前景。     

点到平面距离的点云数据压缩方法

针对三维激光扫描点云数据采集过密、冗余信息较多,现有压缩算法存在不足的问题,该文提出了基于点到平面距离的散乱点云压缩算法。将该算法与基于三角形法向量夹角和格网法两种现有算法的压缩结果进行比较,通过对比构建的空间三角网可以发现,该文算法对物体特征复杂的部位有较好的压缩效果,且在压缩率较高时,不会使较平缓的部位出现过度压缩而失真的情况。     

一种基于凸包的Delaunay三角网算法设计

Delaunay三角网算法的设计与研究对DTM的建立有着重要的作用,本文在分析已有三角网算法的基础上,根据逐点插入算法的思想与凸包算法相结合,提出了自己的算法:先绘制凸包,然后构建初始三角网,最后用LOP方法整体优化。该算法尽可能的减少了对一条边的优化次数,从而提高了算法的运行效率。     

再论三维Douglas-Peucker算法及其在DEM综合中的应用

相对于笔者在已发表论文中所提出的一般性方法,本文在算法上有了进一步的改善或扩展。结果表明,这些措施在保证综合效果的前提下,可以大大提高DEM的综合速度,从而为海量DEM数据的全局动态式综合提供了现实的可能性。     

一种栅格辅助的平面点集最小凸包生成算法

针对平面点集的最小凸包生成问题,提出一种栅格辅助的算法,预先剔除那些不可能成为凸包顶点的点,从而提高算法效率,算法的时间复杂度可近似达到O(n),最坏时间复杂度与Graham扫描算法相同。试验表明,随着行列数的增加,计算效率先快速递增,随后逐渐减小;当栅格行列数取值为总点数的平方根时,剔除比接近最大值,算法执行效率亦相对较高。     

三维点集的自动表面重构算法

提出了一种基于透视约束利用离散三维空间点重建三维表面模型的方法,该方法充分利用摄影测量 以及激光扫描等三维测量技术中隐含的透视关系,将离散点划分到不同的投影面,在局部利用二维三角网构 网技术构建三角网,然后在考虑局部三角网边缘一致性的基础上组合成整体三维表面模型。该方法可以利用 近景摄影测量处理产生的三维景物点或激光扫描仪采集的三维空间点自动构造三维表面模型,重建物体三 维表面。实验结果表明,该算法是有效的。     

基于边长比约束的离散点准确边界追踪算法

提出了一种基于三角形边长比约束的离散点边界追踪算法,实现了对带洞凹多边形边界的有效追踪。通过边长比作为限制条件,有效地降低了边界追踪算法中阈值对点密度的依赖,并通过实验验证了本文所提算法的实用性。     

基于物体表面散乱三维激光扫描点的三角形格网建立

针对物体表面的散乱三维激光扫描点数据,提出了借助柱面坐标系统将三维激光扫描点转换为三角形格网构造系坐标,并根据转换后的坐标利用在平面内计算狄罗里三角形的方法建立三维物体表面格网模型.建立格网模型的效果表明,借助柱面坐标系统构造狄罗里三角形的方法可以作为三维物体表面三角形格网模型的一个重要的基本方法.     

全球六边形离散格网数据的三维可视化方法

针对全球六边形离散格网的三维显示化方法开展研究,设计了一种六边形格网的空间层次结构(hexagonalquaternary balanced structure,HQBS),采用四位码元对格网单元进行编码,定义并实现了格网向量的基本运算,利用这些运算可以方便地实现格网单元的空间索引。在此基础上还研究了全球离散格网的动态生成与显示算法、可视化区域裁剪等相关内容。试验表明:全球格网动态生成的效率110～370单元/ms之间,加载空间数据后,格网数据和空间数据逐层加载的时间在300 ms左右,能够保证加载空间数据后的显示刷新率在20帧/s左右。     

基于菱形块的全球离散格网欧拉数计算

对全球离散格网的研究已成为目前国际GIS界的研究热点,其中欧拉数是讨论球面栅格区域局部拓扑不变量的重要参数,也是描述和推断球面栅格拓扑关系首先要解决的问题。本文以菱形块作为全球离散格网的数据组织单元,在利用线性四叉树Morton编码作为地址码对菱形块进行邻近搜索的基础上,在对菱形块进行剖分的同时,对其子菱形块进行行列号的剖分,然后利用菱形块行列号进行邻近搜索,最后利用邻近搜索的结果计算出全球离散格网的栅格区域进行欧拉数。最后,本文在C++和DirecX环境下验证了该算法的有效性和正确性。     

基于格网索引的点目标捕捉算法

传统的从离散点中捕捉其中一点的算法实现存在精确度低、重复计算耗时、难度大的不足,从而增加了捕捉的计算量而影响性能。本文介绍了一种基于格网索引的点目标捕捉算法,通过对点群的格网划分,行列号的计算与Morton码的获得,建立空间索引表、实体索引表与点目标的存储单链表,成功完成点目标的捕捉。     

基于LiDAR点云数据的树冠空隙度指数分析

分形维数法是分析空间结构分布的一种典型方法,但它对于区分不同的分布形式还存在缺陷。针对这一问题,该文介绍了空隙度指数的定义和树冠空隙度的计算方法;以模拟的树冠点云数据为对象,提出了一种基于三维凸包和三维滑动盒算法的激光雷达(Li DAR)点云数据空隙度分析方法,详尽分析了不同冠型产生的空隙度指数差异;并利用4棵实测的树冠点云数据做检验;最后阐述了空隙度指数在树冠空间异质性分析研究中的作用,并对其应用范围和前景作了展望。结果表明:划分尺度相同时,在一定的尺度范围内,锥型树冠、半球型和半椭球型树冠的差别可以通过空隙度指数曲线有效地区分,实测树冠的结果也体现了空隙度指数对于判断树冠空间结构的有效性。