{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T03:58:25Z","timestamp":1760241505537,"version":"build-2065373602"},"reference-count":38,"publisher":"MDPI AG","issue":"5","license":[{"start":{"date-parts":[[2018,4,24]],"date-time":"2018-04-24T00:00:00Z","timestamp":1524528000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"the National Key Research and Development Program of China","award":["2016YFF0201305"],"award-info":[{"award-number":["2016YFF0201305"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IJGI"],"abstract":"<jats:p>The extraction of terrain feature lines is an important yet challenging problem in the processing and usage of contour lines. Most research has focused on identifying terrain feature points by using methods such as the Douglas\u2013Peucker (D\u2013P) algorithm and on determining contour adjacent relations for closed contour lines by using methods such as Delaunay triangulation and its dual Voronoi diagram, with few attempts made to address open contour lines and identify the direction of contour lines. Here, we propose a novel method for terrain feature line extraction based on adjacent relation trees. First, a contour adjacent relation tree is constructed. The tree is used to determine the directions of closed and open contour lines and thereby form a \u201cdirected adjacent relation tree\u201d (DART). Terrain feature points are then extracted using the classic D\u2013P algorithm, followed by the identification and connection of valley and ridge points via the aforementioned DART. Finally, integrity compensation for terrain feature lines is performed based on a slope extension algorithm. The effectiveness and accuracy of this method is verified by experimental results obtained from 1:10,000 topographic map data.<\/jats:p>","DOI":"10.3390\/ijgi7050163","type":"journal-article","created":{"date-parts":[[2018,4,25]],"date-time":"2018-04-25T03:22:45Z","timestamp":1524626565000},"page":"163","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Extraction of Terrain Feature Lines from Elevation Contours Using a Directed Adjacent Relation Tree"],"prefix":"10.3390","volume":"7","author":[{"given":"Chengming","family":"Li","sequence":"first","affiliation":[{"name":"Chinese Academy of Surveying and Mapping, Beijing 100830, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Peipei","family":"Guo","sequence":"additional","affiliation":[{"name":"Chinese Academy of Surveying and Mapping, Beijing 100830, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pengda","family":"Wu","sequence":"additional","affiliation":[{"name":"Chinese Academy of Surveying and Mapping, Beijing 100830, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xiaoli","family":"Liu","sequence":"additional","affiliation":[{"name":"Chinese Academy of Surveying and Mapping, Beijing 100830, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2018,4,24]]},"reference":[{"key":"ref_1","unstructured":"Price, C.V., Wolock, D.M., and Ayers, M.A. (1989, January 14\u201318). Extraction of terrain features from digital elevation models. Proceedings of the 1989 National Conference Hydraulic, New Orleans, LA, USA."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1016\/j.cageo.2012.06.011","article-title":"Implementation and performance optimization of a parallel contour line generation algorithm","volume":"49","author":"Xie","year":"2012","journal-title":"Comput. Geosci."},{"key":"ref_3","unstructured":"Schmieder, A., and Huber, R. (2000, January 22\u201326). Automatic Generation of Contour Lines for Topographic Maps by Means of Airborne High-Resolution Interferometric Radar Data. Proceedings of the ASPRS Annual Conference, Washington, DC, USA."},{"key":"ref_4","unstructured":"Li, Z., Sui, H., and Gong, J. (1999, January 14\u201321). A system for automated generalization of contour lines. Proceedings of the International Carthographic Conference, Ottawa, ON, Canada."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"323","DOI":"10.1016\/S0734-189X(84)80011-0","article-title":"The extraction of drainage networks from digital elevation data","volume":"28","author":"Mark","year":"1984","journal-title":"Comput. Vis. Graph. Image Process."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"667","DOI":"10.5194\/hess-15-667-2011","article-title":"Efficient extraction of drainage networks from massive, radar-based elevation models with least cost path search","volume":"15","author":"Metz","year":"2011","journal-title":"Hydrol. Earth Syst. Sci."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1016\/j.cageo.2008.09.002","article-title":"Extraction of drainage networks from large terrain datasets using high throughput computing","volume":"35","author":"Gong","year":"2009","journal-title":"Comput. Geosci."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"615","DOI":"10.1016\/j.cageo.2005.09.001","article-title":"An efficient depression processing algorithm for hydrologic analysis","volume":"32","author":"Zhu","year":"2006","journal-title":"Comput. Geosci."},{"key":"ref_9","first-page":"197","article-title":"Computer-assisted determination of the valley and ridge lines of digital terrain models","volume":"24","author":"Yoeli","year":"1984","journal-title":"Int. Yearbook Cartogr."},{"key":"ref_10","first-page":"1593","article-title":"Extracting Topographic Structure from Digital Elevation Data for Geographic Information System Analysis","volume":"54","author":"Jenson","year":"1988","journal-title":"Photogramm. Eng. Remote Sens."},{"key":"ref_11","first-page":"574","article-title":"A Method of Terrian Feature Extraction Based on Contour","volume":"42","author":"Zhang","year":"2013","journal-title":"Acta Geod. Cartogr. Sin."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1179\/caj.2000.37.1.29","article-title":"An integrated technique for automated generalization of contour maps","volume":"37","author":"Li","year":"2000","journal-title":"Cartogr. J."},{"key":"ref_13","first-page":"1129","article-title":"Classifying Hills and Valleys in Digitized Terrain","volume":"66","author":"Cronin","year":"2000","journal-title":"Photogramm. Eng. Remote Sens."},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Hege, H.-C., Polthier, K., and Scheuermann, G. (2009). Representing interpolant topology for contour tree computation. Topology-Based Methods in Visualization II, Springer.","DOI":"10.1007\/978-3-540-88606-8"},{"key":"ref_15","unstructured":"Pascucci, V., Cole-McLaughlin, K., and Scorzelli, G. (2004, January 6\u20138). Multi-resolution computation and presentation of contour trees. Proceedings of the IASTED Conference on Visualization, Imaging, and Image, Marbella, Spain."},{"key":"ref_16","unstructured":"Qiao, C.F., Chen, J., and Zhao, R.L. (2005, January 27\u201329). Preliminary studies on contour tree-based topographic data mining. Proceedings of the International Symposium on Spatio-Temporal, Beijing, China."},{"key":"ref_17","unstructured":"Poorten, P., and Jones, C.B. (1999, January 14\u201321). Customisable line generalization using Delaunay triangulation CD-Rom. Proceedings of the 19th International Cartographic Association Conference, Ottawa, ON, Canada."},{"key":"ref_18","first-page":"461","article-title":"The Method of Generating Contour Tree Based on Contour Delaunay Triangulation","volume":"41","author":"Zhang","year":"2012","journal-title":"Acta Geod. Cartogr. Sin."},{"key":"ref_19","first-page":"472","article-title":"Automated Contour Labelling and the Contour Tree","volume":"7","author":"Roubal","year":"1985","journal-title":"Proc. AUTO-CARTO"},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"112","DOI":"10.3138\/FM57-6770-U75U-7727","article-title":"Algorithms for the reduction of the number of points required to represent a digitized line or caricature","volume":"10","author":"Douglas","year":"1973","journal-title":"Can. Cartogr."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"37","DOI":"10.3138\/JX16-7262-8161-24L6","article-title":"A New Approach for the Simplification of Contours","volume":"39","year":"2004","journal-title":"Cartographica"},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"Guo, X., Li, R., and Huang, C. (2009, January 13\u201314). Direction difference in terrain features extraction. Proceedings of the International Symposium on Spatial Analysis, Spatial-Temporal Data Modeling, and Data Mining, Wuhan, China.","DOI":"10.1117\/12.838625"},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"281","DOI":"10.14358\/PERS.75.3.281","article-title":"An Adaptive Approach to Topographic Feature Extraction from Digital Terrain Models","volume":"75","author":"Song","year":"2009","journal-title":"Photogramm. Eng. Remote Sens."},{"key":"ref_24","doi-asserted-by":"crossref","unstructured":"Liu, H.J., Jin, H.L., and Miao, B.L. (2010, January 4). An Algorithm for Extracting Terrain Structure Lines Based on Contour Data. Proceedings of the SPIE\u2013The International Symposium on Digital Earth: Models, Algorithms, and Virtual Reality, International Society for Optics and Photonics, Beijing, China.","DOI":"10.1117\/12.872701"},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1016\/j.isprsjprs.2007.04.002","article-title":"The Drainage Network Extraction from Contour Lines for Contour Line Generalization","volume":"62","author":"Ai","year":"2007","journal-title":"ISPRS J. Photogramm. Remote Sens."},{"key":"ref_26","doi-asserted-by":"crossref","unstructured":"Zhang, C., Zhang, X., and Jiang, W. (2009, January 11\u201313). Rule-based Extraction of Spatial Relations in Natural Language Text. Proceedings of the International Conference on Computational Intelligence and Software Engineering, CiSE 2009, Wuhan, China.","DOI":"10.1109\/CISE.2009.5363900"},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1080\/13658810701349003","article-title":"Automated spot heights generalisation in trail maps","volume":"22","year":"2008","journal-title":"Int. J. Geogr. Inf. Sci."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"42","DOI":"10.1016\/j.comgeo.2006.05.009","article-title":"Flexible isosurfaces: Simplifying and displaying scalar topology using the contour tree","volume":"43","author":"Carr","year":"2010","journal-title":"Comput. Geom."},{"key":"ref_29","doi-asserted-by":"crossref","unstructured":"Acharya, A., and Natarajan, V. (2015, January 14\u201317). A parallel and memory efficient algorithm for constructing the contour tree. Proceedings of the 2015 IEEE Pacific Visualization Symposium (PacificVis), Hangzhou, China.","DOI":"10.1109\/PACIFICVIS.2015.7156387"},{"key":"ref_30","unstructured":"Gilperez, A., Alonso-Fernandez, F., and Pecharroman, S. (2008, January 19\u201321). Off-line signature verification using contour features. Proceedings of the 11th International Conference on Frontiers in Handwriting Recognition, Montre\u0301al, QC, Canada."},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"1481","DOI":"10.1109\/TVCG.2009.120","article-title":"Automatic transfer function generation using contour tree controlled residue flow model and color harmonics","volume":"15","author":"Zhou","year":"2009","journal-title":"IEEE Trans. Vis. Comput. Gragph."},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"160","DOI":"10.1109\/TSP.2010.2084085","article-title":"\u201cVector Cross-Product Direction-Finding\u201d with an Electromagnetic Vector-Sensor of Six Orthogonally Oriented But Spatially Noncollocating Dipoles\/Loops","volume":"59","author":"Wong","year":"2010","journal-title":"IEEE Trans. Signal Process."},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"198","DOI":"10.1016\/j.isprsjprs.2009.11.001","article-title":"A DEM generalization by minor valley branch detection and grid filling","volume":"65","author":"Ai","year":"2010","journal-title":"ISPRS J. Photogramm. Remote Sens."},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"171","DOI":"10.1006\/ciun.1994.1011","article-title":"Extracting topographic terrain features from elevation maps","volume":"59","author":"Kweon","year":"1994","journal-title":"CVGIP Image Understand."},{"key":"ref_35","unstructured":"Zhang, X., Zhang, C., and Du, C. (July, January 29). SVM based extraction of spatial relations in text. Proceedings of the IEEE International Conference on Spatial Data Mining and Geographical Knowledge Services, Fuzhou, China."},{"key":"ref_36","unstructured":"Ruas, A. (March, January 27). Multiple Paradigms for Automating Map Generalization: Geometry, Topology, Hierarchical Partitioning and Local Triangulation. Proceedings of the ACSM\/ASPRS Annual Convention and Exposition, Washington, DC, USA."},{"key":"ref_37","doi-asserted-by":"crossref","unstructured":"Ware, J.M., Jones, C.B., and Bundy, G.L. (1995, January 21\u201323). A Triangulated Spatial Model for Cartographic Generalization of Areal Objects. Proceedings of the International Conference on Spatial Information Theory, Vienna, Austria.","DOI":"10.1007\/3-540-60392-1_12"},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"741","DOI":"10.1016\/j.comgeo.2014.02.005","article-title":"Delaunay refinement algorithms for triangular mesh generation","volume":"47","author":"Shewchuk","year":"2014","journal-title":"Comput. Geom. Theory Appl."}],"container-title":["ISPRS International Journal of Geo-Information"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2220-9964\/7\/5\/163\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T15:02:01Z","timestamp":1760194921000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2220-9964\/7\/5\/163"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,4,24]]},"references-count":38,"journal-issue":{"issue":"5","published-online":{"date-parts":[[2018,5]]}},"alternative-id":["ijgi7050163"],"URL":"https:\/\/doi.org\/10.3390\/ijgi7050163","relation":{},"ISSN":["2220-9964"],"issn-type":[{"type":"electronic","value":"2220-9964"}],"subject":[],"published":{"date-parts":[[2018,4,24]]}}}