{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,17]],"date-time":"2026-01-17T15:45:18Z","timestamp":1768664718575,"version":"3.49.0"},"reference-count":23,"publisher":"MDPI AG","issue":"10","license":[{"start":{"date-parts":[[2018,9,27]],"date-time":"2018-09-27T00:00:00Z","timestamp":1538006400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["41671410"],"award-info":[{"award-number":["41671410"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Excellent Young Scholar Foundation of Information Engineering University","award":["2016610802"],"award-info":[{"award-number":["2016610802"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IJGI"],"abstract":"<jats:p>Vectors are a key type of geospatial data, and their discretization, which involves solving the problem of generating a discrete line, is particularly important. In this study, we propose a method for constructing a discrete line mathematical model for a triangular grid based on a \u201cweak duality\u201d hexagonal grid, to overcome the drawbacks of existing discrete line generation algorithms for a triangular grid. First, a weak duality relationship between triangular and hexagonal grids is explored. Second, an equivalent triangular grid model is established based on the hexagonal grid, using this weak duality relationship. Third, the two-dimensional discrete line model is solved by transforming it into a one-dimensional optimal wandering path model. Finally, we design and implement the dimensionality reduction generation algorithm for a discrete line in a triangular grid. The results of our comparative experiment indicate that the proposed algorithm has a computation speed that is approximately 10 times that of similar existing algorithms; in addition, it has better fitting effectiveness. Our proposed algorithm has broad applications, and it can be used for real-time grid transformation of vector data, discrete global grid system (DGGS), and other similar applications.<\/jats:p>","DOI":"10.3390\/ijgi7100391","type":"journal-article","created":{"date-parts":[[2018,9,28]],"date-time":"2018-09-28T02:54:54Z","timestamp":1538103294000},"page":"391","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":9,"title":["Duality and Dimensionality Reduction Discrete Line Generation Algorithm for a Triangular Grid"],"prefix":"10.3390","volume":"7","author":[{"given":"Lingyu","family":"Du","sequence":"first","affiliation":[{"name":"Institute of Surveying and Mapping, Information Engineering University, Zhengzhou 450001, China"}]},{"given":"Qiuhe","family":"Ma","sequence":"additional","affiliation":[{"name":"Institute of Surveying and Mapping, Information Engineering University, Zhengzhou 450001, China"}]},{"given":"Jin","family":"Ben","sequence":"additional","affiliation":[{"name":"Institute of Surveying and Mapping, Information Engineering University, Zhengzhou 450001, China"}]},{"given":"Rui","family":"Wang","sequence":"additional","affiliation":[{"name":"Institute of Surveying and Mapping, Information Engineering University, Zhengzhou 450001, China"}]},{"given":"Jiahao","family":"Li","sequence":"additional","affiliation":[{"name":"The Army Infantry Academy, Nanchang 330103, China"}]}],"member":"1968","published-online":{"date-parts":[[2018,9,27]]},"reference":[{"key":"ref_1","first-page":"316","article-title":"An Adaptive Visualized Model of the Global Terrain Based on QTM","volume":"36","author":"Zhao","year":"2007","journal-title":"Acta Geod. Cartogr. Sin."},{"key":"ref_2","unstructured":"Zhang, H., Wen, Y., and Liu, A. (2006). The Basis of Geographic Information System Algorithm, Science Press."},{"key":"ref_3","first-page":"309","article-title":"Study of Auto-vectorization Based on Scan-thinning Algorithm","volume":"41","author":"Liu","year":"2012","journal-title":"Acta Geod. Cartogr. Sin."},{"key":"ref_4","first-page":"1109","article-title":"On Digital Differential Analyzer (DDA) Circle Generation for Computer Graphics","volume":"100","author":"Mccrea","year":"1975","journal-title":"IEEE Comput. Soc."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"10","DOI":"10.1109\/MAHC.2002.1114866","article-title":"Three Early Algorithms","volume":"24","year":"2002","journal-title":"IEEE Ann. Hist. Comput."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1147\/sj.41.0025","article-title":"Algorithm for Computer Control of a Digital Plotter","volume":"4","author":"Bresenham","year":"1965","journal-title":"IBM Syst. J."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"331","DOI":"10.1016\/0734-189X(87)90041-7","article-title":"Double-step Incremental Generation of Lines and Circles","volume":"37","author":"Wu","year":"1987","journal-title":"Comput. Vis. Graph. Image Process."},{"key":"ref_8","first-page":"61","article-title":"A Six-step Algorithm for Line Drawing","volume":"37","author":"Jia","year":"2007","journal-title":"J. Shandong Univ."},{"key":"ref_9","first-page":"1719","article-title":"Self-adaptive Step Straight-line Algorithms","volume":"46","author":"Huang","year":"2006","journal-title":"J. Tsinghua Univ."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"647","DOI":"10.1137\/050642009","article-title":"Discrete Lines and Wandering Paths","volume":"21","author":"Vince","year":"2007","journal-title":"Siam J. Discret. Math."},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Fekete, G., and Treinish, L.A. (1990). Sphere Quadtrees: A New Data Structure to Support the Visualization of Spherically Distributed Data. Proceedings of SPIE\u2014The International Society for Optical Engineerin, SPIE Digital Library.","DOI":"10.1117\/12.19991"},{"key":"ref_12","unstructured":"Dutton, G. (1999). A Hierarchical Coordinate System for Geoprocessing and Cartograph, Springer."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"489","DOI":"10.1080\/13658810110043603","article-title":"Continuous Indexing of Hierarchical Subdivision of the Global","volume":"15","author":"Bartholdi","year":"2001","journal-title":"Int. J. Geogr. Inf. Sci."},{"key":"ref_14","unstructured":"Dutton, G. (1997, January 7\u201310). Digital Map Generalization Using a Hierarchical Coordinate System. Proceedings of the Automated Cartography 13, Seattle, WA, USA."},{"key":"ref_15","unstructured":"Xu, B. (2006). OpenGL Programming Guide: The Official Guide to Learning OpenGL, China Machine Press. [5th ed.]. Version 2."},{"key":"ref_16","first-page":"150","article-title":"Algorithm for Generating a Digital Straight Line on a Triangular Grid","volume":"28","author":"Freeman","year":"1979","journal-title":"IEEE Comput. Soc."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"55","DOI":"10.2498\/cit.2003.02.04","article-title":"Shortest Paths in Triangular Grids with Neighbourhood Sequences","volume":"11","author":"Nagy","year":"2003","journal-title":"J. Comput. Inf. Technol."},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Sarkar, A., Biswas, A., Mondal, S., and Dutt, M. (2016). Finding Shortest Triangular Path in a Digital Object. Discrete Geometry for Computer Imagery, Springer.","DOI":"10.1007\/978-3-319-32360-2_16"},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"68","DOI":"10.1016\/j.patrec.2018.01.009","article-title":"Characterization and Generation of Straight Line Segments on Triangular Cell Grid","volume":"103","author":"Dutt","year":"2018","journal-title":"Pattern Recognit. Lett."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"357","DOI":"10.1016\/0034-4877(88)90037-7","article-title":"Duality (polarity) in Mathematics, Physics and Philosophy","volume":"25","author":"Maurin","year":"1988","journal-title":"Rep. Math. Phys."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"12","DOI":"10.1016\/j.cad.2016.04.005","article-title":"Hierarchical grid conversion","volume":"79","author":"Harrison","year":"2016","journal-title":"Comput. Aided Des."},{"key":"ref_22","first-page":"657","article-title":"Progresses of Geographical Grid Systems Researches","volume":"28","author":"Zhou","year":"2009","journal-title":"Prog. Geogr."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"973","DOI":"10.1007\/s00371-018-1525-7","article-title":"Offsetting spherical curves in vector and raster form","volume":"8","author":"Alderson","year":"2018","journal-title":"Vis. Comput."}],"container-title":["ISPRS International Journal of Geo-Information"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2220-9964\/7\/10\/391\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T15:22:45Z","timestamp":1760196165000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2220-9964\/7\/10\/391"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,9,27]]},"references-count":23,"journal-issue":{"issue":"10","published-online":{"date-parts":[[2018,10]]}},"alternative-id":["ijgi7100391"],"URL":"https:\/\/doi.org\/10.3390\/ijgi7100391","relation":{},"ISSN":["2220-9964"],"issn-type":[{"value":"2220-9964","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,9,27]]}}}