基于三角形法向量的离散点三维构网方法

构建平面不规则三角网的算法已经很成熟,但普遍的算法都是基于某一投影平面,不能满足三维空间离散点的构网要求.本文在研究二维构网生长算法及现有空间三维构网方法的基础上,提出利用空间三角形的法向量实现三维构网,详细讨论该算法的细节问题,并探讨提高构网速度的方法.通过实验证明该算法能快速、有效、稳定地对复杂物体表面离散点构建空间三角网,达到建模效果,同时也体现出其应用范围的广阔性.     

结合二叉树和Graham扫描技术的高效Delaunay三角网构建算法*

为了提高不规则三角网的构建速度,提出了一种高效构建Delaunay三角网算法。首先对平面上的离散点集按一定的阈值进行分块,建立子块索引二叉树,然后利用Graham扫描技术对各子块构建Delaunay三角网,最后自底向上合并具有相同父节点的子块。通过具体实验与其他构网算法比较,该算法在构网速度上具有明显的优越性。     

三维DTM构建算法改进与实现

逐点插入法是一种依次插入数据点来进行三角剖分的方法,此方法可以用于实现平面或三维域上离散数据点的Delaunay三角网的构建.在原算法的基础上提出改进.通过对离散数据点集在XOY二维平面上的排序使之有序化以及对三角形进行分类的方法提高生成delaunay三角网构网速度,并运用到三维DTM的构建实现中.通过程序运行测试显示,随着点数的增加速度增长的幅度也增加,这对于需要大点数DTM的构建有着很好的应用价值.     

约束数据域的Delaunay三角剖分算法研究及应用

研究了一种约束Delaunay三角网生成算法,它充分利用分治算法与生长算法的优点,对离散点、构网中实时生成的边及三角形采用分块进行网格索引,有效地减少了搜索目标点、边及三角形的时间,从而提高了构网速度,并将该算法用于地面模型的构建中,实现了地形三维可视化。     

一种基于插入法的Delaunay三角网生成算法

文章讨论了建立离散点Delaunay三角剖分算法的研究现状,针对＂逐点插入法＂采用网格分块的方法对构网离散点集和已生成的三角网建立索引,提高了点在三角网中的定位效率和三角网的生成效率。     

基于等高线的三角网建模及真实感地形重建

三维地形是自然环境模拟中不可缺少的重要组成部分,具有广泛的应用价值.文中提出了一种基于等高线的三角网建模算法.该算法利用等高线固有的特性及其比邻拓扑关系,将等高线作为特征线并适当增加特征点,改进三角网生长算法,构建带约束条件的狄洛尼三角网.实验采用我国东北某山区的真实等高线数据运用该算法模拟地形.结果表明,该算法具有较高的构网效率,保留了等高线所包含的丰富的地形特征,较好地实现了三维真实感地形重建.     

Delaunay三角网高效构建及地形仿真应用

针对基于离散点的Delaunay三角网构建过程中待插入点的定位耗时问题,提出Delaunay三角网高效构建算法,并将其用于三维地形仿真应用中。对大量数据点进行分块排序预处理后,运用空间自相关理论使下一个待插入点总是紧邻新近插入点,融合最短路径定位算法和三角形面积法,结合三角形重心与点、有向线段的关系遍历三角形,减少遍历时间。在对三角网进行LOP局部优化时,采用Delaunay四叉树保存待调整的所有边的节点信息,提高遍历效率。实验结果证明,该算法构建的三维地表真实感较强,并且具有较低的时间复杂度。     

改进的平面域Delaunay三角网生成算法

讨论了离散点建立Delaunay三角网算法的研究现状,并采用网格划分提高构网速度。由于三角形定位的速度是影响构网速度的关键因素,改进了基于点线关系方向定位算法,充分利用点与三角形的拓扑关系,减少点线关系的方向定位算法中计算重心的次数,从而提高了三角形定位的效率和构网速度。通过测试证明了算法的高效型和稳定性。     

