Delaunay Triangulation Parallel Construction Method And Its Application In Map Generalization

As an important tool for geometry calculations, Delaunay triangulation (Delaunay Triangulated Irregular Network, hereinafter referred to as D-TIN) has been widely used in various fields. In recent years, with the development of computer, D-TIN has also played an increasingly important role on the map generalization and gradually became an indispensable tool. D-TIN generation algorithm has been matured within several decades of research, but for massive data processing, current D-TIN is still unable to meet the requirements of building efficient, therefore, using parallel computing techniques to improve building efficiency is an effective way. The study of D-TIN construction algorithm in parallel (hereinafter referred to as D-TIN parallel algorithm) began in the late 1980s, after twenty years of exploration, domestic and foreign scholars have proposed various parallel designs, among which D-TIN parallel algorithm, basing on data partition,is the most commonly used method. The balance of data partitioning results is to guarantee load balancing, thereby enhancing the performance of such an important premise for parallel algorithms. Although traditional D-TIN parallel algorithms method for data partition can obtain relatively balanced division results and high efficiency when used in the uniform density of point set, the balance of division results can only be obtained at the expense of division efficiency under non-uniform density of point set situation. Aiming to solve this dilemma, the paper puts forward a new D-TIN parallel algorithm based on dynamic strips data partitioning method as well as the realization of a comprehensive map for the Parallel Construction of D-TIN. Content and achievements of this study mainly include the following sections:1,Classified summarized the D-TIN generation algorithm, D-TIN and the D-TIN parallel algorithms integrated map application.Compared the advantages and disadvantages of parallel algorithm design mode, selected the approach of D-TIN parallel construction based on data partition as well as D-TIN generation algorithm based on the characteristics and status quo, selecting improved incremental insertion algorithm as the basis for this study algorithm.2,Aiming at the current D-TIN parallel algorithm problems and needs, proposed the division principle for D-TIN parallel algorithm data, and according to this principle,the paper designed the dynamic strips data partitioning method that can be applied to meet requirements of relatively balanced division results and high efficiency for many distribution types points set data, including gathering point set data. Experiments indicate that this method does help to improve the performance of parallel algorithm for D-TIN.3,Designed the D-TIN parallel algorithm platform, and on the ground of this platform, realized D-TIN parallel algorithm which based on dynamic strips data partitioning method, using different sizes of point set to test, do statistics and analyse the algorithms, along with evaluating the indexes such as its run time, speedup, parallel efficiency and scalability, etc. The results show that the parallel algorithm has better time performance and scalability.4,Analysed D-TIN constructions' special requirements catering for the comprehensive maps. Selected the rivers and collaborative contour lines in D-TIN constructing experiment on the basis of D-TIN parallel construction method. Conducted a parallel design for some major processes such as striking a common point, embedding constraint lines thus realized rapid construction of D-TIN catering for comprehensive maps.