GIS中基于拓扑结构和凸壳技术的快速TIN生成算法

该文提出了一种针对散乱点集的快速生成TIN的算法.该算法首先对散乱点集按扫描线方式排序,然后利用凸壳技术,以排序后的点为着眼点,通过依次扫描各点快速地将有序点集进行三角联网,最后利用拓扑结构快速地将其优化为TIN.在三角网联结过程中由于充分利用了有序点子集的凸壳特性,避免了所有的交点测试,并且加入点联结合理三角形时的判断次数与原始点集的点数无关,只与点集的平面分布结构有关,从而保证了对海量散乱点集生成TIN的效率.该文还对算法进行了具体实现,并在实际项目中进行了成功的应用,证明了算法具有可操作性和较强的实用性.

基于一种曲率最小优化准则的散乱点三角剖分

从曲率入手 ,提出一种空间凸四边形的曲率估计算法 ,由此建立了一种新的基于该曲率的三角剖分优化准则以及曲面三角剖分算法 .该算法修改了部分常用的数据结构 ,使得算法有更好的空间复杂度 .通过分析 ,算法的时间复杂度为O(m2 ) ,同时还将这一优化准则与几种常用的优化准则作了扼要比较 .实验结果分析表明本算法具有保形特性 ,这在曲面重构和曲面设计等方面有很好的实用价值 .

一个通用的快速三角化算法

提出了一个适用于任意平面多边形区域及散乱点集的通用三角化算法 .当算法应用于多边形区域时 ,首先对各个顶点和区域内部的散乱点按扫描方式排序 ,然后依次扫描各点 ,扩展生成新的三角形 ,从而获得局部已剖分区域 ,并最终完成整个区域的三角化 .将上述过程作适当改动后 ,可被用于平面散乱点集的三角网格化 .该通用算法除了具有快速三角化的特点之外 ,还采用局部区域的优化组合来体现最优化准则 。

曲面激光密集测量三维数据的三角片逼近方法

本文对激光———机器视觉测量方式得到的曲面数据云为基础，探讨了曲面密集三维散乱点群数据的几何建模方法。根据激光测量方式和三维点群分布的特点，建立了恰当的数据结构在计算机中表示散乱点群。由八刃树空间分割原理对密集散乱点群进行空间分割，建立八叉树拓扑关系，显著加快了任意点的搜寻速度。采用万有引力定律计算三角片顶点坐标，由此实现散乱点群数据的几何建模。

基于SOFM神经网络的整体网格重构模型

提出了基于SOFM神经网络的大规模散乱点数据压缩方法,并建立了重构矩形拓扑整体网格和三角拓扑整体网格神经网络模型。

基于散乱点集空间划分的凸壳体快速生成算法

针对凸壳体特征的三维散乱点集数据,在空间划分结构的基础上进行K近邻搜索并估算点的法向量.引入点邻域的离差计算来代替曲率计算,提取边界区域特征点集,并比较分析了两种方法的效果.最后对提取后的剩余点集进行基于法向量的分块及拟合,并在可视化工具箱(VTK)中进行布尔运算,实现凸壳体模型的生成及可视化.该方法在双底双壳船舶液舱点集数据中进行了验证.

基于增量算法的三角剖分算法

增量算法是平面投影法中一种常用的点云剖分算法,该算法编程简单,占用内存少,计算速度较慢。针对增量算法的特点,改进算法通过将不同位置的点剖分对应存储到不同的边链表和三角形链表中,降低了边和三角形的搜索时间,提高了三角化的速度。同时,采用了加点剖分中同步优化和初步剖分后全体再次优化的优化方案,大大提高了剖分三角形的质量。实际点云剖分的结果显示,该算法不仅速度快、占用内存小,而且形成的三角表面质量高。

带约束折线的平面散点集Delaunay三角剖分

首先将原始散点与约束点一起进行三角剖分,形成初始Delaunay三角网,然后再将各条约束线段通过局部更新,依次嵌入已存在的三角网中,从而生成带有约束折线的平面散点集的Delaunay三角剖分。该算法思路简捷,易于编程,生成的三角网形态优良。

带内外边界约束的平面点集Delaunay三角剖分

算法首先将离散点与约束边界点一起进行Delaunay三角剖分,形成初始Delaunay三角网,然后将约束边界上的各条约束线段通过局部更新依次嵌入已有的三角网,最后再删除多余的三角形,从而得到带内外边界约束的平面点集Delaunay三角剖分.

互动优化的增量三角剖分算法

当前三角化文献中一般只介绍点云的三角化方法,几乎没有文献注意到点云三角化过程中与用户互动的过程,按用户的要求进行点云的三角化。本算法是一种增量算法,为了提高算法是实用性,算法将剖分信息按照点的不同位置存储到不同的对应边链表和三角形链表中,以降低边和三角形的搜索操作时间,提高三角化的速度;算法中采用了加点剖分中同步优化和初步剖分后用户随意多次优化的多重优化方案提高剖分三角形的质量,并且剖分中同步优化和用户再次优化分别采用最小角最大化优化准则和曲率最小优化准则,使剖分拟合表面更加光顺。通过点云剖分的实例结果显示,该算法具有速度极快、占用内存少、形成三角表面质量高,程序运行界面友好等优点。

