作　　者： ; ; ; ;

机构地区： 中山大学

出　　处： 《地球科学（中国地质大学学报）》 2005年第3期377-380,386,共5页

摘　　要： 针对三维地层表示中散乱点的三角化问题,提出了一种新的剖分算法———环形三角剖分算法.该算法首先在散乱点中心构造初始三角形,并将其3条边作为初始环形路径;然后对环形路径上的每条线段,都在其外围寻找与两端点所成夹角最大的点构造新三角形,并将其纳入环形路径,从而使环形路径不断向外围扩展;重复此扩展过程直到所有散乱点都处于路径范围内.对上述剖分中遗漏的小块区域形成的“空洞”,利用简单多边形的三角剖分方法实现三角化.此算法时间复杂性介于Ο(n)与Ο(n2)之间,其效率体现在:只搜索外围散乱点,减少了夹角计算过程;只对已扩展点进行“空洞”判断,节省了处理时间.将此环形三角剖分算法应用于广东省东深供水改造工程的三维地层构造与分析中,取得了良好的剖分效果和执行效率,对地层的任意剖切和开挖分析均具有良好的支持. In order to form triangles with discrete points distributed in a plane in the research of 3D stratum, this paper presents a new algorithm called automatic annular triangular cutting arithmetic (AATCA) which expands from the center to the periphery. It constructs a triangle by searching for reasonable points in the periphery place around a polygon path from the beginning of the central part of these discrete points, and updates the polygon with time. There will be hollows during the expanding, as some small areas may be skipped. But they can be divided into triangles by an existing method. Then the memory structure of data in the grid cutting process is discussed; The basic procedure and steps of AATCA are given; The time complexity of AATCA we concerning about, is between O(n) and O(n2). Efficiency is embodied in two aspects: to reduce the steps of angle calculation by only considering some polygons distributed on the periphery or on the nearside of present side; and to save time by only giving an estimation of the hollows for the expanded points. The AATCA algorithm is then applied to the Water Supply Reconstruction Project from Dongjiang to Shenzhen, which is the largest water conservancy construction project in Guangdong Province at present. The results show that the algorithm not only gives a reasonable triangular division for the polygon points but also performs efficiently.

关 键 词： 三维地层 网格剖分方法 散乱点 三角化 工程应用

领　　域： [自动化与计算机技术] [自动化与计算机技术] [天文地球] [天文地球] [天文地球]