凹包内散乱点集Delaunay四面体角度剖分算法 (2014年)

在邵铁政[1]三维空间散乱点集Delaunay四面体剖分算法的基础上，提出了一种不含有除法运算(不存在被0除或丧失计算精度的情形)的通用的判定空间两三角形内交的算法，可以实现凹包内散乱点集的Delaunay四面体剖分。该算法已经通过Fortran语言编程实现并且给出了算例。 ### 凹包内散乱点集Delaunay四面体角度剖分算法解析 #### 概述 本文介绍了一种改进的Delaunay四面体剖分算法，该算法针对凹包内的散乱点集，能够在无需进行除法运算的情况下实现四面体角度剖分。基于邵铁政提出的三维空间散乱点集Delaunay四面体剖分算法，研究者们进一步提出了判断空间中两个三角形是否内交的新算法，并通过Fortran语言进行了编程实现。 #### Delaunay三角剖分背景 Delaunay三角剖分是由俄国数学家Boris Delaunay于1934年提出的一种优化网格划分技术。这种技术在有限元方法的应用中尤为重要，因为它能够确保生成的网格具有良好的形状特性，从而提高数值计算的准确性和效率。随着计算机科学的发展，Delaunay三角剖分在计算机图形学、航天、地质学、土木工程等多个领域得到了广泛应用。 #### 三维空间的Delaunay四面体剖分难点 相较于二维情况下的三角剖分，三维空间中的四面体剖分面临着更大的挑战，尤其是在处理复杂的外包面结构时更为困难。现有的方法如分而治之算法、逐点插入算法及三角网增长法等，在处理三维空间中的凹包时存在一定的局限性。例如，某些方法需要首先构建凸空间来简化问题，然后再逐步分解，这种方法不仅增加了计算量，还可能引入额外的误差。 #### 改进算法的关键技术点 ##### 1. 相关概念 为了准确实现凹包内散乱点集的Delaunay四面体剖分，首先需要明确几个关键概念。空间两三角形内交是指在三维空间中，两个三角形之间的交集如果是一条线段，则认为这两个三角形内交（如果这条线段与其中一个三角形的边完全重合，则不算作内交）。 ##### 2. 基本思路 本算法在邵铁政提出的算法基础上增加了对空间两个三角形内交的判断。具体步骤包括： - 首先利用现有算法对散乱点集进行Delaunay四面体剖分。 - 接着检查每个生成的四面体面是否与已知的边界面发生内交。 - 如果发生内交，则继续寻找下一个点以构造四面体；如果没有内交，则生成的四面体满足Delaunay条件。 ##### 3. 判断空间两个三角形内交的数学方法 为了实现空间两个三角形内交的判断，研究者提出了一套具体的数学方法。设三角形的顶点坐标分别为\(P_1(x_1, y_1, z_1)\)、\(P_2(x_2, y_2, z_2)\)、\(P_3(x_3, y_3, z_3)\)和\(Q_1(x_4, y_4, z_4)\)、\(Q_2(x_5, y_5, z_5)\)、\(Q_3(x_6, y_6, z_6)\)，分别位于平面\(K_1\)和\(K_2\)上。通过建立联立方程组来判断两三角形所在直线与平面之间的位置关系（相交、平行或在面内）。特别地，为了避免除法运算可能导致的精度损失问题，算法采用了特殊的技术手段，即通过对联立方程的每一项乘以特定系数来消除除法运算。 #### 结论 本文提出了一种针对凹包内散乱点集的Delaunay四面体剖分新算法。该算法通过增加空间两三角形内交的判断机制，有效避免了传统方法在处理复杂外包面时遇到的问题。此外，通过消除除法运算，进一步提高了算法的稳定性和计算精度。这一改进对于提高三维空间中散乱点集的Delaunay四面体剖分效率具有重要意义。