The Stabilization Of Triangle And Its Applications In Geoscience Modeling

Triangulation is often applied to Computational Geometry、Geometry、Physical Modeling、Numerical Simulation and some other areas. Triangulation is a very important branch in computational geometry. Delaunay triangulation has the properties of MaxMin angle criterion, MinMax angle criterion and incircle tests, etc. It is generally considered to be the "nice" triangular mesh. Triangle is a program for two-dimensional mesh generation and construction of Delaunay triangulations, constrained Delaunay triangulations and Voronoi. Triangle is fast, memory-efficient, and robust. Guaranteed-quality meshes are generated using refinement algorithm. Features include user-specified constraints on angles and triangle areas, user-specified holes, concavities and concaveness, etc. Therefore, Triangle is often applied to the study of geographic modeling.In geographic applications, as the data are often very large, floating-point errors will lead to the program failure. The actual geographic case is analyzed in this paper. It is found that in the process of inserting constrained edge into Delaunay triangulation because the almost coincidence point is inserted which has caused the dead circulation and collapse of the Triangle program. Further experiments show that if we make a translation of point coordinates in the above case, we can reduce the point coordinates and then can successfully use Triangle to generate CDT. This suggests that floating-point is so big that it causes the floating-point errors which leads to the dead circulation. Therefore, it is necessary to improve the Triangle algorithm to avoid the emergency of this situation and meet the needs of geographic modeling.Triangle uses the sign area to determine whether the segment pipm locates within the angle of the oriented triangle△PiPkPj (the origin of the triangle is pi)., Whether the segment is left collinear or right collinear with the oriented triangle can be judged especially when the sign area is zero. For floating-point, whether a floating-point number equals to zero is usually determined by judging whether its absolute value is less than a given fully small positive. Therefore, the method of Triangle to judge the collinearity is debatable. Although the Triangle has adopted the economical and practical means of exact arithmetic to compensate for the impact of floating-point error, which maybe appropriate for the case of the smaller size of the data. However, it may not be able to fit for the problem of larger scale and data. This paper presents two new algorithms to determine whether the segment locates within the angle of the oriented triangle(algorithm4.4and4.5).For example, in determining whether the segment pipm is left collinear with the oriented triangle△PiPkPj,a small enough relative value h/l is added to determine its left collinearity.(h is the distance from the point pm to the edge pipj of the oriented triangle△pmpipj and l is the length of the edge PiPj).This value better reflects the degree of collinearity between the insert segment pipm and the edge pipj of the oriented triangle△PiPkPj.Numerical experiments show that the improved Triangle is more stable and robust which can overcome the impact of large data as well as floating-point errors, so it can meet the needs of geographic modeling applications.