{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,14]],"date-time":"2026-06-14T07:26:10Z","timestamp":1781421970048,"version":"3.54.1"},"reference-count":28,"publisher":"MDPI AG","issue":"4","license":[{"start":{"date-parts":[[2020,4,17]],"date-time":"2020-04-17T00:00:00Z","timestamp":1587081600000},"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":["No. 2016YFB0501403"],"award-info":[{"award-number":["No. 2016YFB0501403"]}]},{"DOI":"10.13039\/501100001809","name":"the National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["Nos. 41201395, 416014160"],"award-info":[{"award-number":["Nos. 41201395, 416014160"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IJGI"],"abstract":"<jats:p>When using the traditional Douglas\u2013Peucker (D\u2013P) algorithm to simplify linear objects, it is easy to generate results containing self-intersecting errors, thus affecting the application of the D\u2013P algorithm. To solve the problem of self-intersection, a new vector line simplification algorithm based on the D\u2013P algorithm, monotonic chains and dichotomy, is proposed in this paper. First, the traditional D\u2013P algorithm is used to simplify the original lines, and then the simplified lines are divided into several monotonic chains. Second, the dichotomy is used to search the intersection positions of monotonic chains effectively, and intersecting monotonic chains are processed, thus solving the self-intersection problems. Two groups of experimental data are selected based on large data sets. Results demonstrate that the proposed experimental method has advantages in algorithmic efficiency and accuracy when compared to the D\u2013P algorithm and the Star-shaped algorithm.<\/jats:p>","DOI":"10.3390\/ijgi9040251","type":"journal-article","created":{"date-parts":[[2020,4,21]],"date-time":"2020-04-21T03:23:06Z","timestamp":1587439386000},"page":"251","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":23,"title":["A Vector Line Simplification Algorithm Based on the Douglas\u2013Peucker Algorithm, Monotonic Chains and Dichotomy"],"prefix":"10.3390","volume":"9","author":[{"given":"Bo","family":"Liu","sequence":"first","affiliation":[{"name":"Faculty of Geomatics, East China University of Technology, 418# Guanglan Road, Nanchang 330013, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Xuechao","family":"Liu","sequence":"additional","affiliation":[{"name":"Faculty of Geomatics, East China University of Technology, 418# Guanglan Road, Nanchang 330013, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Dajun","family":"Li","sequence":"additional","affiliation":[{"name":"Faculty of Geomatics, East China University of Technology, 418# Guanglan Road, Nanchang 330013, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yu","family":"Shi","sequence":"additional","affiliation":[{"name":"Faculty of Geomatics, East China University of Technology, 418# Guanglan Road, Nanchang 330013, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Gabriela","family":"Fernandez","sequence":"additional","affiliation":[{"name":"Department of Geography, Center for Human Dynamics in the Mobile Age (HDMA), San Diego State University, 5500 Campanile Drive, San Diego, CA 92182-4493, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yandong","family":"Wang","sequence":"additional","affiliation":[{"name":"State Key Laboratory of Information Engineering in Surveying, Mapping and Remote Sensing, Wuhan University, 129# Luoyu Road, Wuhan 430079, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"1968","published-online":{"date-parts":[[2020,4,17]]},"reference":[{"key":"ref_1","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 its caricature","volume":"10","author":"Douglas","year":"1973","journal-title":"Can. Cartogr."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"244","DOI":"10.1016\/S0146-664X(72)80017-0","article-title":"An iterative procedure for the polygonal approximation of plane curves","volume":"1","author":"Ramer","year":"1972","journal-title":"Comput. Graph. Image Process."},{"key":"ref_3","first-page":"50","article-title":"Rules for robot draughtsmen","volume":"42","author":"Lang","year":"1969","journal-title":"Geogr. Mag."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"101","DOI":"10.3138\/C213-3627-90X7-LR15","article-title":"The integration of simplification and smoothing algorithms in line generalization","volume":"26","author":"McMaster","year":"1989","journal-title":"Can. Cartogr."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1179\/caj.1988.25.2.143","article-title":"An Algorithm for Compressing Digital Contour Data","volume":"25","author":"Li","year":"1988","journal-title":"Cartogr. J."},{"key":"ref_6","unstructured":"Visvalingam, M., and Whyatt, J. (1992). Line generalisation by repeated elimination of the smallest area. Technical Report, Discussion Paper 10, Cartographic Information Systems Research Group (CISRG), The University of Hull."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"707","DOI":"10.1080\/13658810110053107","article-title":"Robustness in GIS algorithm implementation with application to line simplification","volume":"15","author":"Ratschek","year":"2001","journal-title":"Int. J. Geogr. Inf. Sci."},{"key":"ref_8","first-page":"3","article-title":"Line Generalization Based on Analysis of Shape Characteristics","volume":"25","author":"Wang","year":"1998","journal-title":"Cartogr. Geogr. Inf. Syst."},{"key":"ref_9","unstructured":"Zhao, Z., and Saalfeld, A. (1997, January 7\u201310). Linear-Time Sleeve-Fitting Polyline simplification algorithms. Proceedings of the AutoCarto 13, Seattle, WA, USA. Published by American Congress on Surveying and Mapping & American Society for Photogrammetry and Remote Sensing, Maryland."},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Gary, R.H., Wilson, A.D., Archuleta, C.M., Thompson, F.E., and Vrabel, J. (2010). Production of a National 1:1000000-Scale Hydrography Dataset for the United States: Feature selection, Simplification, and Refinement.","DOI":"10.3133\/sir20095202"},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"373","DOI":"10.1080\/02693799208901921","article-title":"Algorithms for automated line generalization based on a natural principle of objective generalization","volume":"6","author":"Li","year":"1992","journal-title":"Int. J. Geogr. Inf. Sci."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"1485","DOI":"10.1080\/13658816.2017.1306864","article-title":"Shape adaptive geometric simplification of heterogeneous line datasets","volume":"31","author":"Yakimova","year":"2017","journal-title":"Int. J. Geogr. Inf. Sci."},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"de Berg, M., van Kreveld, M., Overmars, M., Overmars, M., and Schwarzkopf, O. (2000). Computational Geometry: Algorithms and Applications, Springer. [2nd ed.].","DOI":"10.1007\/978-3-662-04245-8"},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"1003","DOI":"10.1016\/0098-3004(92)90017-L","article-title":"Principal axis line simplification","volume":"18","author":"Cromley","year":"1992","journal-title":"Comput. Geosci."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"427","DOI":"10.1080\/15230406.2013.803707","article-title":"Scale-specific automated line simplification by vertex clustering on a hexagonal tessellation","volume":"40","author":"Raposo","year":"2013","journal-title":"Cartogr. Geogr. Inf. Syst."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"22","DOI":"10.1080\/23729333.2019.1631535","article-title":"Simplification of polylines by segment collapse: Minimizing areal displacement while preserving area","volume":"6","author":"Kronenfeld","year":"2020","journal-title":"Int. J. Cartogr."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1179\/000870406X93490","article-title":"Performance Evaluation of Line Simplification Algorithms for Vector Generalization","volume":"43","author":"Shi","year":"2006","journal-title":"Cartogr. J."},{"key":"ref_18","first-page":"1236","article-title":"A new algorithm of vector date compression based on the tolerance of area error in GIS","volume":"32","author":"Mi","year":"2012","journal-title":"Sci. Geogr. Sin."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"7","DOI":"10.1559\/152304099782424901","article-title":"Topologically consistent line simplification with the Douglas-Peucker algorithm","volume":"26","author":"Saalfeld","year":"1999","journal-title":"Cartogr. Geogr. Inf. Sci."},{"key":"ref_20","unstructured":"Ho, P.S., and Kim, M.H. (2001, January 8\u201314). A hierarchical scheme for representing curves without self-intersections. Proceedings of the 2001 IEEE Computer Society Conference (CVPR 2001), Kauai, HI, USA."},{"key":"ref_21","unstructured":"Mantler, A., and Snoeyink, J. (2000). Safe sets for line simplification. 10th Annual Fall workshop on Computational Geometry, Stony Brok University. Available online: http:\/\/citeseerx.ist.psu.edu\/viewdoc\/summary?doi.10.1.1.32.402."},{"key":"ref_22","unstructured":"Avelar, S., and M\u00fcller, M. (2000). Generating topologically correct schematic maps. Proceedings of the 9th International Symposium on Spatial Data Handling, Swiss Federal Institute of Technolog Zurich. Technical Report."},{"key":"ref_23","unstructured":"Wu, S.T., and Marquez, M.R.G. (2003, January 12\u201315). A non-self-intersection Douglas-Peucker algorithm. Proceedings of the 16th Brazilian Symosium on Computer Graphics and Image Processing (SIBGRAPI), Sao Carlos, Brazil."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"995","DOI":"10.1016\/S0098-3004(02)00009-2","article-title":"Short note: A correction to the Douglas-Peucker line generalization","volume":"28","author":"Ebisch","year":"2002","journal-title":"Comput. Geosci."},{"key":"ref_25","unstructured":"Yan, H.W., Wang, M.X., and Wang, Z.H. (2012). Computational Geometry: Spatial Data Processing Algorithm, Science Press."},{"key":"ref_26","first-page":"17","article-title":"Assessment of line-generalization algorithms using characteristic points","volume":"12","author":"White","year":"1985","journal-title":"Cartogr. Geogr. Inf. Sci."},{"key":"ref_27","first-page":"1","article-title":"Computation of the Hausdorff distance between plane vector polylines","volume":"4","year":"1995","journal-title":"Auto-Carto XII: Proceedings of the International Symposium on Computer-Assisted Cartography, Charlotte, North Carolina"},{"key":"ref_28","unstructured":"Joao, E.M. (1998). Gauses and Consequences of Map Generalization, Taylor and Francis."}],"container-title":["ISPRS International Journal of Geo-Information"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2220-9964\/9\/4\/251\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,13]],"date-time":"2025-10-13T14:08:57Z","timestamp":1760364537000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2220-9964\/9\/4\/251"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,4,17]]},"references-count":28,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2020,4]]}},"alternative-id":["ijgi9040251"],"URL":"https:\/\/doi.org\/10.3390\/ijgi9040251","relation":{},"ISSN":["2220-9964"],"issn-type":[{"value":"2220-9964","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,4,17]]}}}