Grid Cutting Method of 3D Stratum and Its Application to Engineering

In order to form triangles with discrete points which 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(n²). 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.