二维任意域内点集的Delaunay三角划分的研究

传统的Ｄｅｌａｕｎａｙ三角划分不适合许多实际的应用．本文提出了二维任意域内点集的Ｄｅｌａｕｎａｙ三角划分（简记为ＤＴＡＤ）的概念，研究了其存在性、唯一性的条件以及一个三角划分是ＤＴＡＤ的充要条件．ＤＴＡＤ具有最小角最大以及平均形态比最大的性质，因此它是给定区域和点集的最佳三角划分．本文同时阐述了它的对偶图：任意域内点集的Ｖｏｒｏｎｏｉ图的概念和性质．ＤＴＡＤ突破了传统的Ｄｅｌａｕｎａｙ三角划分的限制，为有限元网格划分等实际应用提供了理论基础．

一种基于区域分割的三角划分方法

基于三维重建中物体截面轮廓边缘序列中相邻轮廓基本相似的事实 ,提出了一种物体截面轮廓线点集之间的三角划分的快速算法。该算法首先寻找轮廓线的控制点 ,对每两条相邻轮廓线的控制点进行配对 ,其次将这样两条轮廓线之间的三角划分的任务分配在多个小的曲线段对之间进行 ,并且由于事先的控制点匹配 ,在每个小的区域中就能够进行简化快速的三角划分。通过试验验证了本算法的有效性。

实现3D离散点优化三角划分的三维算法

本文系统研究了３Ｄ离散数据的直接三角划分，并解决了与多值曲面相对应离散数据的分片三角划分问题。实现这一算法的关键是将这些与多值曲面相对应的离散数据按有关的特征线分解，慢之转化成较简单的问题分别进行处理。目前，这种分片三角划分算法已在Ｂｅｚｉｅｒ三角曲面插值中取得了良好的效果。

基于约束Delaunay三角划分法在节理图上实现网格自动剖分

分析了现有的在节理图上自动生成有限元网格方法的不足之处,提出了应用约束Delaunay三角划分法来实现网格剖分。该方法将所有的节理线看作特征约束线,在散乱点约束的Delaunay三角划分的基础上,逐次嵌入约束线,然后再应用细化算法进行网格加密,得到符合数值计算精度要求的网格。

多连通曲面离散点集的3D三角划分算法研究

在对非封闭曲面、简单封闭曲面和多连通封闭曲面的特点进行分析之后,提出了一种多连通封闭曲面离散点集的3D三角划分算法.该算法无须对离散点集所对应的自由曲面进行分片,直接在3D空间根据曲面的形态变化向前逐层推进生成三角网格.算法同时还适用于非封闭曲面和简单封闭曲面两种情形.实验结果表明,该算法的划分效果优良,能够满足曲面重构的需要.

二维Delaunay三角划分的平均形态比最大性质

本文提出了三角划分的一种新的准则：平均形态比最大准则，证明了二维Ｄｅｌａｕｎａｙ三角划分具有最大的平均形态比，从而证明了平均形态比最大准则、最小角最大准则、Ｃｉｒｃｌｅ准则的等价性．这个性质在理论上进一步说明了Ｄｅｌａｕｎａｙ三角划分的最优性，为有限元网格划分的质量评估提供了理论依据，并为寻求三维三角划分的最优准则提供了线索．

离散点集3D三角划分算法在裁剪曲面中的实现

提出一种在 3D空间直接对曲面离散数据点进行三角网格划分的算法 ,该方法适用于非封闭曲面、封闭曲面及多连通复杂曲面的离散点集 ,同时也能处理剪裁曲面的离散点集 ,得到优良的三角网格。在引入边界环融合的概念的基础上 ,详细阐述算法如何实现对剪裁曲面离散点集三角划分 。

散乱数据点集的三角划分算法研究

