基于线结构光扫描点云数据的数据精简及三角网格剖分

在分析线结构光扫描点云数据特点的基础上,讨论了针对测量点云数据精简算法,包括测量基面数据精简和基于弦高-角度偏差准则的数据精简算法.介绍了散乱数据的基于Delaunay三角剖分优化准则和Liang提出的相邻扫描线之间的三角网格构建方法,并在此基础上提出了一种改进方法,基于优化准则的线结构光扫描点云数据三角剖分算法,该算法符合Delaunay的三角最优剖分.以摩托车后视镜点云数据为例的实验结果表明该方法是有效的和切实可行的.图12,参11.     

一种改进的螺旋边三角剖分算法

提出了一种改进的螺旋边三角剖分算法.本算法引用“自然邻近点集”的概念,以螺旋边三角剖分算法的边界环为基础向外生长三角形,以包围盒算法搜索边界点的邻近点集,估计边界点的法向量,将边界点及其邻近点集投影到切平面上并进行局部二维Delaunay三角剖分,从而确定边界点的自然邻近点集,最后将自然邻近点集以适当的方式添加到边界环上.这样,既避免了拼接问题又能搜索到自然邻近点集,三角剖分后的网格基本上接近最优Delaunay网格.实验结果表明,本算法能高效、稳定地重构出散乱数据点的三角网格.     

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

描述了一种平面散乱点集的Delaunay三角剖分算法.首先对散乱点集预处理,保证每次插入的点落在已处理点集形成的临时边界环外;然后逐点插入预处理后的点,使临时边界环不断向外围扩展,直至点集处理完毕,形成散乱点集的三角网格;最后运用Delaunay优化准则优化.该算法由于充分利用了Visual C 语言中MFC类的数据资源,使得编程容易实现.最后举例验证了该算法的优越性.     

Delaunay三角剖分在线算法

本文提出一个构造平面有限点集Ｄｅｌａｕｎａｙ三角剖分的实时算法，并给出算法正确性的 严格的征明．该算法是文献［１］所预示的一个好算法．     

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

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

一种简单的三维地形重建方法

基于等高线地图的三维地形重建是目前的研究热点,但读懂等高线地图需要一定的专业知识,并且应用等高线地图进行地形重建需要较专业的OpenGL等工具以及很高的编程技术.提出了一种基于散乱点的三维地形重建算法:先对这些散乱点在平面内做三角剖分得到一些三角形,然后用等值线切割每个三角形得到一些内点,并计算出每一个内点的坐标及高程,最后对所有的点再次应用三角剖分方法生成空间中的三角形面片.实验结果及算法复杂度分析表明该算法既简单易行又达到了预期效果.     

三角网自动连接的聚焦算法

在三角网生长法的基础上，采用面向对象的技术，利用点数组和点索引数组来存贮平面上的散乱数据点，基于Delaunay三角剖分的“圆准则”，提出三角网自动连接的聚焦算法．该算法在扩展新三角形时，将点的搜索范围控制在已知三角形的外接圆内，计算速度大大加快．从给出的算例表明，该算法十分有效，特别适合于大数据量的三角剖分。     

三正则平面图与平面三角剖分图

探讨三正则平面图的路与平面三角剖分图 Hamilton圈的关系 ,给出平面三角剖分图 Hamilton圈的一个充分条件及算法     

长江口北槽水域的Delaunay三角剖分

为了进行长江口水动力过程等的有限元数据模拟，研究了任意平面区域的Delaunay三角剖分和基于背景网格等值线点集的新的自动生成方法：局部三角形内得到等值线、进行自动加点；改进任意平面区域的Delauay三角剖分法，与行波法结合，从区域边界向域内逐步三角化，前者简化了自动加点算法，保证新生成点均位于域内、疏密连续变化和最终网格具有良好形态，后者则统一解决了多连通、4点共圆和非凸域的自动三角剖分问题，逐步减少人为给定边界的影响，从而减少了算法的运行时间，据此开发的软件包可动态监控点，网格的生成过程，并经大量的测试、验证，应用于长江口北槽水域的自动加点和三角剖分，取得了较好的效果。     

空间点集Voronoi图的海量构造算法及可视化技术

设计空间点集Voronoi图的增量式外存算法以及空间点集Voronoi图的任意平面可视化剖分技术,以"点-线-面-体"的空间数据结构为基础,实现在指定空间区域内生成Voronoi图的新方法.提出的算法数据结构清晰合理,数据交互方案简单有效且无内存限制,发展的可视化技术可以对空间点集Voronoi图进行任意的平面剖分,实现了三维Voronoi晶胞集合体内部结构的可视化.     

三角剖分中拓扑关系的动态创建与维护

