Message Board

Respected readers, authors and reviewers, you can add comments to this page on any questions about the contribution, review,        editing and publication of this journal. We will give you an answer as soon as possible. Thank you for your support!

Name
E-mail
Phone
Title
Content
Verification Code
Turn off MathJax
Article Contents

WANG Lei, ZHANG Na, YIN Nan, CHENG Gang, HE Shi. An Adaptive Terrain Simplification Algorithm Based on Centroidal Voronoi Diagram[J]. Geomatics and Information Science of Wuhan University. doi: 10.13203/j.whugis20200699
Citation: WANG Lei, ZHANG Na, YIN Nan, CHENG Gang, HE Shi. An Adaptive Terrain Simplification Algorithm Based on Centroidal Voronoi Diagram[J]. Geomatics and Information Science of Wuhan University. doi: 10.13203/j.whugis20200699

An Adaptive Terrain Simplification Algorithm Based on Centroidal Voronoi Diagram

doi: 10.13203/j.whugis20200699
Funds:

The National Natural Science Foundation of China (41801318)

  • Received Date: 2021-09-25
  • Objectives: Terrain simplification, which uses 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, itis 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, a terrain adaptive simplification algorithm based on centroidal Voronoi diagram is proposed. Methods: Centroid Voronoi diagram has the characteristic that site points converge to the region with larger density. Meanwhile, more data points should be assigned to the region with larger relief and rough surface in terrain simplification. Therefore, centroidal Voronoi diagram, which is generated by considering the topographic relief as density function, is used to simplify the terrain adaptively. Firstly, based on thedensity function given by topographic relief extracted from Digital Terrain Model (DEM), centroidal Voronoi diagram is generated using Lloyd's algorithm. Secondly, the DEM is simplified and 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. Thirdly, the effect of simplification is verified qualitatively by contrasting the feature lines, such as collection waterlines, ridge and valley lines and contours, of the reconstructed and theoriginal terrain. Finally, Root Mean Square Errors (RMSE) of the proposed algorithm and 3D Douglas-Peucker algorithm are computed and contrasted to access the effect of the simplification quantitatively. Results: (1) Feature lines, such as collection waterlines, ridge and valley lines and contours, extracted from simplified terrain and the original terrain have high degree of overlap. Therefore, the simplified terrain maintains the features of the original terrain better due the use of Voronoi vertices mostly distributed on the terrain feature lines. (2) The RMSE of the proposed algorithm is lower than that of the 3D Douglas-Peucker algorithm at each level of simplification. This is mainly because the proposed algorithm takes both centroidal Voronoi sites that distributed in areas with large topographic relief and centroidal Voronoi vertices that mostly distributed on the terrain feature lines into consideration, while 3D Douglas-Peucker algorithm only preserves the points distributed on the ridge and valley lines. Conclusions: The proposed centroidal Voronoi diagram-based algorithm simplifies terrain according to points in areas with large topographic relief and points on the ridge and valley lines of terrain. Both local fluctuations and overall characteristics of the terrain are taken into consideration in the algorithm, so it has higher accuracy compared with 3D Douglas-Peucker algorithm while maintaining the overall features of the terrain.
  • [1] Wiebel R. An Adaptive Methodology for Automated Relief Generalization[J]. AutoCarto, 1987, 1(8):42-49.
    [2] Chen Z, Guevara J A. Systematic Selection of Very Important Points (VIP) from Digital Terrain Model for Constructing Triangular Irregular Networks[C]. Auto-Carto 8, Baltimore, USA, 1987.
    [3] Bredregal C., Rivara M C. Longest-edge Algorithms for size-optimal Refinement of Triangulations[J]. Computer-Aided Design, 2014, 46:246-251.
    [4] Lee J. Comparison of Exiting Methods for Building Triangular Irregular Network, Models of Terrain from Grid Digital Elevation Models[J]. International Journal of Geographical Information System, 1991, 5(3):267-285.
    [5] Fei L., He J. A Three Douglas-Peucker Algorithm and its Application to Automated Generalization of DEMs. International Journal of Geographical Information Science, 2009, 23(6):703-718.
    [6] Douglas D H., Peucker T K. Algorithms for the Reduction of the Number of Points Required to Represent a digitized line or its Caricature[J]. Cartographica:The International Journal for Geographic Information and Geovisualization. 1973, 10(2):112-122.
    [7] Yang B., Shi W., Li Q. An Integrated TIN and Grid Method for Constructing Multiresolution Digital Terrain Models[J]. International Journal of Geographical Information Science, 2005, 19(10):1019-1038.
    [8] Zhou Q, Chen Y. Generalization of DEM for Terrain Analysis Using a Compound Method. ISPRS Journal of Photogrammetry and Remote Sensing, 2011, 66(1):38-45.
    [9] Chen Y., Zhou Q. A Scale-adaptive DEM for Multi-scale Terrain Analysis[J], International Journal of Geographical Information Science, 2013, 27(7):1329-1348.
    [10] Ringler T., Ju Li., Gunzburger M. A Multiresolution Method for Climate System Modeling:Application of Spherical Centroidal Voronoi Tessellations[J], Ocean Dynamics, 2008, 58(5-6):475-498.
    [11] Lloyd S. Least squares quantization in PCM[J]. IEEE Transactions on Information Theory, 1982, 28(2):129-137.
    [12] MacQueen J. Some Methods for Classification and Analysis of Multivariate Observations[C]. Proceedings of the Fifth Berkeley Symposium on Mathematical Statistics and Probability. Berkeley, 1967:181-197.
  • 加载中
