The International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences
Publications Copernicus
Download
Citation
Articles | Volume XXXIX-B2
https://doi.org/10.5194/isprsarchives-XXXIX-B2-23-2012
https://doi.org/10.5194/isprsarchives-XXXIX-B2-23-2012
25 Jul 2012
 | 25 Jul 2012

DELAUNAY TRIANGULATION PARALLEL CONSTRUCTION METHOD AND ITS APPLICATION IN MAP GENERALIZATION

J. Shen, L. Guo, L. Qi, and W. Zhu

Keywords: Delaunay Triangulated Irregular Network, parallel computing, data partitioning, dynamic strip, mesh simplification

Abstract. Delaunay triangulated irregular network (D-TIN) has been widely used in various fields and also played an increasingly important role on map generalization. But for massive data processing, current D-TIN algorithm is still not efficient enough to meet the requirements of map generalization. Data partitioning is an important step of parallel algorithm design. The load balance and efficiency of data partitioning is the precondition of improving parallel algorithm efficiency. For aggregated distributed point sets, the traditional Delaunay Triangulation parallel algorithm can’t ensure the balance and the execution’s efficiency of the partitioning result. The paper introduces a partitioning method using dynamic strips aiming to guarantee the computing load balance. We tested the speed-up of the D-TIN parallel algorithm using different type of point sets and the results of the experiments shows that the method of dynamic strips partitioning can help to get high and stable speed-up and the data distributional pattern and size has less influence to it. The paper realizes a mesh simplification algorithm based on parallel D-TIN and compares the efficiency based on parallel and serial D-TIN.