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

YAN Haowen, ZHANG Xingang, LU Xiaomin, LI Pengbo. Approach to automating the DP Algorithm—taking river simplification as an example[J]. Geomatics and Information Science of Wuhan University. doi: 10.13203/j.whugis20210412
Citation: YAN Haowen, ZHANG Xingang, LU Xiaomin, LI Pengbo. Approach to automating the DP Algorithm—taking river simplification as an example[J]. Geomatics and Information Science of Wuhan University. doi: 10.13203/j.whugis20210412

Approach to automating the DP Algorithm—taking river simplification as an example

doi: 10.13203/j.whugis20210412
Funds:

The National Natural Science Foundation of China (41930101).

  • Received Date: 2022-07-13
    Available Online: 2022-08-18
  • Objectives: Curve simplification is of importance in automated map generalization; nevertheless, the Douglas-Peucker Algorithm (i.e., the DP Algorithm) popularly used in map generalization is not automatic, because a key parameter called distance tolerance (i.e.,ε) must be given by experienced cartographers and need to be input before execution of the algorithm. Methods: To solve the problem, this paper proposed a method to automatically calculate 𝜀 and by which the automation of the DP Algorithm is achieved. The method consists of the following steps:(1) A formula is constructed by the Hausdorff Distance for calculating the similarity degree (Sim) between a curve at a larger scale and its simplified counterpart at a smaller scale. (2) 15 linear rivers are selected, and each of them are manually simplified to get their counterparts at seven different scales. The Sim of each original river and each of its simplified counterpart at a smaller scale can be obtained using the formula constructed by the Hausdorff Distance, and 15×7=105 coordinate pairs consisting of (S, Sim) can be got, and a function between Sim and 𝑆 are constructed by the curve fitting using the coordinates. (3) In the meanwhile, the 15 rivers are simplified using a number of 𝜀, and the Sim of each original river and each of its simplified counterpart at a smaller scale can be calculated using the formula constructed by the Hausdorff Distance. In this way, a number of coordinate pairs (ε, Sim) are got, and a function between 𝜀 and Sim is constructed by the curve fitting. (4) By the function between Sim and S and that between 𝜀 and Sim, a formula between 𝜀 and 𝑆 can be deducted. Using the formula ε can be calculated automatically, because in a map generalization task 𝑆 is usually known. After this step, automation of the DP Algorithm is achieved. Results: The experiments have shown that (1) the proposed DP Algorithm can automatically simplify the rivers in a specific geographical area to get the results at different scales; and (2) the resulting river curves generated by the proposed DP Algorithm have a high degree of similarity with the ones made by experienced cartographers. Their average similarity degree is 0.927. Conclusion: The proposed DP algorithm can simplify curve features on maps automatically, and the results are highly intelligent and credible. Although only river data is tested in this paper, the principle of the proposed method can be extended to other linear features on maps. Our future work will be on improving the accuracy of the proposed DP Algorithm using more river data so that the algorithm can be used in practical map generalization engineering.
  • [1] R Weibel.ATypology of Constraints to Line Simplification[C]//Advance in GIS Research Ⅱ,Proceedings of 7thinternational symposium on spatial Data Handling. Lon-don:Taylor&Francis, 1997.
    [2] Jenkins J, Fleenor A, Dietz F. Moving beyond the Frame:Geovisualization of Landscape Change along the Southwestern Edge of Yosemite National Park[J]. Journal of Geovisualization and Spatial Analysis, 2019, 3(2):9
    [3] Li Z L, Gong X Y, Jun C, et al. Functional Requirements of Systems for Visualization of Sustainable Development Goal (SDG) Indicators[J]. Journal of Geovisualization and Spatial Analysis, 2020, 4(1):5
    [4] Mao B, Li B C. Graph-Based 3D Building Semantic Segmentation for Sustainability Analysis[J]. Journal of Geovisualization and Spatial Analysis, 2020, 4(1):4
    [5] Larkey L B, Markman A B. Processes of Similarity Judgment[J]. Cognitive Science, 2005, 29(6):1061-1076
    [6] Visser H, de Nijs T. The Map Comparison Kit[J]. Environmental Modelling&Software, 2006, 21(3):346-358
    [7] Li B N, Fonseca F. TDD:A Comprehensive Model for Qualitative Spatial Similarity Assessment[J]. Spatial Cognition&Computation, 2006, 6(1):31-62
    [8] Rodriguez M A, Egenhofer M J. Determining Semantic Similarity among Entity Classes from Different Ontologies[J]. IEEE Transactions on Knowledge and Data Engineering, 2003, 15(2):442-456
    [9] Ramer U. An Iterative Procedure for the Polygonal Approximation of Plane Curves[J]. Computer Graphics and Image Processing, 1972, 1(3):244-256
    [10] 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
    [11] Hershberger J, Snoeyink J. Speeding up the Douglas-Peucker line-simplification algorithm[C]//Proceedings of the 5th Symposium on Data Handling, 1992:134-143
    [12] Yan H W. Quantitative Relations between Spatial Similarity Degree and Map Scale Change of Individual Linear Objects in Multi-Scale Map Spaces[J]. Geocarto International, 2015, 30(4):472-482
    [13] Yan H W, Shen Y Z, Li J. Approach to Calculating Spatial Similarity Degrees of the Same River Basin Networks on Multi-Scale Maps[J]. Geocarto International, 2016, 31(7):765-782
    [14] Chen Z L, Ye W. The Precise Representation Model of Topological Relations of Complex Planar Objects[J]. Journal of Geodesy and Geoinformation Science, 2019, 2(3):18-30
    [15] Huang B H, Zhong W, Zhai R J, et al. Hierarchical Area Partitioning Method of Urban Road Networks Matching[J]. Journal of Geodesy and Geoinformation Science, 2019, 2(3):55-67
    [16] Toussaint G T. A comparison of rhythmic dissimilarity measures[J]. FORMA. 2006, 21(2):129-149
    [17] Rosso R, Bacchi B, La Barbera P. Fractal Relation of Mainstream Length to Catchment Area in River Networks[J]. Water Resources Research, 1991, 27(3):381-387
    [18] Power C, Simms A, White R. Hierarchical Fuzzy Pattern Matching for the Regional Comparison of Land Use Maps[J]. International Journal of Geographical Information Science, 2001, 15(1):77-100
    [19] Huttenlocher D P, Klanderman G A, Rucklidge W J. Comparing Images Using the Hausdorff Distance[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1993, 15(9):850-863
  • 加载中
通讯作者: 陈斌, bchen63@163.com
  • 1. 

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

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

Article Metrics

Article views(74) PDF downloads(8) Cited by()

Related
Proportional views

Approach to automating the DP Algorithm—taking river simplification as an example

doi: 10.13203/j.whugis20210412
Funds:

The National Natural Science Foundation of China (41930101).

Abstract: Objectives: Curve simplification is of importance in automated map generalization; nevertheless, the Douglas-Peucker Algorithm (i.e., the DP Algorithm) popularly used in map generalization is not automatic, because a key parameter called distance tolerance (i.e.,ε) must be given by experienced cartographers and need to be input before execution of the algorithm. Methods: To solve the problem, this paper proposed a method to automatically calculate 𝜀 and by which the automation of the DP Algorithm is achieved. The method consists of the following steps:(1) A formula is constructed by the Hausdorff Distance for calculating the similarity degree (Sim) between a curve at a larger scale and its simplified counterpart at a smaller scale. (2) 15 linear rivers are selected, and each of them are manually simplified to get their counterparts at seven different scales. The Sim of each original river and each of its simplified counterpart at a smaller scale can be obtained using the formula constructed by the Hausdorff Distance, and 15×7=105 coordinate pairs consisting of (S, Sim) can be got, and a function between Sim and 𝑆 are constructed by the curve fitting using the coordinates. (3) In the meanwhile, the 15 rivers are simplified using a number of 𝜀, and the Sim of each original river and each of its simplified counterpart at a smaller scale can be calculated using the formula constructed by the Hausdorff Distance. In this way, a number of coordinate pairs (ε, Sim) are got, and a function between 𝜀 and Sim is constructed by the curve fitting. (4) By the function between Sim and S and that between 𝜀 and Sim, a formula between 𝜀 and 𝑆 can be deducted. Using the formula ε can be calculated automatically, because in a map generalization task 𝑆 is usually known. After this step, automation of the DP Algorithm is achieved. Results: The experiments have shown that (1) the proposed DP Algorithm can automatically simplify the rivers in a specific geographical area to get the results at different scales; and (2) the resulting river curves generated by the proposed DP Algorithm have a high degree of similarity with the ones made by experienced cartographers. Their average similarity degree is 0.927. Conclusion: The proposed DP algorithm can simplify curve features on maps automatically, and the results are highly intelligent and credible. Although only river data is tested in this paper, the principle of the proposed method can be extended to other linear features on maps. Our future work will be on improving the accuracy of the proposed DP Algorithm using more river data so that the algorithm can be used in practical map generalization engineering.

YAN Haowen, ZHANG Xingang, LU Xiaomin, LI Pengbo. Approach to automating the DP Algorithm—taking river simplification as an example[J]. Geomatics and Information Science of Wuhan University. doi: 10.13203/j.whugis20210412
Citation: YAN Haowen, ZHANG Xingang, LU Xiaomin, LI Pengbo. Approach to automating the DP Algorithm—taking river simplification as an example[J]. Geomatics and Information Science of Wuhan University. doi: 10.13203/j.whugis20210412
Reference (19)

Catalog

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return