Research On Key Technologies Of High-Performance Digital Terrain Analysis

With the development of surveying equipment and technologies,the amount of DEM data used for digital terrain analysis is increasing,while the computational efficiency of some present algorithms is low,resulting in overlong processing time.Although many researches have been devoted to improving the efficiency of digital terrain analysis,it is often difficult to fully utilize the superior performance of computer clusters while the optimization of relative algorithms is insufficient.Parallel computing and algorithm optimization are two effective ways to solve the above problems.Based on the theory of digital terrain analysis and practical problems,this thesis adopts the optimization and the parallelization of algorithms to improve the efficiency of digital terrain analysis.According to the characteristics of actual digital terrain analysis problems,cut-fill analysis and flood analysis are selected for further analyze.The aim is to propose a corresponding high-performance analysis method for each type of digital terrain analysis problems.The main contents and achievements of this thesis include the following three parts.(1)Aiming at the actual problems of cut-fill analysis,a parallel cut-fill algorithm based on equal area partitioning is proposed,which improves the calculation efficiency and the processing capacity of massive DEM data.For the problem of cut-fill analysis under irregular region,the parallelization of the cut-fill algorithm is implemented based on equal-area data partitioning scheme,which ensures the load balancing of parallel tasks,while improving the processing capability by reading in DEM data according to segmentations.The proposed algorithm provides a general parallelization method for non-neighbor analysis problems.(2)Given the water level,a parallel flooding analysis algorithm based on strip boundary tracking is proposed.Meanwhile,a parallel result fusion strategy is designed to improve the computational efficiency of the parallel algorithm.By optimizing the serial algorithm,the parallelizable component of the flooding algorithm is improved,which provides a theoretical basis for the parallel efficiency improvement of the algorithm.Through the efficient result fusion strategy,the serial components existed in the algorithm are effectively reduced,leading to improved parallelization degrees.The proposed algorithm also provides an effective parallelization strategy for neighborhood analysis problems.(3)Given the amount of water,a flooding analysis algorithm based on rapid merge tree generation is proposed.The merge tree generation algorithm belongs to global analysis algorithms,which means its parallelization is difficult,resulting in negligible parallel efficiency improvement.By optimizing the algorithm with higher complexity,the overall analysis time can be effectively reduced,while the computational efficiency of the flooding analysis can be improved.By optimizing the existing flooding analysis and its preprocessing algorithm,this thesis reduces the running time of the preprocessing algorithm and analyzes the more efficient flooding query scheme.The optimization ideas proposed in this thesis have a strong reference value for other global analysis algorithms.