{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,18]],"date-time":"2026-03-18T09:31:31Z","timestamp":1773826291308,"version":"3.50.1"},"reference-count":29,"publisher":"MDPI AG","issue":"6","license":[{"start":{"date-parts":[[2023,6,18]],"date-time":"2023-06-18T00:00:00Z","timestamp":1687046400000},"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":["42271436"],"award-info":[{"award-number":["42271436"]}],"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":["ZR2021MD030"],"award-info":[{"award-number":["ZR2021MD030"]}],"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":["ZR2021QD148"],"award-info":[{"award-number":["ZR2021QD148"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100007129","name":"Shandong Provincial Natural Science Foundation","doi-asserted-by":"publisher","award":["42271436"],"award-info":[{"award-number":["42271436"]}],"id":[{"id":"10.13039\/501100007129","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100007129","name":"Shandong Provincial Natural Science Foundation","doi-asserted-by":"publisher","award":["ZR2021MD030"],"award-info":[{"award-number":["ZR2021MD030"]}],"id":[{"id":"10.13039\/501100007129","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100007129","name":"Shandong Provincial Natural Science Foundation","doi-asserted-by":"publisher","award":["ZR2021QD148"],"award-info":[{"award-number":["ZR2021QD148"]}],"id":[{"id":"10.13039\/501100007129","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IJGI"],"abstract":"<jats:p>Indoor space information is the basis of indoor location services such as indoor navigation, path planning, emergency evacuation, etc. Focusing on indoor navigation needs, this paper proposes a fast construction algorithm for a complex indoor space topology model based on disjoint set for the problem of lacking polygon description and topological relationship expression of indoor space entity objects in building plan drawings. Firstly, the Tarjan algorithm is used for identifying the hanging edges existing in the indoor space. Secondly, each edge is stored as two different edges belonging to two adjacent polygons that share the edge. A ring structure is introduced to judge the geometric position of walls, and then an efficient disjoint set algorithm is used to perform set merging. After that, disjoint set is queried to obtain all indoor space contours and external boundary contours, thereby the complete indoor space topological relationship at multiple levels is established. Finally, the connectivity theory of graph is used for solving the problem of a complex isolated polygon in topology information generation. The experimental results show that the proposed algorithm has generality to efficiently complete the automatic construction of a topological model for complex scenarios, and effectively acquire and organize indoor space information, thus providing a good spatial cognition mode for indoor navigation.<\/jats:p>","DOI":"10.3390\/ijgi12060248","type":"journal-article","created":{"date-parts":[[2023,6,19]],"date-time":"2023-06-19T01:59:51Z","timestamp":1687139991000},"page":"248","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Navigation-Oriented Topological Model Construction Algorithm for Complex Indoor Space"],"prefix":"10.3390","volume":"12","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6427-0785","authenticated-orcid":false,"given":"Litao","family":"Han","sequence":"first","affiliation":[{"name":"College of Geodesy and Geomatics, Shandong University of Science and Technology, Qingdao 266590, China"},{"name":"Key Laboratory of Geomatics and Digital Technology of Shandong Province, Shandong University of Science and Technology, Qingdao 266590, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hu","family":"Qiao","sequence":"additional","affiliation":[{"name":"College of Geodesy and Geomatics, Shandong University of Science and Technology, Qingdao 266590, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0804-3972","authenticated-orcid":false,"given":"Zeyu","family":"Li","sequence":"additional","affiliation":[{"name":"College of Geodesy and Geomatics, Shandong University of Science and Technology, Qingdao 266590, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mengfan","family":"Liu","sequence":"additional","affiliation":[{"name":"College of Geodesy and Geomatics, Shandong University of Science and Technology, Qingdao 266590, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pengfei","family":"Zhang","sequence":"additional","affiliation":[{"name":"College of Geodesy and Geomatics, Shandong University of Science and Technology, Qingdao 266590, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2023,6,18]]},"reference":[{"key":"ref_1","first-page":"729","article-title":"An Indoor Navigation Network Considering Walking Habits and its Generation Algorithm","volume":"51","author":"Han","year":"2022","journal-title":"Acta Geod. Cartogr. Sin."},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Schuldt, C., Shoushtari, H., Hellweg, N., and Sternberg, H. (2021). L5IN: Overview of an Indoor Navigation Pilot Project. Remote Sens., 13.","DOI":"10.3390\/rs13040624"},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"7","DOI":"10.1186\/s43020-021-00041-3","article-title":"Indoor navigation: State of the art and future trends","volume":"2","author":"Li","year":"2021","journal-title":"Satell. Navig."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"7459","DOI":"10.1109\/TII.2020.2974252","article-title":"Accurate and Efficient Indoor Pathfinding Based on Building Information Modeling Data","volume":"16","author":"Zhou","year":"2020","journal-title":"IEEE Trans. Ind. Inform."},{"key":"ref_5","first-page":"104","article-title":"Searching Approach of Boundary Building Elements Within BIM Indoor Enclosure Space Based on Topological Relationship","volume":"26","author":"Luo","year":"2019","journal-title":"Geomat. World"},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Ariono, B., Wasesa, M., and Dhewanto, W. (2022). The Drivers, Barriers, and Enablers of Building Information Modeling (BIM) Innovation in Developing Countries: Insights from Systematic Literature Review and Comparative Analysis. Buildings, 12.","DOI":"10.3390\/buildings12111912"},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"103736","DOI":"10.1016\/j.jobe.2021.103736","article-title":"Barriers to the implementation of Building Information Modelling (BIM) for facility management","volume":"46","author":"Durdyev","year":"2022","journal-title":"J. Build. Eng."},{"key":"ref_8","unstructured":"Karabulut, N. (2021). Rule-Based Semantical Enhancement of Two-Dimensional CAD\u2019s in the Context of Building Plans. [Master\u2019s Thesis, Technical University of Munich]."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"012051","DOI":"10.1088\/1757-899X\/371\/1\/012051","article-title":"BIM for existing buildings: Potential opportunities and barriers","volume":"Volume 371","author":"Hossain","year":"2018","journal-title":"IOP Conference Series: Materials Science and Engineering"},{"key":"ref_10","unstructured":"Han, L., Zhou, L., Guo, J., and Sun, X. (2021). An Algorithm of Indoor Spatial Topological Model Based on Building Plans. Bull. Surv. Mapp."},{"key":"ref_11","first-page":"249","article-title":"The Raster Algorithm on Creation of Topological Relationship of Polygons","volume":"31","author":"Wang","year":"2002","journal-title":"Acta Geod. Cartogr. Sin."},{"key":"ref_12","first-page":"66","article-title":"A Fast Algorithm of Realtimely Establishing Regions\u2019 Topological Relationsin Geographical Information System","volume":"11","author":"Fu","year":"2006","journal-title":"Information Security and Communications Privacy."},{"key":"ref_13","first-page":"785","article-title":"An Algorithm of Polygon Auto-Construction Based on Angle Changing Tendence","volume":"6","author":"Liang","year":"2005","journal-title":"J. Image Graph."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"346","DOI":"10.1111\/1755-6724.12305_17","article-title":"Polygon Growing Algorithm for Network Schematic Maps","volume":"44","author":"Zhang","year":"2015","journal-title":"Acta Geod. Cartogr. Sin."},{"key":"ref_15","unstructured":"Wang, H., Guo, Y., and Gao, P. (2020). Construction Algorithm of the Minimum Polygon Based on Quad-Tree Index. Geospat. Inf., 18."},{"key":"ref_16","first-page":"282","article-title":"Polygon Auto-Construction Based on Improved Left-Turn Algorithm","volume":"266\u2013268","author":"Liu","year":"2018","journal-title":"Bull. Surv. Mapp."},{"key":"ref_17","first-page":"70","article-title":"A Fast Algorithm of Polygon Auto-Construction Based on Left-Turn Algorithm in Coal Mine Geological Mapping","volume":"41","author":"Jia","year":"2016","journal-title":"Sci. Surv. Mapp."},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Ling, Y., Ouyang, Y., and Zhang, M. (2008, January 21\u201322). Polygon Auto-Construction Algorithm Based on Vector External Product of Virtual Arc. Proceedings of the 2008 International Symposium on Intelligent Information Technology Application Workshops, Shanghai, China.","DOI":"10.1109\/IITA.Workshops.2008.9"},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Nguyen Vinh, N., and Le, B. (2013, January 24\u201327). Constructing and modeling parcel boundaries from a set of lines for querying adjacent spatial relationships. Proceedings of the International Conference on Computational Science and Its Applications, Ho Chi Minh City, Vietnam.","DOI":"10.1007\/978-3-642-39637-3_42"},{"key":"ref_20","first-page":"37","article-title":"A Graph-Based Algorithm for Generating Polygons\u2019 Topological Relationships","volume":"19","author":"Zhou","year":"1999","journal-title":"J. Comput. Appl."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/S0010-4485(01)00171-3","article-title":"A Graph-Based Algorithm for Extracting Units and Loops from Architectural Floor Plans for a Building Evacuation Model","volume":"35","author":"Zhi","year":"2003","journal-title":"Comput.-Aided Des."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"704","DOI":"10.1080\/16864360.2014.914388","article-title":"A New Reconstruction Method for 3D Buildings from 2D Vector Floor Plan","volume":"11","author":"Zhu","year":"2014","journal-title":"Comput.-Aided Des. Appl."},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Pang, Y., Zhang, C., Zhou, L., Lin, B., and Lv, G. (2018). Extracting Indoor Space Information in Complex Building Environments. ISPRS Int. J. Geo-Inf., 7.","DOI":"10.3390\/ijgi7080321"},{"key":"ref_24","first-page":"731","article-title":"A Method of Generating Indoor Map Spatial Data Automatically from Architectural Plans","volume":"45","author":"Sun","year":"2016","journal-title":"Acta Geod. Cartogr. Sin."},{"key":"ref_25","first-page":"27","article-title":"The Basis for Generation of Topologic Information of Polygons in GIS","volume":"4","author":"Chen","year":"1996","journal-title":"Acta Geod. Cartogr. Sin."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1007\/s10009-015-0382-1","article-title":"Concurrent Depth-First Search Algorithms Based on Tarjan\u2019s Algorithm","volume":"18","author":"Lowe","year":"2016","journal-title":"Int. J. Softw. Tools Technol. Transf."},{"key":"ref_27","first-page":"269","article-title":"Satellite Mission Planning Method Based on Disjoint Set Search","volume":"7","author":"Wang","year":"2021","journal-title":"J. Command. Control."},{"key":"ref_28","first-page":"797","article-title":"Low Complexity Fuzzy Clustering Signal Sorting Algorithm Based on Union-Find Set","volume":"36","author":"Zhang","year":"2021","journal-title":"Chin. J. Radio Sci."},{"key":"ref_29","first-page":"177","article-title":"Traversable region model and its automatic extraction algorithm for indoor navigation","volume":"44","author":"You","year":"2019","journal-title":"Geomat. Inf. Sci. Wuhan Univ."}],"container-title":["ISPRS International Journal of Geo-Information"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2220-9964\/12\/6\/248\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T19:55:55Z","timestamp":1760126155000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2220-9964\/12\/6\/248"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6,18]]},"references-count":29,"journal-issue":{"issue":"6","published-online":{"date-parts":[[2023,6]]}},"alternative-id":["ijgi12060248"],"URL":"https:\/\/doi.org\/10.3390\/ijgi12060248","relation":{},"ISSN":["2220-9964"],"issn-type":[{"value":"2220-9964","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,6,18]]}}}