{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,3]],"date-time":"2026-07-03T23:07:16Z","timestamp":1783120036181,"version":"3.54.6"},"reference-count":31,"publisher":"MDPI AG","issue":"3","license":[{"start":{"date-parts":[[2019,3,21]],"date-time":"2019-03-21T00:00:00Z","timestamp":1553126400000},"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":["61806211"],"award-info":[{"award-number":["61806211"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["41871284"],"award-info":[{"award-number":["41871284"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IJGI"],"abstract":"<jats:p>Viewshed analysis is of great interest to location optimization, environmental planning, ecology and tourism. There have been plenty of viewshed analysis methods which are generally time-consuming and among these methods, the XDraw algorithm is one of the fastest algorithms and has been widely adopted in various applications. Unfortunately, XDraw suffers from chunk distortion which greatly lowers the accuracy, which limits the application of XDraw to a certain extent. Previous works failed to remove chunk distortion because they are unaware of the underlying contribution relationship. In this paper, we propose HiXDraw\u2014an improved XDraw algorithm free of chunk distortion. We first uncover the causation of chunk distortion from an innovative contributing perspective. Instead of recording LOS (line-of-sight) height, we use a new auxiliary grid to preserve contributing points. By preventing improper terrain data from contributing to determining the visibility, we significantly improve the accuracy of the outcome viewshed. The experimental results reveal that the error rate largely decreases by 65%. Given the same computing time, HiXDraw is more accurate than previous improvements in XDraw. To validate the removal of chunk distortion, we also present a pillar experiment.<\/jats:p>","DOI":"10.3390\/ijgi8030153","type":"journal-article","created":{"date-parts":[[2019,3,21]],"date-time":"2019-03-21T12:28:01Z","timestamp":1553171281000},"page":"153","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":17,"title":["HiXDraw: An Improved XDraw Algorithm Free of Chunk Distortion"],"prefix":"10.3390","volume":"8","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2869-8397","authenticated-orcid":false,"given":"Guangyang","family":"Zhu","sequence":"first","affiliation":[{"name":"College of Electronic Science and Technology, National University of Defense Technology, Changsha 410073, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jun","family":"Li","sequence":"additional","affiliation":[{"name":"College of Electronic Science and Technology, National University of Defense Technology, Changsha 410073, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jiangjiang","family":"Wu","sequence":"additional","affiliation":[{"name":"College of Electronic Science and Technology, National University of Defense Technology, Changsha 410073, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mengyu","family":"Ma","sequence":"additional","affiliation":[{"name":"College of Electronic Science and Technology, National University of Defense Technology, Changsha 410073, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Li","family":"Wang","sequence":"additional","affiliation":[{"name":"College of Electronic Science and Technology, National University of Defense Technology, Changsha 410073, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ning","family":"Jing","sequence":"additional","affiliation":[{"name":"College of Electronic Science and Technology, National University of Defense Technology, Changsha 410073, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"1968","published-online":{"date-parts":[[2019,3,21]]},"reference":[{"key":"ref_1","unstructured":"Franklin, W.R., Ray, C.K., and Mehta, S. (1994). Geometric algorithms for siting of air defense missile batteries. Res. Proj. Battle Columb. Div. Deliv. Order, 2756."},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Li, J., Zheng, C., and Hu, X. (2010, January 28\u201331). An Effective Method for Complete Visual Coverage Path Planning. Proceedings of the 2010 Third International Joint Conference on Computational Science and Optimization (CSO), Huangshan, China.","DOI":"10.1109\/CSO.2010.167"},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"754","DOI":"10.3390\/ijgi4020754","article-title":"HybVOR: A voronoi-based 3D GIS approach for camera surveillance network placement","volume":"4","author":"Yaagoubi","year":"2015","journal-title":"ISPRS Int. J. Geo-Inf."},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Kau\u010di\u010d, B., and Zalik, B. (2002, January 24\u201327). Comparison of viewshed algorithms on regular spaced points. Proceedings of the 18th Spring Conference on Computer Graphics, Budmerice, Slovakia.","DOI":"10.1145\/584458.584487"},{"key":"ref_5","unstructured":"Teng, Y.A., and Davis, L.S. (1992). Visibility Analysis on Digital Terrain Models and Its Parallel Implementation, University of Maryland, Center for Automation Research, Computer Vision Laboratory."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1145\/2367574.2367577","article-title":"Viewsheds on terrains in external memory","volume":"4","author":"Toma","year":"2012","journal-title":"Sigspatial Spec."},{"key":"ref_7","unstructured":"Van Kreveld, M.J. (1996). Variations on Sweep Algorithms: Efficient Computation of Extended Viewsheds and Class Intervals, Utrecht University, Information and Computing Sciences."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"171","DOI":"10.1111\/j.1467-8659.1995.cgf143_0171.x","article-title":"Visibility and Dead-Zones in Digital Terrain Maps","volume":"Volume 14","author":"Or","year":"1995","journal-title":"Computer Graphics Forum"},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Fishman, J., Haverkort, H., and Toma, L. (2009, January 4\u20136). Improved visibility computation on massive grid terrains. Proceedings of the 17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, Seattle, WD, USA.","DOI":"10.1145\/1653771.1653791"},{"key":"ref_10","unstructured":"Haverkort, H., and Toma, L. (arXiv, 2018). A Comparison of I\/O-Efficient Algorithms for Visibility Computation on Massive Grid Terrains, arXiv."},{"key":"ref_11","first-page":"5","article-title":"Computing visibility on terrains in external memory","volume":"13","author":"Haverkort","year":"2009","journal-title":"J. Exp. Algorithmics (Jea)"},{"key":"ref_12","first-page":"6","article-title":"An efficient external memory algorithm for terrain viewshed computation","volume":"2","author":"Ferreira","year":"2016","journal-title":"ACM Trans. Spat. Algorithms Syst. (TSAS)"},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"Haverkort, H., Toma, L., and Wei, B.P.F. (2013, January 5\u20138). On IO-efficient viewshed algorithms and their accuracy. Proceedings of the 21st ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, Orlando, FL, USA.","DOI":"10.1145\/2525314.2525369"},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Ferreira, C.R., Magalh\u00e3es, S.V., Andrade, M.V., Franklin, W.R., and Pompermayer, A.M. (2012, January 6\u20139). More efficient terrain viewshed computation on massive datasets using external memory. Proceedings of the 20th International Conference on Advances in Geographic Information Systems, Redondo Beach, CA, USA.","DOI":"10.1145\/2424321.2424398"},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"2304","DOI":"10.1080\/13658816.2014.918319","article-title":"An IO-efficient parallel implementation of an R2 viewshed algorithm for large terrain maps on a CUDA GPU","volume":"28","author":"Osterman","year":"2014","journal-title":"Int. J. Geogr. Inf. Sci."},{"key":"ref_16","unstructured":"Axell, T., and Frid\u00e9n, M. (2015). Comparison between GPU and Parallel CPU Optimizations in Viewshed Analysis. [Master\u2019s Thesis, Department of Computer Science and Engineering, Chalmers University of Technology]."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"363","DOI":"10.1080\/13658816.2012.692372","article-title":"A parallel computing approach to viewshed analysis of large terrain data using graphics processing units","volume":"27","author":"Zhao","year":"2013","journal-title":"Int. J. Geogr. Inf. Sci."},{"key":"ref_18","unstructured":"Ferreira, C., Andrade, M.V., Magalh\u00e3es, S.V., Franklin, W.R., and Pena, G.C. (2013). A Parallel Sweep Line Algorithm for Visibility Computation, GeoInfo."},{"key":"ref_19","first-page":"171","article-title":"A parallel algorithm for viewshed computation on grid terrains","volume":"5","author":"Ferreira","year":"2014","journal-title":"J. Inf. Data Manag."},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"Dou, W., Li, Y., and Wang, Y. (2018). A fine-granularity scheduling algorithm for parallel XDraw viewshed analysis. Earth Sci. Inform., 1\u201315.","DOI":"10.1007\/s12145-018-0339-5"},{"key":"ref_21","first-page":"87","article-title":"Generating viewsheds without using sightlines","volume":"66","author":"Wang","year":"2000","journal-title":"Photogramm. Eng. Remote Sens."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"767","DOI":"10.14358\/PERS.69.7.767","article-title":"A fast algorithm for approximate viewshed computation","volume":"69","author":"Izraelevitz","year":"2003","journal-title":"Photogramm. Eng. Remote Sens."},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Zhi, Y., Wu, L., Sui, Z., and Cai, H. (2011, January 24\u201326). An improved algorithm for computing viewshed based on reference planes. Proceedings of the IEEE 2011 19th International Conference on Geoinformatics, Shanghai, China.","DOI":"10.1109\/GeoInformatics.2011.5980948"},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"955","DOI":"10.1080\/13658810601034218","article-title":"A partition-based serial algorithm for generating viewshed on massive DEMs","volume":"21","author":"Wu","year":"2007","journal-title":"Int. J. Geogr. Inf. Sci."},{"key":"ref_25","doi-asserted-by":"crossref","unstructured":"Xu, Z.Y., and Yao, Q. (2009, January 18\u201319). A novel algorithm for viewshed based on digital elevation model. Proceedings of the Asia-Pacific Conference on Information Processing (APCIP 2009), Shenzhen, China.","DOI":"10.1109\/APCIP.2009.209"},{"key":"ref_26","unstructured":"Caraba\u00f1o, J., Sarjakoski, T., and Westerholm, J. (2015, January 4\u20136). Efficient implementation of a fast viewshed algorithm on SIMD architectures. Proceedings of the Proceedings of the 23rd Euromicro International Conference on Parallel, Disturbed, and Network-Based Processing, Turku, Finland."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1016\/j.jpdc.2015.07.001","article-title":"GPU enabled XDraw viewshed analysis","volume":"84","author":"Lewis","year":"2015","journal-title":"J. Parallel Distrib. Comput."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"511","DOI":"10.1007\/s12145-016-0263-5","article-title":"Parallel viewshed analysis on a PC cluster system using triple-based irregular partition scheme","volume":"9","author":"Song","year":"2016","journal-title":"Earth Sci. Inform."},{"key":"ref_29","doi-asserted-by":"crossref","unstructured":"Li, Y.N., Dou, W.F., and Wang, Y.L. (2017, January 13\u201316). Design and Implementation of parallel XDraw algorithm based on triangle region division. Proceedings of the 2017 16th International Symposium on Distributed Computing and Applications to Business, Engineering and Science (DCABES), AnYang, China.","DOI":"10.1109\/DCABES.2017.16"},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"2776","DOI":"10.1007\/s11227-018-2321-x","article-title":"A fault-tolerant computing method for Xdraw parallel algorithm","volume":"74","author":"Dou","year":"2018","journal-title":"J. Supercomput."},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"315","DOI":"10.1016\/j.cageo.2017.09.004","article-title":"A synthetic visual plane algorithm for visibility computation in consideration of accuracy and efficiency","volume":"109","author":"Yu","year":"2017","journal-title":"Comput. Geosci."}],"container-title":["ISPRS International Journal of Geo-Information"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2220-9964\/8\/3\/153\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T12:39:45Z","timestamp":1760186385000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2220-9964\/8\/3\/153"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,3,21]]},"references-count":31,"journal-issue":{"issue":"3","published-online":{"date-parts":[[2019,3]]}},"alternative-id":["ijgi8030153"],"URL":"https:\/\/doi.org\/10.3390\/ijgi8030153","relation":{},"ISSN":["2220-9964"],"issn-type":[{"value":"2220-9964","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,3,21]]}}}