作战模拟中基于不规则三角网的路径规划研究

针对分队级作战模拟的路径规划问题,该文采用了一种基于不规则三角网的路径规划方法,通过将作战地图上的面状区域进行三角网剖分,区分地貌、地物设置三角面的属性,以描述不同三角网之间的可通行性,并在此基础上利用A*算法寻路,可以快速实现路径规划。非路网的路径规划将使作战模拟中实体的行为更加逼真,达到了野战环境下运动规划的目的。

基于三角网算法的公路纵断面设计及实例验证

当前公路纵断面设计结果与真实施工环境数据拟合度较差,应用效果不佳。为此,提出基于三角网算法的公路纵断面设计方法,并通过实例验证此方法应用效果。首先,根据车辆行驶参数统计分析结果,确定公路基础设计参数;其次,构建基础三维模型,将该模型与研究区域的基础三角网图合并,得到三角网计算模型;最后,应用模型计算结果,完成公路纵断面设计方案,确定关键设计参数。实验结果表明:基于三角网算法的公路纵断面设计结果与真实施工环境数据拟合度更高。

基于渐进三角网的多波束滤波算法研究

多波束测深过程中,由于受到各种要素干扰,数据会生成大量异常值。异常值(通常称为噪声)剔除是多波束数据处理过程中的关键。当前常用的趋势面滤波算法主要是建立水下地形的曲面,对于噪声点与所建立曲面对比完成多波束噪声的过滤。针对多波束噪声剔除问题,提出了渐进三角网加密(progressive TIN densification algorithm,简称PTD)算法,选取最低水深点。利用Grubbs算法选取最低水深点,通过Delaunay三角剖分建立三角网构筑海底模型,利用三角网边长、角度与距离作为判断阈值,分离噪声点与水深点。以温州海域航道水深测量为例,与Caris软件中CUBE算法处理结果以及传统趋势面算法进行对比,验证渐进三角网加密算法的实用性和优缺点。

高效构建Delaunay三角网数字地形模型算法研究

在对传统构建Delaunay三角剖分 (尤其是分割 合并 )算法进行分析的基础上 ,采用自适应格网划分方法对点集进行排序、分割 ,并按照逆序合并Delaunay子三角网 ,然后进行约束处理 ,快速、高效地实现了Delaunay三角网的构建 ;对Delaunay子三角网合并、地性线处理、平三角形处理等关键问题进行了描述。实测结果表明 ,该算法的时间复杂度接近于O(n)。

Delaunay三角网的生成算法研究

Ｄｅｌａｕｎａｙ三角网作为一种主要的ＤＴＭ表示法，具有极其广泛的用途。经过二十多年来的研究，它的生成算法已趋于成熟。本文简要介绍了Ｄｅｌａｕｎａｙ三角网的定义及其特性，在简单回顾和评价了分割－归并法，逐点插入法，三角网生长法等三类主流算法的基础上，提出了一个融以上算法优点于一体，兼顾空间与时间性能的合成算法。经测试，一般情况下它的运算速度远快于逐点插入法，与分割－归并法相当，较好的情况下快于分割－归并法。

一种基于三角网扩张法的Delaunay三角网逐块归并算法

本文中提出一种基于三角网扩张法的不规则三角网的逐块归并算法,它采用按横向或纵向对离散点集切割分块,对各子块用三角网扩张法构建Delaunay三角网,最后用三角网扩张法依次将相邻的子网合并。该算法采用的子集分块的做法使构网时的搜索范围减小,在数据量较大时避免了计算时间随点数的指数次增加,同时在构网时也能保证三角形邻接关系的正确维护。

快速构建三角网数字地形模型方法的研究

改进和优化了逐点插入算法 ,通过建立网格索引 ,实现了DTM数据的高效组织和管理 ,再结合有向查找技术 ,研究出了三角形的快速定位算法。采用Watson的空外接圆法优化构网 ,为减少优化时间 ,提出了按网格轮流取点的策略。在地性线的处理上 ,采用了先构建初级Delaunay三角网 ,再将地性线做为约束边嵌入初级网中的二级建网方案。经实践验证 ,该算法具有速度快、网形优、精度高。

基于Delaunay三角网的等值线绘制算法

提出了一种快速构建Delaunay三角网算法(QGDTN)。在每次迭代中,该算法从点集P最左边的两点中,选取离凸边中点距离最近的一点与凸边构成Delaunay三角形,并加入三角网中,算法实现简单,且时间复杂度为O(n)。基于Delaunay三角网,根据三角形的各边上是否有等值点,用内插值法求出等值点坐标,跟踪、连接等值点生成等值线;最后,采用三次方Bezier曲线平滑等值线。实验证明,基于Delaunay三角网的等值线绘制算法是高效的,并且具有一定的实用价值。

一种生成Delaunay三角网的合成算法

经过２０ 多年的研究，自动生成Ｄｅｌａｕｎａｙ 三角网的算法已趋于成熟。它们基本上可分为分治算法、逐点插入法、三角网生长法等３ 类。其中前两类较第３ 类在应用上更加广泛。但即使这两类算法也分别存在着时间和空间效率上的缺陷，使它们的应用受到了一定的限制。提出了一个融以上两类算法优点于一体，兼顾空间与时间性能的合成算法。经测试，它的运算效率大大高于逐点插入法，在大多数情况下，也高于分治算法，在分割阈值约为总数据量的十分之一时，效率最高。

四叉树高效Delaunay三角网生成算法

实现了一种以地形为应用背景的大规模离散点快速生成TIN的算法,该算法首先对大规模离散点按一定的阈值进行四叉树分割,然后对四叉树的每个叶子块分别以凸壳技术构三角网,而后再自底向上合并具有相同父亲节点的块,最后进行全局优化,生成Delaunay三角网。经实际地形数据验证结果表明:同样的算法,采用四叉树分块比采用平均分块策略有着更高的执行效率。

