An indoor navigation network considering walking habits and its generation algorithm

doi:10.11947/j.AGCS.2022.20210065

Abstract

Abstract: An indoor navigation network is the basis of indoor path planning and navigation. The existing indoor navigation networks have some shortcomings such as unreasonable topological connection structure and unnatural geometric shape of generated paths. Accordingly, a novel indoor navigation network and its automatic generation algorithm are proposed in this paper according to the "short cut" behavioral characteristics formed by human beings for a long time and the security need of collision avoidance. The navigation network divides the indoor passable space into ordinary rooms and corridors. The network in one ordinary room is mapped as straight lines connecting the room node and the door nodes, and the corridor space with complex shape is subdivided into narrow corridor spaces and open corridor spaces according to spatial scale and convexity. The central axis of each narrow corridor space is taken as its corresponding route, and a complete graph is formed by connecting all door nodes and hatchway nodes in each open corridor space. Finally, door nodes are connected to the corridor route to form a complete indoor navigation network. The experimental results show that the proposed network model and its generating algorithm can reasonably partition the complex passable space according to indoor space scale and generate the navigation network structure consistent with spatial characteristics, which makes the shape of planned shortest paths more in line with human being's walking characteristics.

Key words: indoor navigation network, building plans, indoor topological model, behavioral characteristics, indoor navigation

CLC Number:

P208

HAN Litao, ZHOU Lijuan, GONG Cheng, ZHANG Aiguo. An indoor navigation network considering walking habits and its generation algorithm[J]. Acta Geodaetica et Cartographica Sinica, 2022, 51(5): 729-738.

References 25