平面散乱点线集三角剖分的算法

利用平面扫描的思想 ,即利用从右到左移动的 y 轴扫描点线集 当扫描线达到某个给定点或给定线段端点时 ,将该点或端点与其上下相邻线段端点连接 新连线与已三角剖分的边只能在其端点处相交 该算法的时间复杂性为O(NlogN) 。

八象限法三角化

空间点云的三角化是三维立体视觉领域中的研究热点,当前三角化文献中大多数只介绍空间部分点云的三角化方法,只有少量文献中介绍的空间闭合点云的三角化方法,但其算法较复杂而不太实用。本文通过将空间闭合点云划分成多个相当的部分点云进行平面三角化,然后再将分割的部分点云进行缝合,而最终形成对整体空间闭合点云的完整三角化。实验表明该算法简单,速度快,三角化的质量高。

基于法向量场的散乱点集三角网格化

文章提出了基于散乱空间点集进行曲面重建的新方法,即从散乱点集的空间位置信息中估算出待建曲面的法向量场,构造基于法向量的曲面重建控制方法和控制参数,并用该参数来确定拓扑重建的搜索空间,采用面片生长的方式重建曲面。该方法在快速获得正确的拓扑连接的同时,直接生成用较少的面片就能保持曲面特征的优化网格。

曲面拼接与扩展的三角剖分算法的改进

对递归分割曲面在编辑方面的拼接和平面扩展问题的散乱点的三角剖分算法进行了研究。通过边界轨迹优先生成和点的有效性判断等约束条件对原有剖分算法进行了改进,顺利实现了递归分割曲面的拼接和平面扩展,并保证了拼接边界和扩展边界网格拓扑的正确性。

3D散乱数据点分段二次逼近的曲面拟合

为进一步提高曲面重构的保形性及高效性,提出了一种自动构建光顺三角曲面的方法.该法首先通过构建三角形元覆盖边界域来构建一张曲面近似粗网,然后从点集中不断添加新点直至达到指定的容差,在每个插入数据点处构造C1连续的分片二次逼近面片,最终整体的C1曲面由各三角形上的曲面片拼合而成.最后给出了该方法在真实点集上的运用结果并与其他方法所构造的逼近曲面形状进行了比较,结果表明,该方法对密集3D散乱数据点建模有效,生成的曲面质量高,误差小.该方法也适用于数据精简.

基于平行截面的三维散乱点物体表面重构

三维物体的散乱点构型技术是近几年计算机视觉领域中的热点问题,它在众多行业有着广泛的应用前景。该文提出了一种新的能够适用于大多数物体的构型方法,并且计算量也相应地得到了控制。

一种通用的三维散乱数据点图形重建算法

通过三维扫描仪可以获得物体表面的三维散乱数据点集 ,如何通过图形重建算法来对散乱数据点集进行重建 ,在许多系统中是一个重要的步骤 ,并在许多行业有广泛的应用前景。文章提出了一种新的通用的三维散乱数据点重建算法 ,它是基于轮廓线的构型方法 ,该方法不仅能够适用于凸形物体的构型 。

一种新的散乱点云特征提取方法研究

结合显著特征点与马尔科夫随机场的特性,提出一种新的散乱点云特征提取算法研究.首先构造点云的显著度函数,计算点云模型中散乱点的显著度;然后根据点的显著度及点间测地距构造Reeb图,由Reeb图及判断Reeb图显著点的两个条件提取显著特征点;接着根据点到显著特征点及中心点的距离计算马尔科夫随机场的联合密度函数,通过贝叶斯估计求最大后验概率分布函数,采用马尔科夫最大后验概率框架归约简化得到最优标号的目标函数;最后采用图割法求解目标函数,依赖全局能量变化调整标号集,得到点云的最优标号集,并根据最优标号集与点集间对应关系提取特征点.实验结果表明:该算法能够有效的检测出散乱点云的特征点,改善了算法的时间性能;其中,算法根据随机场的全局能量变化调整标号,得出最优标号集,避免了传统方法人工调参的问题.

基于散乱点集的规则格网构建方法

数字高程模型(DEM)是地理信息系统(GIS)重要的空间地理信息,是地理信息系统(GIS)进行地形分析的核心数据。模型构建方法的选择是数字高程模型的核心问题,它直接影响数字高程模型的质量,贯穿于数字高程模型生产制作的全过程。数字高程模型有三种数据结构形式:规则格网数据结构、不规则三角网结构和等高线结构。在通常的使用中,规则格网形式的数字高程模型是使用最为广泛的一种,也是建立最为容易的。为此,本文着重对规则格网的构建方法中的内插方法进行了探讨。

由三维散乱点重建三角网格曲面方法的分类与评价

介绍了三维散乱点重建网格曲面的有关知识及发展现状，对现有的由三维散乱点重建三角网格曲面的典型算法分为三大类型，对这三类算法的特点加以深入地分析和比较，指出了各个算法的适用范围．最后分析了由散乱点生成三角网格曲面中需要进一步研究和解决的问题．