Research On The Isoline Generation Algorithm Based On Delaunay Triangulation

Isoline, which is the combination of data and figure, helps us find the trends of changing data. The greater distance between the contour lines is, the smaller amount of change in value will be. As a way to reflect the value change, isoline, which is a common and effective way of expression, is widely used in petroleum exploration and development, geology, geophysical mapping, military, geophysical and other aspects.Triangulated irregular network model, which changes with the change of the density of point set,can be a good representation of surface morphology. When the terrain is complex, the collected data points are relatively dense and triangles are small and dense, when the terrain is flat, the collected data points are relatively sparse, and triangles will be relatively large and sparse. In all the triangulation algorithms, the Delaunay triangulation algorithm is used most widely currently, it is because that the results of Delaunay triangulation are closest to equilateral triangle and illegal triangles can be avoided. The method of triangle mesh improves the speed and accuracy of contour mapping because of using the uneven original data without any other operations. In this dissertation, the main work is as follows.1) The traditional Delaunay triangulation algorithms are introduced at the first and in this dissertation the Delaunay triangulation is implemented by incremental insertion algorithm. Point location is the most time-consuming process part in Delaunay triangulation, since each point should be processed. With the increase in the number of points, the total number of triangles is also increasing. The efficiency will be too low to use without a good strategy to solve the problem. The directed acyclic graph is used to solve the point location process in this dissertation and the time complexity is O(nlogn) which reaches the lower limit.2) It is difficult to find the start point in contour propagation algorithm. We use an array to record the boundary edge and treat non-closed contours and closed contours separately. Non-closed contour lines always start with a boundary edge and terminate in a boundary edge, while the starting point and the ending point of a closed contour coincide. We process the non-closed contour lines according to the topological relation of edges and triangles at first, the contour line walks across from a triangle to the adjacent triangle. After all the isoline points on boundary edges being processed, if there are any isoline points being left, they are the points on closed contours. The only difference between closed contours tracking and non-closed contours tracking is that any point can be the starting point in closed contours tracking as a closed contour is like a circle.3) Contours generated without being processed are connected by a series of lines and needed to be smoothed and labeled. In this dissertation, the Tension Spline Function is used for smoothing contour lines, and some other smoothing methods are introduced and compared. Labeling is another important processing to help people get more useful information from the contour map. It looks more natural after labeling on the flat region.