Discrete Points Of To Generate Triangulated Irregular Network Algorithm Research And Implementation

As the important expression of Visualization in scientific computing technology, the research about Digital Elevation Model has became a classic study of the Geo-Science. From the late1950's, people's enthusiasm about the DEM have not waned. In this sixty years, there are some mature models appear, such as Grid, TIN, contour lines. At the same time, the number of the methods about model is more and more, however, with the unremitting development of the GIS, in order to make the DEM model realistic with the terrain, the research about the algorithm research is continuing.TIN is more commonly used in the practical application. The generation algorithm of TIN has become a hot topic, so the algorithm drew people's attention. This paper summarized and analyzed the principle of traditional generation algorithms according to there's characteristics, described the principle and method to establish TIN with the convex hull. Because that many of computational geometry books simplified the process of building the convex hull by limiting points, this paper shows an improvement algorithm to solve this problem in the process of forming a convex hull. The core content about the algorithm in this paper is divided into two steps, the first step is to create triangulations quickly, second is optimizing design to the triangulations. The advantage of this algorithm is all the point which has not inserted to the convex hull is in the one side of the convex hull, at the same time, if the point is inserted, the point must in the inside of the convex hull. The running speed of the algorithm is faster than the traditional algorithms, at the sane time, the improved algorithm can deal with some particular cases, such as repeat points, three points are on a straight line.There have many constrained dates in the actual topography named the characteristic line, such as a large body water, ridge lines and valley line. The general algorithm about TIN is hard to meet the requirements. So this paper analyzed the existing research results, embedding the constrained data based the rapid generation of the triangular irregular network. In the processing of embedding constrained data, this paper using the improved edge loop switching method which meets the demand of the Delaunay triangulation. Through analyzed the special circumstances, this paper aimed at puts forward the solution about the special situation, improves the accuracy of the Triangular Irregular Network. At the same time, this algorithm deleted the triangle outside the constrained data, so that CD-TIN is more close to the actual terrain.In the tracking of the equivalent point, this method with full use of topological relation about the Triangular Irregular Network, making the tracking of the equivalent point more efficient and can effectively take care of the impact of constrained data fields. When the equivalence point is confirmed, this arithmetic use tension spline interpolation function in order to ensure the smooth of the contours and to meet require of the surface features.Finally, based on the experiment result about the improved algorithm, this paper analyzed and compared the results. Experiments show that this algorithm is simple, effective and practical.