DELAUNAY TRIANGULATION PARALLEL CONSTRUCTION METHOD AND ITS APPLICATION IN MAP GENERALIZATION

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.