[1]	XIONG Qing, ZHU Qing, DU Zhiqiang, et al. Free multi-floor indoor space extraction from complex 3D building models[J]. Earth Science Informatics, 2017(10):69-83. DOI:10.1007/s12145-016-0279-x.
[2]	PANG Yueyong, ZHANG Chi, ZHOU Liangchen, et al. Extracting indoor space information in complex building environments[J]. International Journal of Geo-information, 2018, 7(8):321. DOI:10.3390/ijgi7080321.
[3]	刘涛,张星,李清泉,等. 顾及地标可视性的室内导航路径优化算法[J].武汉大学学报(信息科学版), 2017, 42(1):43-48.DOI:10.13203/j.whugis20150387. LIU Tao, ZHANG Xing, LI Qingquan, et al. An indoor pedestrian route planning algorithm based on landmark visibility[J]. Geomatics and information science of wuhan university,2017,42(1):43-48. DOI:10.13203/j.whugis20150387.
[4]	游天,王光霞,吕晓华,等. 一种面向室内导航的通行区域模型及其自动提取算法[J].武汉大学学报(信息科学版),2019,44(2):177-184. DOI:10.13203/j.whugis20170056. YOU Tian, WANG Guangxia, LV Xiaohua, et al.Traversable region model and its automatic extraction algorithm for indoor navigation[J]. Geomatics and Information Science of Wuhan University, 2019,44(2):177-184. DOI:10.13203/j.whugis20170056.
[5]	XIONG Qing, ZHU Qing, DU Zhiqiang, et al. A dynamic indoor field model for emergency evacuation simulation[J]. ISPRS International Journal of Geo-Information. 2017, 6(4):104. DOI:10.3390/ijgi6040104.
[6]	赵江洪, 董岩, 危双丰, 等. 室内导航路网提取研究进展[J]. 测绘科学, 2020, 45(12):45-54, 76. ZHAO Jianghong, DONG Yan, WEI Shuangfeng, et al. Review of the research progresses on extraction of indoor navigation network[J]. Science of Surveying and Mapping, 2020, 45(12):45-54, 76.
[7]	MORTARI F, CLEMENTINI E, ZLATANOVA S, et al. An indoor navigation model and its network extraction[J]. Applied Geomatics, 2019, 11(4):413-427. DOI:10.1007/s12518-019-00273-8.
[8]	武恩超,张恒才,吴升.基于中轴变换算法的室内外一体化导航路网自动生成方法[J]. 地球信息科学学报,2018, 20(6):730-737. DOI:10.12082/dqxxkx.2018.170582. WU Enchao, ZHANG Hengcai, WU Sheng. Automatic generation method of indoor and outdoor integrated navigation network based on medial axis transform algorithm[J]. Journal of Geo-information Science, 2018, 20(6):730-737. DOI:10.12082/dqxxkx.2018.170582.
[9]	LEE J. A spatial access-oriented implementation of a 3D-GIS topological data model for urban entities[J]. Geoinformatica, 2004, 8(3):237-264. DOI:10.1023/B:GEIN.0000034820.93914.d0.
[10]	HAN Litao, ZHANG Teng, WANG Zhenyong. The design and development of indoor 3D routing system[J]. Journal of Software, 2014,9(5):1223-1228. DOI:10.4304/jsw.9.5.1223-1228.
[11]	BOGUSLAWSKI P, MAHDJOUBI L, ZVEROVICH V, et al. Automated construction of variable density navigable networks in a 3D indoor environment for emergency response[J]. Automation in Construction, 2016, 72:115-128.
[12]	TOMÁS L, WESLEY M A. An algorithm for planning collision free paths among polyhedral obstacles[J]. Communications of the ACM, 1979, 22(10):560-570. DOI:10.1145/359156.359164.
[13]	LIU L, ZLATANOVA S. A "door-to-door" path-finding approach for indoor navigation[C]//Proceedings of gi4DM 2011:Geo-Information for Disaster Management. Antalya, Turkey:ISPRS, 2011. DOI:http://repository.tudelft.nl/assets/uuid:de84a1c2-6596-4888-a0dd.
[14]	PANG Yueyong, ZHOU Liangchen, LIN Bingxian, et al. Generation of navigation networks for corridor spaces based on indoor visibility map[J]. International Journal of Geographical Information Science, 2019, 34(1):1-25. DOI:10.1080/13658816.2019.1664741.
[15]	YANG L, WORBOYS M. Generation of navigation graphs for indoor space[J]. International Journal of Geographical Information Science. 2015,5:1-21. DOI:10.1080/13658816.2015.1041141.
[16]	MAHESHWARI N, RAJAN K S. A semantic model to define indoor space in context of emergency evacuation[J]. Remote Sensing and Spatial Information Sciences, 2016, XLI-B4:313-318. DOI:10.5194/isprsarchives-XLI-B4-313-2016.
[17]	DIAKITÉ A, ZLATANOVA S. Spatial subdivision of complex indoor environments for 3D indoor navigation[J]. International Journal of Geographical Information Science,2018,32(2):213-235. DOI:10.1080/13658816.2017.1376066.
[18]	傅梦颖,张恒才,王培晓,等.基于移动对象轨迹的室内导航网络构建方法[J].地球信息科学学报, 2019, 21(5):631-640. DOI:10.12082/dqxxkx.2019.190024. FU Mengying, ZHANG Hengcai, WANG Peixiao, et al. A method for constructing indoor navigation networks based on moving object trajectory[J]. Journal of Geo-information Science, 2019, 21(5):631-640. DOI:10.12082/dqxxkx.2019.190024.
[19]	朱丽, 檀文迪. 基于行为习性的城市外部空间设计[J]. 河北联合大学学报(社会科学版), 2015,15(2):44-47. DOI:10.3969/j.issn.2095-2708.2015.02.010. ZHU Li, TAN Wendi. City of external space design based on behavior[J]. Journal of Hebei United University (Social Science Edition), 2015,15(2):44-47. DOI:10.3969/j.issn.2095-2708.2015.02.010.
[20]	胡正凡, 林玉莲. 环境心理学:环境——行为研究及其设计应用[M]. 4版. 北京:中国建筑工业出版社, 2018. HU Zhengfan, LIN Yulian. Environmental psychology:environment behavior research and its design application[M]. 4th ed. Beijing:China Architecture & Building Press, 2018.
[21]	孙卫新,王光霞,张锦明,等.源自建筑平面图的室内地图空间数据自动生成方法[J]. 测绘学报,2016,45(6):731-739. DOI:10.11947/j.AGCS.2016.20150658. SUN Weixin, WANG Guangxia, ZHANG Jinming, et al. A method of generating indoor map spatial data automatically from architectural plans[J]. Acta Geodaetica et Cartographica Sinica,2016,45(6):731-739. DOI:10.11947/j.AGCS.2016.20150658.
[22]	韩李涛, 周丽娟, 郭佳, 等. 基于建筑平面图的室内空间拓扑模型自动生成算法[J]. 测绘通报, 2021(3):75-80.DOI:10.13474/j.cnki.11-2246.2021.0081. HAN Litao, ZHOU Lijuan, Guo Jia, et al. An algorithm of indoor spatial topological model based on building plans[J]. Bulletin of Surveying and Mapping, 2021(3):75-80.DOI:10.13474/j.cnki.11-2246.2021.0081.
[23]	陈亚婷, 严泰来, 朱德海. 基于辛普森面积的多边形凹凸性识别算法[J]. 地理与地理信息科学, 2010, 26(6):28-30, 55. CHEN Yating, YAN Tailai, ZHU Dehai. An algorithm for identifying convex-concave vertices of polygon based on Simpson formula[J]. Geography and Geo-Information Science, 2010, 26(6):28-30, 55.
[24]	CHEN Zhanlong, YE Wen. The precise representation model of topological relations of complex planar objects[J]. Journal of Geodesy and Geoinformation Science, 2019, 2(3):18-30.DOI:10.11947/j.JGGS.2019.0303.
[25]	王行风,汪云甲.一种顾及拓扑关系的室内三维模型组织和调度方法[J].武汉大学学报(信息科学版),2017,09(1):35-42. DOI:10.13203/j.whugis20140798. WANG Xingfeng, WANG Yunjia. study on organization and scheduling of indoor three-dimensional geometric model based on spatial topological relation[J]. Geomatics and Information Science of Wuhan University, 2017,09(1):35-42. DOI:10.13203/j.whugis20140798.