增量Delaunay三角化算法局部优化过程的分析与改进

增量Delaunay三角化算法局部优化过程的分析与改进

论文摘要

近年来随着数据采集设备和技术的发展,科学计算和工程分析的对象越来越复杂,大规模离散数据点的三角网格剖分引起了广泛的研究,如何提高三角网格的生成速度是当前网格剖分技术的研究热点之一。局部变换法和Watson算法是工程实践中常用的三角剖分算法,两者都属于逐点添加、局部优化的增量Delaunay三角剖分方法。快速定位包含新插入点的网格单元、减小局部优化的范围是增量Delaunay三角剖分方法的关键。建立离散数据的矩形空间索引可以提高查找包含新插入点的网格单元的效率,本文在此基础上重点研究了如下几个问题:(1)不同的加点次序对局部变换法和Watson算法的局部优化影响较大,按位置相邻次序加点的方法易产生外接圆较大的扁平三角形,引起较多三角形的局部优化,三角网格的生成速度下降。而按随机次序加点,网格生成过程中网格单元相对匀称,局部优化的三角形较少,缩短了局部优化消耗的时间。以激光点扫描采集的数据为例,统计分析了局部优化三角形的数量及分布特征,当数据点大于20000时,随机次序加点方法能提高三角网格生成速度1倍以上,且数据量越大,效率越高。(2)建立离散数据的矩形空间索引,按索引轮流加点,点序对局部优化的影响降低,相邻次序加点方法局部优化的三角形总量是随机次序加点方法的1.1~1.3倍,其中随机次序加点与没有空间索引的随机次序相比,局部优化的三角形数量仅增加了约1%。(3)点与三角形位置关系判别和三角形外接圆包含点的测试分别是局部变换法和Watson算法正确生成Delaunay三角网格的重要环节。对于大规模离散数据,点的空间分布比较复杂,由于计算机浮点运算精度有限,当数据点的位置坐标较大时,三角形的面积坐标和外接圆圆心、半径会产生较大的计算误差,导致点与三角形位置关系以及三角形外接圆包含点的错误判别,从而生成几何拓扑关系不正确的三角网格。采用相对位置坐标可以提高面积坐标和外接圆圆心、半径的计算精度,以等高线地图采集的393252点的实例数据进行测试,相对位置坐标的计算精度能够保证生成几何拓扑关系正确的Delaunay三角网格。将上述关于增量Delaunay三角剖分局部优化的研究成果应用于逆向工程、地质建模的实例数据处理,能够快速有效地生成Delaunay三角网格。在此基础上利用三角形外接圆半径与最长边之比评估三角网格的质量,在允许移动或添加数据点的情况下优化三角网格中的畸形单元。

论文目录

  • 摘要
  • Abstract
  • 第1章 绪论
  • 1.1 网格剖分的需求
  • 1.2 三角网格生成方法分类
  • 1.2.1 按剖分对象分类
  • 1.2.2 按算法思路分类
  • 1.3 Delaunay 三角化算法
  • 1.3.1 局部变换法
  • 1.3.2 Watson 算法
  • 1.4 本文的研究内容、目的与意义
  • 1.5 本文的组织与开发环境
  • 第2章 三角化的理论基础
  • 2.1 Delaunay 三角化的数学基础
  • 2.1.1 点的邻域与Dirichlet/Voronoi 图
  • 2.2 三角化的基本概念、定义
  • 2.2.1 n 维单纯体(n-simplex)
  • 2.2.2 三角化(triangulation)
  • 2.3 Delaunay 三角化的构造
  • 2.4 Delaunay 三角网的特性
  • 第3章 逐点添加-局部优化的Delaunay 三角化算法
  • 3.1 局部换边法
  • 3.2 Watson 算法
  • 3.3 数据结构设计
  • 3.4 主要类的设计
  • 3.5 提高算法的效率
  • 3.5.1 类的设计
  • 3.5.2 索引系统
  • 3.5.3 快速定位
  • 3.5.4 Delaunay 空洞与局部重构
  • 第4章 加点次序对三角网格局部优化的影响
  • 4.1 加点次序对局部优化的影响
  • 4.2 空间索引对局部优化的影响
  • 4.3 算法效率的提高
  • 4.4 增加随机选点功能的 Delaunay 三角剖分算法思路
  • 4.5 Delaunay 三角网格实例
  • 第5章 计算误差对离散点集Delaunay 三角剖分的影响
  • 5.1 局部变换法中点与三角形位置关系的判别
  • 5.2 Watson 算法中三角形外接圆计算误差的影响
  • 5.3 改进的面积坐标与外接圆圆心和半径的计算方法
  • 5.4 改进算法生成的Delaunay 三角网格实例
  • 第6章 Delaunay 三角网格质量评估
  • 6.1 网格单元质量的评价标准
  • 6.1.1 三角形的质量评价标准
  • 6.2 畸形网格单元
  • 6.2.1 畸形三角形单元
  • 6.3 改善网格单元质量的方法
  • 6.3.1 Laplacian 光顺
  • 6.3.2 Delaunay 细化算法
  • 第7章 应用实例
  • 7.1 激光扫描数据处理
  • 7.2 数字地形模型
  • 第8章 总结与展望
  • 8.1 工作总结
  • 8.2 展望
  • 参考文献
  • 致谢
  • 攻读硕士学位期间已发表及待发表的论文
  • 相关论文文献

    标签:;  ;  ;  ;  

    增量Delaunay三角化算法局部优化过程的分析与改进
    下载Doc文档

    猜你喜欢