通讯作者: 陈斌, bchen63@163.com
  • 1. 

    沈阳化工大学材料科学与工程学院 沈阳 110142

  1. 本站搜索
  2. 百度学术搜索
  3. 万方数据库搜索
  4. CNKI搜索

Article Metrics

Article views(371) PDF downloads(19) Cited by()

Related
Proportional views

An Adaptive Terrain Simplification Algorithm Based on Centroidal Voronoi Diagram

doi: 10.13203/j.whugis20200699
Funds:

The National Natural Science Foundation of China (41801318)

Abstract: Objectives: Terrain simplification, which uses 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, itis 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, a terrain adaptive simplification algorithm based on centroidal Voronoi diagram is proposed. Methods: Centroid Voronoi diagram has the characteristic that site points converge to the region with larger density. Meanwhile, more data points should be assigned to the region with larger relief and rough surface in terrain simplification. Therefore, centroidal Voronoi diagram, which is generated by considering the topographic relief as density function, is used to simplify the terrain adaptively. Firstly, based on thedensity function given by topographic relief extracted from Digital Terrain Model (DEM), centroidal Voronoi diagram is generated using Lloyd's algorithm. Secondly, the DEM is simplified and 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. Thirdly, the effect of simplification is verified qualitatively by contrasting the feature lines, such as collection waterlines, ridge and valley lines and contours, of the reconstructed and theoriginal terrain. Finally, Root Mean Square Errors (RMSE) of the proposed algorithm and 3D Douglas-Peucker algorithm are computed and contrasted to access the effect of the simplification quantitatively. Results: (1) Feature lines, such as collection waterlines, ridge and valley lines and contours, extracted from simplified terrain and the original terrain have high degree of overlap. Therefore, the simplified terrain maintains the features of the original terrain better due the use of Voronoi vertices mostly distributed on the terrain feature lines. (2) The RMSE of the proposed algorithm is lower than that of the 3D Douglas-Peucker algorithm at each level of simplification. This is mainly because the proposed algorithm takes both centroidal Voronoi sites that distributed in areas with large topographic relief and centroidal Voronoi vertices that mostly distributed on the terrain feature lines into consideration, while 3D Douglas-Peucker algorithm only preserves the points distributed on the ridge and valley lines. Conclusions: The proposed centroidal Voronoi diagram-based algorithm simplifies terrain according to points in areas with large topographic relief and points on the ridge and valley lines of terrain. Both local fluctuations and overall characteristics of the terrain are taken into consideration in the algorithm, so it has higher accuracy compared with 3D Douglas-Peucker algorithm while maintaining the overall features of the terrain.

WANG Lei, ZHANG Na, YIN Nan, CHENG Gang, HE Shi. An Adaptive Terrain Simplification Algorithm Based on Centroidal Voronoi Diagram[J]. Geomatics and Information Science of Wuhan University. doi: 10.13203/j.whugis20200699
Citation: WANG Lei, ZHANG Na, YIN Nan, CHENG Gang, HE Shi. An Adaptive Terrain Simplification Algorithm Based on Centroidal Voronoi Diagram[J]. Geomatics and Information Science of Wuhan University. doi: 10.13203/j.whugis20200699
Reference (12)

Catalog

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return