Int. Arch. Photogramm. Remote Sens. Spatial Inf. Sci., XXXIX-B2, 23-28, 2012
http://www.int-arch-photogramm-remote-sens-spatial-inf-sci.net/XXXIX-B2/23/2012/
doi:10.5194/isprsarchives-XXXIX-B2-23-2012
© Author(s) 2012. This work is distributed
under the Creative Commons Attribution 3.0 License.
 
25 Jul 2012
DELAUNAY TRIANGULATION PARALLEL CONSTRUCTION METHOD AND ITS APPLICATION IN MAP GENERALIZATION
J. Shen1,2, L. Guo1,2, L. Qi3, and W. Zhu1,2 1Institute of Geographic Science, Nanjing Normal University, 210046 Nanjing, China
2Key Laboratory of Virtual Geographic Environment, Ministry of Education, Nanjing Normal University, China
3Nanjing Institute of Geography and Limnology Chinese Academy of Sciences, 210008 Nanjing, China
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.
Conference paper (PDF, 531 KB)


Citation: Shen, J., Guo, L., Qi, L., and Zhu, W.: DELAUNAY TRIANGULATION PARALLEL CONSTRUCTION METHOD AND ITS APPLICATION IN MAP GENERALIZATION, Int. Arch. Photogramm. Remote Sens. Spatial Inf. Sci., XXXIX-B2, 23-28, doi:10.5194/isprsarchives-XXXIX-B2-23-2012, 2012.

BibTeX EndNote Reference Manager XML