在对当前的三角网格划分方法进行比较分析后,提出了一种散乱数据点集的3D三角网格划分算法,该算法不需如同二维划分方法一样要对散乱点集对应的自由曲面分片投影,并可自然处理含有凹边界及孔域的曲面数据点集,利用网格扩展、边界环分裂和边界环封闭,根据曲面的变化逐层推进生成三角网格,使算法能方便地处理非封闭曲面、空间剪裁曲面、封闭曲面、空间多连通曲面等各种曲面的散乱数据。

一种新的求解最小权三角划分的免疫算法

提出了一种基于自适应免疫遗传算法的求解最小权三角划分(MWT)问题的方案,通过自适应地调整疫苗库的进化和有选择地注射疫苗,提高了新算法的收敛速度和全局搜索能力,结合具体的MWT问题,给出了疫苗更新与注射算子构造的具体方案。仿真实验表明,新算法能产生比免疫算法更好的划分效果,尤其适合大规模点集,有较大的实用价值。

基于PVM的最小权三角划分并行遗传算法研究

平面点集的三角划分在计算机图形学,三维可视化等领域具有广泛地应用,在许多应用中需要提供形状最优的三角划分。但该类问题推测属于NP完全问题。为了快速有效地求解最小权三角划分(MWT)问题,提出了一种基于PVM的并行遗传算法来近似获取全局最优解,并系统地测试算法中一些重要的并行控制参数,包括迁移代数和节点平均负载对算法性能的影响。实验结果表明,该方法简单,可靠,大大缩短了优化过程的时间,提高获取全局最优解的概率。

平面轮廓线之间的分块三角划分算法

从三维空间点集通过三角划分重建三维表面的方法在实际应用中涉及到的数据量常常很大 ,因此对算法的计算速度有较高的要求。基于三维重建中物体截面轮廓边缘序列中相邻轮廓基本相似的事实 ,提出了一种物体截面轮廓线点集之间的三角划分的快速算法。该算法首先寻找轮廓线的控制点 ,对每两条相邻轮廓线的控制点进行配对 ,其次将这样两条轮廓线之间的三角划分的任务分配在多个小的曲线段对之间进行 ,并且由于事先的控制点匹配 ,在每个小的区域中就能够进行简单快速的三角划分。理论分析和实验表明 ,本算法与常规的全局优化算法相比在视觉效果上基本一致 ,在计算时间上却要少得多 。

基于局部分块三维物体表面三角划分算法

基于三维重建工作中物体截面轮廓线序列中相邻轮廓线基本相似的事实，提出了物体截面轮廓线点集之间三角划分的一种快速算法．算法首先寻找轮廓线的控制点，对每两条相邻轮廓线的控制点进行配对；然后将这样两条轮廓线之间的三角划分分配在多个小曲线段对之间进行，并且根据事先匹配的控制点，在每个小的区域中进行简便快速的三角划分．实验验证了算法的有效性．

基于三角划分的多连通域图形匹配研究

由若干个多边形通过组合产生的具有多个连通域的多连通域图形识别问题是工程图纸识别与理解所要解决的重要问题。首先,通过建立包围多边形、连通多边形概念,完成对多连通域图形的表示;然后,依据最近距离、无遮挡、包含原则添加辅助线,实现三角划分,解决了包含连通的定位问题。在匹配过程中,首先通过匹配包围多边形实现多连通域图形的外轮廓定位;然后通过匹配连通多边形删除连通域,逐步收缩图形,实现图形匹配。应用此方法,解决了多连通域图形的旋转、缩放匹配问题,在汽车线束图纸识别中取得了良好的应用效果。

三维物体表面三角划分的快速算法

