3维离散数据四面体快速生成算法研究

Algorithm for Fast Constructing Tetrahedral Network From Three Dimensional Dispersed Data

文中系统地研究了使用逐点插入算法构建3维离散数据四面体模型中的几个关键问题,提出了动态创建和维护四面体拓扑关系的方法,建立了快速确定点在四面体中的算法原理及空外接球判断法则的简易表达式,实验分析证明本算法有着较高的执行效率,算法复杂度与点数几乎成线性关系。

This paper studies some key procedures that hold up the efficiency of tetrahedral network based on Delaunay(DTEN). A algorithm for dynamically renewing the topological relations in DTEN is represented. The paper also studies the way of finding tetrahedral network that contains a given point in DTEN and the formula of empty circum-sphere test. The incremental insertion algorithm of constructing DTEN, has a time complexity that is about linear to the number of points set.