基于不规则三角网构建的网格生长算法

提出一种基于离散点Delaunay三角网快速构建的网格生长算法,采用分治算法将离散点表达为唯一网格,利用稀疏矩阵完成网格数据的压缩存储,通过标识码实现有值单元格与离散点之间的高效检索,从而提高网格构建的效率。依据有值单元格的密度获取预设正方形搜索空间,并在三角网扩展时根据需要动态建立正方形搜索空间,从而保证网格生长的准确性。实验结果表明,该算法的时间复杂度为O(nlogn),对于少量或海量离散点均具有较好的适应性。     

基于LiDAR点云数据的三角网构建算法

在现有Delaunay三角网生长法的基础上进行改进,提出了一种三角网生长算法.该算法对大规模点云进行等格网分块,自适应确定搜索范围.通过在构建过程中对生成的基线进行分组和排序,动态删除封闭点,提高了构建三角网的速度;通过在整个点集范围内进行搜索,避免了通过插值所产生的误差和模块之间的拼接过程.利用此算法对大规模LiDAR点云数据进行构网,结果表明了该算法的有效性.     

建立多精度三角网

多精度三角网可用于数据压缩及进行不同细节程度的２．５维分析处理,现有建立多精度三角网的算法功能单一,不能满足随时改变精度的要求。该文给出了一套完整的建立多精度的三角网的算法,包括建立基本三角网,在三角网中增加点和删除点等。并且实现了两个运行版本,一个可建立指定精度的三角网,另一个可在运行中     

无线传感网络中基于共面度的三维定位算法研究与设计

无线传感器网络中的节点定位技术是其得到广泛应用的关键支撑技术之一.尽管对定位技术已经有很多研究,但面向三维定位的研究较少并至今尚没有推出有效的定位算法.研究分析了现有的二维定位算法和个别依赖额外硬件三维定位算法后,提出基于共面度的三维定位算法.该算法通过分析参考点拓扑结构对定位造成的影响,在研究四面体的数学理论基础上提...     

结合体元数据结构的机载LIDAR建筑物检测

目的 目前,点云、栅格格网及不规则三角网等建筑物检测中常用的离散机载激光雷达（LIDAR）点云数据表达方式存在模型表达复杂、算法开发困难、结果表达不准确及难以表达多返回数据等缺点。为此,针对LIDAR点云体元结构模型构建及在此基础上的建筑物检测展开研究,提出一种基于体元的建筑物检测算法。方法 首先将点云数据规则化为二值（即1、0值,分别表示体元中是否包含有激光点）3D体元结构。然后利用3D滤波算法将上述体元结构中表征数据点的体元分类为地面和非地面体元。最后,依据建筑物边缘的接近直线、跳变特性从非地面体元中搜寻建筑物边缘作为种子体元进而标记与其3D连通的非地面体元集合为建筑物体元。结果 实验基于ISPRS（international society for photogrammetry and remote sensing）提供的包含了不同的建筑物类型的城区LIDAR点云数据测试了"邻域尺度"参数的敏感性及提出算法的精度。定量评价的结果表明：56邻域为最佳邻域尺度;建筑物的检测质量可达到95%以上——平均完整度可达到95.61%、平均正确率可达95.97%。定性评价的结果表明：对大型、密集、不规则形状、高低混合及其他屋顶类型比较特殊的复杂建筑物均可成功检测。结论 本文提出的建筑物检测算法采用基于体元空间邻域关系的搜索标记方式,可有效实现对各类建筑目标特别是城市建筑目标的检测,检测结果易于建模3D建筑物模型。     

三维不规则三角网格的精确裁剪算法

给出了一种基于约束Delaunay三角剖分的三维不规则三角网格的精确裁剪算法。算法结合TIN数据的生成特点,首先将TIN投影到二维平面,然后利用约束Delaunay三角剖分把裁剪多边形的每条边嵌入三角网中,再利用边-三角形的拓扑关系删除裁剪多边形外部多余三角形,最后利用边-点的拓扑关系对裁剪多边形顶点高程进行插值,使生成裁剪后的TIN模型。对不同复杂程度的三维TIN模型进行裁剪实验,发现二维投影策略极大地提高了三维TIN裁剪效率。算法的程序实现简单,且符合工程需求。     

