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

Algorithm for Fast Constructing Tetrahedral Network From Three Dimensional Dispersed Data

作　　者：钟正[1] 樊启斌[2] 张叶挺[1] 

机构地区：[1]武汉大学测绘遥感信息工程国家重点实验室,湖北武汉430079 [2]武汉大学数学与统计学院,湖北武汉430072

出　　处：《测绘学院学报》2004年第4期286-288,291,共4页Journal of Institute of Surveying and Mapping

摘　　要：文中系统地研究了使用逐点插入算法构建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.

关 键 词：3维离散数据 3维Delaunay四面体网格 四面体拓扑关系 

分 类 号：P208[天文地球—地图制图学与地理信息工程]