凹包内散乱点集Delaunay四面体角度剖分算法-论文.pdf

《凹包内散乱点集Delaunay四面体角度剖分算法-论文.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第35卷第2期水道港口Vo1．35No．22014年4月JournalofWaterwayandHarborApr．2014凹包内散乱点集Delaunay四面体角度剖分算法李世森，王熹芳(天津大学，天津300072)摘要：在邵铁政Ⅲ三维空间散乱点集Delaunay四面体剖分算法的基础上，提出了一种不含有除法运算(不存在被0除或丧失计算精度的情形)的通用的判定空间两三角形内交的算法，可以实现凹包内散乱点集的Delaunay四面体剖分。该算法已经通过Fortran语言编程实现并且给出了算例。关键词：散乱点；Delaunay规则；空间三角形内交；四面体

2、中图分类号：0182．2文献标识码：A文章编号：1005～8443(2014)02—0180—05Delaunay三角剖分算法起源于1934年俄国数学家Delaunay提出的Delaunay准则]。在应用有限元方法解决各类问题时，Delaunay网格有严谨的数学证明，能够生成形态优化的网格b]，是网格划分的主要方法之一。目前，Delaunay角剖分算法广泛地应用于计算机图形学、航天、地质、土木工程等领域，体现了较强的实用价值。Delaunay三角剖分算法大致可以分为三类：分而治之算法、逐点插入算法和三角网增长法⋯。虽然二维的Delaunay三角剖

3、分算法已经取得了一定的成果，但是三维空间的Delaunay四面体剖分算法，由于三维空间外包面的复杂性，目前的研究还不够成熟。如文献[5—6]需要先从任意多面体中剖分出一个凸空间，得到一个新的多面体，再把剖分出来的凸空间分割成多个四面体，再重复对新的多面体进行剖分，直至剖分完毕；文献[7-9]在对空间散乱点集进行Delaunay四面体剖分时，需要先将散乱点集的外边界进行Delaunav三角剖分，由边界面生成初始四面体，再通过交换或寻找几何关系将初始四面体剖分更新为新的四面体。本文提出了对边界面已知的，外包面为凹的空间散乱点进行Delaunay四面体

4、剖分的算法。通过引入对于空间2个三角形是否内交的判断，保证了生成的四面体在凹包边界面的里侧，实现了凹包内散乱点集的Delaunay四面体剖分。1凹包内散乱点Delaunay四面体网格生成方法1．1相关概念为了有效地解决凹包内散乱点Delaunay四面体剖分，本算法给出了空间两三角形内交的定义。空间两三角形内交定义为在三维空间内，当一个三角形三条边所围成的区域与另一个三角形三条边所围成的区域的交集为一条线段时，则称作两三角形内交。在本算法中，当该线段与三角形的某一条边重合时，不认为两三角形内交。1．2基本思路参考文献[1]在Delaunay准则定义

5、口、球缺角定义n、四面体球缺角定义及特性⋯的基础上，给出了凸包内散乱点集Delaunay四面体剖分算法，本算法在此基础上又加入了判断空问两三角形内交的算法。给定一个空间散乱点集以及该散乱点集的外包面(以空间三角形面组成)，首先用参考文献[1]中的方法对散乱点集进行Delaunay四面体划分，然后判断生成四面体的各个面是否与已知的边界面内交。若内交继续寻找下收稿日期：2013—04—02；修回日期：2013—06—20作者简介：李世森(1969-)，男，河北冀县人，副教授，主要从事港口航道与近海水流、泥沙研究。Biography：LIShi—sen

6、(1969一)，ma]e，associateprofessor．2014年4Y]李世森，等凹包内散乱点集Delaunay四面体角度剖分算法181一点构成四面体，若不内交，则生成一个Delaunay四面体，这样就使得参考文献[1]中的方法能够处理凹包设空间内一个三角形的三个顶点坐标分别为Pl(Y，)，P2(，Y：，z：)，P。(Y)，则该j角形所在平面另一三角形的三个顶点坐标为Q(％Y)，Q(Y，)，Q，(Y，)，该三角形所在平面方程设为为了判断这两三角形是否内交，需要首先分别判断一个三角形的三条边所在的直线与另一三角形所在平面的位置关系：相交、平

7、行(交点在无穷远处相交)、在面内(有无穷多个交点)。以判断三角形Q。QQ的边f+By+Cz+D=0(1)1：：(2)I5一4y5一y4z5一z4连等式(2)的每一项均乘以一)(y一y)0一)得到新的无除法的连等式后，再与方程式(1)联立可解得方程组的解，但是当=或Y：Y或=z时，这样求解方程组是不可以的。为了求解该方程组，令连等式(2)中的每一项均等于即==：T，与方程式(1)联立可解得直线Q1Q，与平面K．交=一X4)+X=一)+z如果直接采用式(3)这一表达式进行计算机编程，当t，=0时(或者t，非常的接近于0时)，会造成计算机数值溢出(或者

8、计算结果丧失精度)。即式(3)在计算机中并不是总能求出具体的数值(但是式(3)在任何情求解完直线QQ：与平面K的交点表达式后，需要进一步