利用灰度体元模型的机载LiDAR 3D道路提取

面向机载LiDAR数据的道路提取算法的常用数据结构存在局限: 2D格网及TIN表达多次回波数据时存在的信息损失会影响提取结果的完整性且提取结果为2D形式; 点云的空间结构及拓扑信息难以利用, 由此导致算法设计的困难.为此, 提出了一种基于灰度体元模型的3D道路提取算法.算法首先将LiDAR数据规则化为灰度体元模型(灰度为体元内LiDAR点的平均强度值的量化表示); 然后选取道路种子体元进而搜寻并标记种子及其3D连通区域为道路体元; 最后利用数学形态学优化提取结果.基于ISPRS提供的包含不同复杂程度的城区路网LiDAR数据测试"邻域尺度"和"灰度差阈值"参数的敏感性及提出的算法的精度.实验结果表明: 56邻域为最佳邻域尺度、2为最佳灰度差阈值; 道路提取的平均质量、完整度及正确率分别为70%、86.77%及81.13%;对相对平坦的单层路网及起伏较大的复杂路网均可成功提取.     

一种改进的高效Delaunay三角网的生成算法

Delaunay三角网在GIS／VR中具有很广泛的用途，而分而治之算法和逐点插入法是目前普遍用于生成Delaunay三角网的两种算法。本在研究了基于这两种算法的合成算法后，对其进行了修改和优化，形成了高效合成算法。高效合成算法中提出了通过确定点线关系来解决点的定位问题，优化了其LOP的算法，提高了算法的稳定性，使其执行效率得到很明显地提高，本算法的设计思想还可推广到三维空间。     

基于均匀圆阵的闭环式单基站测向算法研究

为了估算基于均匀圆阵列(UCA)的三维(3D)单基站测向(方位角、仰角和区间),提出了一种改进的适用于三维场景的闭环式算法。该算法是一种计算过程较简单的通用算法,无需使用均匀圆阵列的中心对称性,没有任何传感器数量的限制,只需要一个单独的最小平方程序用于估算基站的位置,并可以估算所有的三维测向参数。实验结果表明,相比多种类似算法,所提算法的性能可与三维MUSIC算法的性能相媲美,且计算复杂度更低,实现速度更快。     

一种高效的Delaunay三角网合并生成技术

在传统的建模方法中，规则三角网方法（GRID）由于是在格网点上对格网周围采样点按照距离远近加权平均，难以在细节上反映原貌，精度不高；不规则三角网方法（TN）按照某种原则（delaunay)将采样点直接民网，建立起模型，但是建模过程复杂，内存耗费很大，当原始采样数据量很大时，效率很低，引进四叉树分块生成标准delaunay网格，并采用凸壳边界跟踪优化合并形成三角网格，大大提高delaunay三角网生成速度，提高了建模效率。     

TIN generation and point-cloud compression for vehicle-based mobile mapping systems

The vehicle-based mobile mapping system (MMS) is effective for capturing dense 3D data of roads, roadside objects and buildings. Since discrete points are not convenient for many application systems, a triangulated irregular network (TIN) is often generated from point-clouds. However, TIN data require two or three times larger storage than point-clouds. If TIN models can be promptly generated while loading point-clouds, it would not be necessary to store huge TIN models on a hard disk. In this paper, we propose two efficient TIN generation methods according to types of laser scanners. One is the line-by-line TIN generation method, and the other is the GPS-time based method. These methods can quickly generate TIN models based on scan lines of laser scanners. In addition, we introduce a new compression method to reduce the loading time of point-clouds. Our compression method is also based on the scan lines of laser scanners. Since points captured by a MMS tend to be positioned on nearly straight lines, their data size can be significantly reduced by coding the second order differences.