快速构建Delaunay三角网算法研究

研究一种快速构建 Delaunay三角网的算法 ,该算法结合逐点插入算法和分治算法 ,具有建网速度快、耗费空间小的优点。采用多级自适应网格划分点集 ,对叶子网格内的点采用改进了的逐点插入算法生成子三角网 ,子三角网间利用分治算法的思想进行合并。经实践验证 ,算法复杂度与点数几乎成线性关系。

一种非凸包边界约束不规则三角网生成算法

数字高程模型(DEM)模拟的大多数地形区域是多种类型区域镶嵌而成的复合体,且子区域的边界一般为非凸多边形,即三角网受到边界的约束。而目前已有的各种Delaunay三角网构网算法生成的不规则三角网的边界都是区域内采样点集的凸包,不能表达复合区域和边界为非凸多边形的区域。本文作者对三角网扩张法作了扩展,使之能够在任意多边形所包围的区域内生成不规则三角网。扩展后的算法具有步骤简单、适合任意多边形边界内生成不规则三角网的优点,而且该算法可用于"分块"式生成数据量较大的三角网,同时保证各"分块"之间完整的邻接关系。

基于不规则三角网的河网提取算法

本文提出了一种基于不规则三角网(Triangulated Irregular Network,TIN)的河网水系提取算法。讨论了河网水系的结构模式,包括河网水系的组织结构、层次结构和拓扑结构,并给出了河网水系描述的拓扑数据结构。在分析TIN中三角形各边的汇流特性基础上,依据矢量代数理论,讨论了三角形各边和水流方向的关系,并给出了各边汇流特性的判断准则。基于上述理论,设计了TIN的河网水系提取算法,并通过实例进行了分析验证。

一种基于三角网的等值线自动填充算法

等值线填充就是先在等值线间建立拓扑关系,然后基于拓扑关系来完成等值线的填充,这一直是一个比较困难的问题。为了快速方便地进行等值线自动填充,提出了一种基于不规则三角网的等值线自动填充算法。该算法把采用不规则三角网生成的非闭合等值线,先根据一定关系与自定义边界连接成闭合等值线,然后通过确定各闭合等值线之间的包含关系和各等值线之间的填充颜色来绘制出等值线填充图。实践表明,该算法易于实现,且运算速度能满足业务需求。

地形建模中不规则三角网构建的优化算法研究

对利用数字线划图(DLG)重建地形三维模型进行了研究,提出了基于三角形拓扑关系的自动联结三角网算法,并构造了复杂地形的三维数据模型。基于此模型,设计实现了构网优化算法,实现了复杂地形的自动三维重建。试验证明,本文提出的构网优化算法是稳健、高效的。

缓冲曲线和边约束三角网辅助的缓冲区生成算法

本文在分析了已有的缓冲区生成算法后，提出缓冲曲线和边约束三角网辅助的矢量缓冲区生成算法。算法分两步，第一步生成作者提出的缓冲曲线，第二步将缓冲曲线切割组合为缓冲区。算法通过缓冲曲线，在理论上减少了参与切割重组的线段数目，将不可能成为缓冲区边界的线段在一开始就剔除；在第二步中，算法通过边约束三角网和环绕系数的传递将线段切割重组的过程优化，不相交的线段之间免去比较判断，从而为生成缓冲区提供一个快速完整的方案。

改进的三角网构网算法用于LiDAR树冠体积提取（英文）

在分析现存点云处理方法的特性后,通过改进三角网构网算法的算法机制,提出了一种基于空间分割的分块优先级机制的三角网表面重建算法,用于重构树冠表面,实现树冠体积的准确提取.通过可视化方法对比了多种算法的点云构网效果,以实验区选定的30棵树为研究对象,利用T-LiDAR获取树冠点云数据,通过人工方法、传统算法和本文的改进算法计算树冠体积,对这些结果进行了对比分析.分析发现:四种方法之间均显示出较好的相关性(R2>=0.831),其中所提出的改进Delaunay方法拥有理想的精度,较好稳定性和最少的耗费时间.实验结果表明,提出的算法在点云(尤其是T-LiDAR数据)树冠的体积提取中具有很大的优势.结合T-LiDAR数据还可以实现树冠表面积和生物量等树冠因子的高精度快速提取.

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

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

三角网数字地面模型的生成及其在路线设计中的应用

论述了一种形成离散点三角形格网 (TIN)数字地面模型的方法 ,在生成初始三角形后 ,采用队列及平衡二叉树等数据结构进行三角网的扩展 ,通过点集分块改进点的搜索方法 ,减少了搜索时间 ,并用 L OP算法优化网形。用这种方法生成的带状数字地面模型已成功地应用于铁路和公路的勘测设计中。

多核处理器的机载激光雷达点云并行三角网渐进加密滤波方法

滤波是机载LiDAR点云数据处理的关键步骤之一,点云数据的海量化特性使得一般的串行化滤波处理方法无法满足快速成图的应用需求。提出一种基于多核计算技术的并行三角网渐进加密滤波方法,将串行方法中最耗时的三角网构建与脚点判别过程进行了并行化改造。三角网构建算法的并行化基于分治法实现,脚点判别算法的并行化采用一种随机分配策略将三角网划分为多个离散分布的三角形子集合来实现负载均衡。并行滤波方法在8核环境下多次渐进加密的实际加速比达到3.1左右。试验证明,该方法可以充分发挥多核计算优势,并且对不同分布形态点云数据具有良好的适应性。