Objectives  Terrain simplification algorithms, which use minimal amount of effective terrain information to express the overall terrain, can solve the contradiction between massive terrain data and computer hardware, and meet the needs of multi-scale terrain applications. However, it is difficult for most of the existing terrain simplification algorithms to take local fluctuations and overall characteristics of the terrain into account at the same time. Aiming at these deficiencies, an adaptive terrain simplification algorithm based on centroidal Voronoi diagram is proposed.

  Methods  First, centroidal Voronoi diagram, which is generated by considering the topographic relief as density function, is used to simplify the terrain adaptively. Second, the terrain is reconstructed according to the sites of the centroidal Voronoi diagram that distributed in areas with large topographic relief, and Voronoi vertices, which mostly distributed on the terrain feature lines. Finally, the effect of simplification is verified by contrasting the feature lines of the original terrain and the reconstructed terrain. And the accuracy of the proposed algorithm is compared with that of 3D Douglas-Peucker algorithm.

  Results  Feature lines, such as ridge lines, valley lines and contours, extracted from simplified terrain and the original terrain have high degree of overlap. Therefore, the proposed algorithm maintains the features of the original terrain well. The simplification error of the proposed algorithm is lower than that of the 3D Douglas-Peucker algorithm at the same level of simplification.

  Conclusions  The proposed algorithm has a higher accuracy compared with 3D Douglas-Peucker algorithm.