三角剖分算法研究

三角剖分是计算机辅助几何设计、几何造型及计算机图形学中研究的重要内容之一。对于设计一个三角剖分算法来说,最重要的就是其复杂度低和高质量网格的形成。三角剖分算法在计算几何、曲面重构及有限元网格生成中有着重大的应用价值。本文研究内容如下: 1.首先介绍了离散点和多边形三角剖分的一些基本理论,以及Voronoi图和Delaunay三角剖分的定义,包括Delaunay三角剖分的优化准则、Delaunay三角/四面体剖分的相关定义。 2.研究了多边形的三角剖分。首先介绍了凸多边形的相关定义和凸划分算法。凸划分中特殊的情况就是生成的凸多边形为三角形。算法思想是先采用切割耳的方法删去歧点(同时又是凸点),使剖分的时候的两条链都是单调链,然后剖分这个单调多边形。但是这样生成的三角形中狭长的三角形比较多。所以在产生三角形的同时,使用Delaunay三角剖分的优化准则,以便生成质量更好的三角形。 3.本文重点在第四章,首先介绍了平面点集三角剖分的定义,接着对主要的平面点集三角剖分算法进行了介绍,并且采用了对比方式进行分析描述。在Delaunay三角剖分优化准则的基础下,提出了一种新的平面点集三角剖分算法。该算法的基本思想就是生成一个满足的条件的三角形,以每条边为基础向周围寻找可以满足条件的点,生成新的三角形,再以新的三角形为基础向周围生长,直至覆盖平面中的所有点。该算法的时间复杂度为O ( n log n ),很好地避免了病态三角形的出现,提高了网格质量,特别适用于有限元网格生成。 4.在二维三角剖分的基础上,推广到三维空间。首先介绍了凸壳的一些基本概念和平面点集凸壳的一些重要算法。接着给出了两个三维空间点集剖分算法。一种算法是:先求得点集的凸壳,然后在凸壳区域内根据点的坐标,利用四阶行列式的值来选择一个符合条件的点进行点集剖分。从而提高了算法的效率。该算法的时间复杂度为O ( n log n )。另外一种是空间点集三角剖分算法,算法的思想是:首先生成一个凸壳,接着在剩下的点再形成一个凸壳,依次类推。所有的点都划成凸壳,接着关键就是凸壳之间的连接。这样可以保证生成更好的三角形,从而保证剖分质量。