通过三角划分从三维空间点集重建三维表面的方法 ,在实际应用中涉及到的数据量常常很大 ,因此对算法的计算速度有较高的要求 .基于三维重建时物体截面轮廓线序列中的相邻轮廓线基本相似的事实 ,提出了一种物体截面轮廓线点集之间的三角划分的快速算法 .该算法首先寻找轮廓线的控制点 ,并对每两条相邻轮廓线的控制点进行配对 ,然后将这样两条轮廓线之间的三角划分 ,分配在多个小的曲线段对之间进行 ,并且由于事先进行了控制点匹配 ,因此 ,在每个小的区域中就能够进行简化快速的三角划分 .经理论分析和实验 ,该算法与常规的全局优化算法相比 ,在视觉效果上基本一致 ,可在计算时间上却要少得多 。

基于Delaunay三角划分策略的WSN区域覆盖优化研究

针对无线传感器网络在对初次抛洒节点形成的覆盖漏洞进行二次部署的过程中,传统几何学方法难以运用于概率感知模型的问题,提出一种基于Delaunay三角划分策略的无线传感器网络区域覆盖优化算法——DPSO算法。首先对监测区域内随机抛洒的静态节点和监测区域边缘顶点进行Delaunay三角划分,以得到静态节点三角网,结合无线传感器网络节点的概率感知模型证明三角形内部存在完全未覆盖区域即覆盖漏洞;其次将通过筛选得到的三角形形心集合作为粒子群优化算法的初始解集,利用改进的粒子群优化算法完成对移动节点的二次部署,以达到修复覆盖漏洞的目的。实验表明,所提出的基于Delaunay三角划分策略的优化算法能够有效修复覆盖漏洞,使区域覆盖率得到显著提高。

基于二维凸多边形内散乱点的三角划分新算法

基于给定的平面散点数据,提出了逐层提取轮廓线,并将轮廓线之间的区域进行三角划分的新算法。实现这一算法的关键是在给定阈值的条件下逐层提取内部离散点的轮廓线,再在所提取的轮廓线间进行等比例三角划分。最后,利用Lawson提出的局部优化过程来优化分割好的三角形网。通过实验证明了算法的有效性。

散乱点云的三角划分算法研究

通过对当前的三角网格划分方法进行比较分析,提出了一种散乱点云的3D三角网格划分算法。该算法不需如同二维划分方法那样要对散乱点云对应的自由曲面分片投影,而是直接在3D空间,根据离散点集所对应的曲面形态变化,利用网格扩展、边界环分裂和边界环封闭,逐层收缩生成三角网格。该算法能方便地处理空间多种曲面的散乱点云数据,并且生成的三角网格形态优良,布局合理。

3D空间离散点集三角划分的逐层收缩算法

根据离散点集所对应曲面的形态变化,采取逐层推进收缩方法,在3D空间直接对离散点集进行三角划分,生成三角网格。通过实例证明,该算法切实可行,并具有一定的优越性,对逆向工程CAD建模技术的发展具有指导作用。

密集散乱数据三角划分及数据压缩

介绍了Delaunay三角划分方法 ,运用一种算法对密集散乱数据进行三角划分 ,并在给定容差条件下对其进行成批压缩。由点云数据中最大、最小的六个点构成初始八面体 ,将数据分割为八个三角形区域上的凸包数据 ,在每个凸包数据中 ,搜寻到其对应的三角形的垂直距离最大的点 ,如果距离大于给定的容差 ,则将该点插入并局部优化三角网格。反之则将该点压缩掉。最后给出的实例证明了该算法的有效性和效率。

关于多边形三角划分中的一个逼近问题

1970年Monksy证明了正方形不能划分为奇数个面积相等的三角形 ,此性质已被推广到中心对称的多边形以及其它特殊的多边形 .本文证明 :对任意多边形K ,存在平面多边形簇 {Kn｜n∈N} 和 {K′n｜n ∈N} 使得{Kn｜n∈N}∪ {K′n｜n∈N} 中任何一个Kn 或K′n 都不能划分为奇数个面积相等的三角形并且limn→∞ Kn =K=limn→∞ K′n ,A(Kn) A(K) A(K′n) ,limn→∞ A(Kn) =A(K) =limn→∞ A(K′n) .