散乱数据三角剖分方法研究

作     者：胡荣林 

作者单位：南京理工大学 

学位级别：硕士

导师姓名：李东波

授予年度：2003年

学科分类：081203[工学-计算机应用技术] 08[工学] 0835[工学-软件工程] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主      题：三维散乱数据点,三角剖分,空间划分,局部增量,网格扩张 

摘      要：本文主要研究了三维散乱数据的三角剖分算法。低计算复杂度和高网格质量的三角剖分算法在计算几何、曲面重构及三维数据场可视化等研究领域中有着重大的应用价值。 本文在详细研究和分析了典型平面及空间散乱数据三角剖分算法思想后，根据散乱数据点规模越来越大的趋势，提出了一种大规模散乱数据的空间划分方法及相应的数据结构和编码方案，缩小了在剖分时搜寻和遍历数据点的空间范围，提高了算法效率。通过分析空间散乱数据点之间拓扑关系的本质特征提出了基于局部增量网格扩张的三维散乱数据点的空间直接三角剖分算法，并首次提出了外连剖分和内连剖分的概念。该算法能在线性时间内完成三角剖分计算，其总体计算复杂度为O(N)，有效地降低了三角剖分算法的时间复杂度，提高了剖分后网格的质量。本文还分析了三维空间直接三角剖分所要解决的一些关键问题，进而提出了空间中点与直线位置关系判别的新方法及空间多边形顶点凹凸性判别的新方法，修正了以往算法在应用上的局限性，使之能够适用于复杂网格多边形边界。