平面散点域的三角化效率一直是人们关心的问题.以三角形面结构为存储结构,对逐点插入三角化算法中三角形的拓扑关系维护进行了研究,提出了动态创建和维护三角形拓扑关系的算法.算法原理简单、通用性强,实验测试表明基于本文原理所设计的逐点插入算法有较高的执行效率.     

基于约束三角剖分的k-means聚类

提出基于约束三角剖分的k-means聚类算法.笔者首先按照约束三角剖分规则对数据点集进行三角网格化,删除大于给定阈值的长边形成k个连通子图,每个连通子图作为一个子类;然后对删除长边的孤立数据点在其邻域内进行局部划分,将其归到最接近的子类中.实验结果表明本文算法无需事先输入聚类数目,可以发现任意非凸形状簇.     

任意形状平面域不完全Delaunay三角化研究

基于构造平面凸集Ｄｅｌａｕｎａｙ三角化的圆准则，提出了任意形状平面域的不完全圆准则，并给出了以该准则为条件的不完全Ｄｅｌａｕｎａｙ三角化算法。该算法也可用于处理平面凸集的Ｄｅｌａｕｎａｙ三角化。最后给出了考核实例。     

微切平面逼近三维散乱数据的研究

提出了三维散乱数据微切平面逼近的算法．基于曲面形状信息反映在三维散乱点集中，用三维点集中某点的邻域点集构造微切平面来近似表示该点处的局部形状，所有点的微切平面集合则构成了待构曲面的近似表示．通过欧几里德最小生成树对微切平面法矢方向进行调整使其达到整体一致性，该算法在三维散乱数据曲面重构中具有重要意义．     

最小权三角划分的进化算法

提出了一种解决平面点集最小权三角划分的新方法——最小权三角划分进化算法。针对平面点集最小权三角划分问题的特点，提出了新的交叉算子和变异算子，即多边形交叉算子与三角形变异算子。从而保证了经交叉与变异操作后得到的后代仍为合理的三角划分，加快了算法的收敛速度。研究了进化算法的几个主要参数（如：解群规模、交叉概率、变异概率及自适应系数）对算法性能及收敛性的影响，并给出了影响曲线。计算结果表明，新算法能得到比贪心算法更优的结果。     

Data Reduction and Triangulation Approach to Scattered Points

For the generation of the model in reverse engineering, a laser scanner is currently used a lot due to the fast measuring speed and high precision. Direct triangulation of data points captured from a physical object has a great advantage in that it can reduce the time and error in modeling process. It is important to reduce the number of data points for triangulating points with maintaining precision. To triangulate data points within a tolerance ε a new approach is developed in this paper. Different level of triangulations can be generated directly from data points using the proposed strategy that reduces and triangulates data points based on triangulation of 3D parametric surfaces. An experimental example is presented to demonstrate the effectiveness and efficiency of the proposed algorithm.     

连杆平面通过五个位置的运动综合

采用两组四位置设计问题相结合的方法解决五位置的运动综合问题，把自由曲线自动求交的原理应用于圆心（圆点）曲线，改进了连杆平面精确通过五个指定位置时设计铰链四杆机构的方法，避免了直接求解时不易收敛的问题     

Trimmed 曲面的隐藏线消除算法

提出了一种Ｔｒｉｍｍｅｄ曲面的隐藏线消除算法．首先将Ｔｒｉｍｍｅｄ曲面三角化;其次将显示屏幕分割成一定数量的小矩形区域;再将Ｔｒｉｍｍｅｄ曲面上的三角片投影到屏幕上,并分类到不同的矩形区域中;最后进行曲面网格点对三角片的可见性测试,并显示消隐后的曲面．     

基于MPI的二维经验模分解并行算法

针对二维经验模分解(BEMD)处理大尺寸图像耗时较长的问题,提出了一种基于MPI技术的BEMD并行算法.对BEMD串行程序中极值点选取、平面三角剖分、三角域内数值插值等几个主要部分的运行时间进行了统计,结果表明三角域内数值插值是耗时的主要部分,也是并行化的重点处理部分;随后在高性能计算平台上构建并行环境,基于MPI技术对BEMD算法的包络面生成部分实现了并行化,具体方法是先将剖分后的三角形序列按照进程数均匀划分,使整个图像分割为若干子区域并分配给相应进程,然后各进程拟合出对应子区域的上下Bezier曲面并由0进程进行合并,进而生成上下包络面;最后通过加速比等指标对该算法进行测评.结果表明,算法在30核并行执行时加速比可达20.1396,利用率为64.97%,运行效率的提升较为明显.在数据量达到原始数据的25倍时可扩展性指标为1.3975,表明该算法对大数据量的任务有很好的适应性.