Methodology to generate navigation models in building
Abstract
Indoor route networks models are created for use in navigation. They may be built manually, but it is better to generate them automatically, based on the building floor plans. Research has been conducted in this field in many research centers. The authors undertook to develop their own methodology for generating navigation networks, using topological neighborhood relations and semantic data. The research project focuses on one floor in a building, which consists of rooms and an expanded corridor with an obstacle in the form of an open space between the floors. The first stage of the project consisted in the segmentation of the corridor space to improve its resolution. The objective of the conducted research was to select special points (five suggestions) for the segmentation. As a result, five different segmentations of the corridor space were obtained. The aim of the second stage was to automatically generate five navigation network models. The graphically presented results have been verified against the routes generated between the selected points in the building plan. A comparison of the results with other solutions shows that the routes generated in the presented methodology are more straight-line and less zigzagging.
Keyword : indoor navigation, navigation routes in buildings, TIN, Voronoi, segmentation hallway
How to Cite
Lewandowicz, E., & Lisowski, P. (2018). Methodology to generate navigation models in building. Journal of Civil Engineering and Management, 24(8), 619-629. https://doi.org/10.3846/jcem.2018.6599
This work is licensed under a Creative Commons Attribution 4.0 International License.
References
Afyouni, I.; Cyril, R.; Christophe, C. 2012. Spatial models for context-aware indoor navigation systems: A survey, Journal of Spatial Information Science 1(4): 85–123. https://doi.org/10.5311/JOSIS.2012.4.73
Alattas, A. F.; Zlatanova, S.; Oosterom, P. V.; Chatzinikolaou, E.; Lemmen, C.; Li, K. J. 2017. Supporting indoor navigation using access rights to spaces based on combined use of IndoorGML and LADM models, ISPRS International Journal of Geo-Information 6(12): 384–416. https://doi.org/10.3390/ijgi6120384
Boeters, R.; Ohori, K. A.; Biljecki, F.; Zlatanova, S. 2015. Automatically enhancing CityGML LOD2 models with a corresponding indoor geometry, International Journal of Geographical Information Science 29(12): 2248–2268. https://doi.org/10.1080/13658816.2015.1072201
Bogusławski, P.; Mahdjoubi, L.; Zverovich, V.; Fadli, F. 2016. Automated construction of variable density navigable networks in a 3D indoor environment for emergency response, Automation in Construction 72: 115–128. https://doi.org/10.1016/j.autcon.2016.08.041
Brassel, K. E.; Reif, D. 1979. A procedure to generate Thiessen polygons, Geographical Analysis 11(3): 215–222. https://doi.org/10.1111/j.1538-4632.1979.tb00695.x
Chew, L. P. 1987. Constrained Delaunay triangulations, in Proceedings of the 3rd Annual Symposium on Computational Geometry, 1987, Waterloo, Ontario, Canada. ACM Press, 215–222. https://doi.org/10.1145/41958.41981
Cichociński, P. 2017. Modelowanie ewakuacji z budynków z wykorzystaniem analiz rastrowych [Modelling evacuation of buildings using raster analysis], Roczniki Geomatyki 15(4): 341–351.
Coleman, D. J.; Rajabifard, A.; Kolodziej, K. W. 2016. Expanding the SDI environment: comparing current spatial data infrastructure with emerging indoor location-based services, International Journal of Digital Earth 9(6): 629–647. https://doi.org/10.1080/17538947.2015.1119207
ESRI. 2018. ArcGIS online [online], [cited 10 May 2018]. Available from Internet: http://www.arcgis.com
Franz, G.; Mallot, H. A.; Wiener, J. M. 2005. Graph-based models of space in architecture and cognitive science – A comparative analysis, in Proceedings of 17th International Conference on Systems Research, Informatics and Cybernetics (INTERSYMP-2005), 1–7 August 2005, Baden-Baden, Germany.
Gao, S.; Krogstie, J.; Thingstad, T.; Tran, H. 2017. An empirical study of the adoption of an indoor location-based service: Finding reading rooms, International Journal of Technology and Human Interaction 13(2): 70–88. https://doi.org/10.4018/IJTHI.2017040105
Hahmann, S.; Jakob, M.; Bernd, R.; Lauer, J.; Zipf, A. 2018. Routing through open spaces – a performance comparison of algorithms, Geo-spatial Information Science 21(3): 247–256. https://doi.org/10.1080/10095020.2017.1399675
Hilsenbeck, S.; Bobkov, D.; Schroth, G.; Huitl, R.; Steinbacg, E. 2014. Graph-based data fusion of pedometer and WiFi measurements for mobile indoor positioning, in Proceedings of the 2014 ACM International Joint Conference on Pervasive and Ubiquitous Computing, 2014, 147–158. https://doi.org/10.1145/2632048.2636079
Joan-Arinyo, R.; Pérez-Vidal, L.; Gargallo-Monllau, E. 1997. An adaptive algorithm to compute the medial axis transform of 2-d polygonal domains, in D. Roller, P. Brunet (Eds.). CAD systems development. Tools and methods. Berlin Heidelberg: Springer, 283–298. https://doi.org/10.1007/978-3-642-60718-9_20
Kaliszczuk, L. 2013. Wizualizacja 3D budynku Wydziału Geodezji i Gospodarki przestrzennej UWM w Olsztynie w Google Earth [3D visualization of a building of the Faculty of Geodesy and Spatial management UWM in Olsztyn in Google Earth]: Diploma thesis. Katedra Geodezji Szczegółowej, UWM Olsztyn.
Krūminaitė, M. 2014. Space subdivision for indoor navigation: Master thesis. Delft University of Technology.
Lee, J. 2004. A spatial access-oriented implementation of a 3-D GIS topological data model for urban entities, Geoinformatica 8(3): 237–264. https://doi.org/10.1023/B:GEIN.0000034820.93914.d0
Lee, J. 2007. A three-dimensional navigable data model to support emergency response in microspatial built-environments, Annals of the Association of American Geographers 97(3): 512–529. https://doi.org/10.1111/j.1467-8306.2007.00561.x
Lewandowicz, E. 2014. Network models of 2D and 3D cadastral data. Selection and peer-review under responsibility of the Vilnius Gediminas Technical University.
Lewandowicz, E. 2015. 3D cadastre, building 3D models with navigation network, in New challenges for land information systems in the light of European standards. Croatian Information Technology Society, GIS Forum. Zagreb, Croatia.
Lewandowicz, E.; Packa, A.; Kondratowicz, S. 2013. Przekształcanie danych topologicznych, geometrycznych i atrybutowych GIS do modeli analitycznych [Conversion topological geometric and attribute GIS data to analytical models], Acta Universitatis Lodziensis, Folia Geographica Socio-Oekonomica 14: 33–44.
Lin, Z.; Xu, Z.; Hu, D.; Li, W. 2017. Hybrid spatial data model for indoor space: Combined topology and grid, ISPRS International Journal of Geo-Information 6(11): 343. https://doi.org/10.3390/ijgi6110343
Lisowski, P.; Lewandowicz, E. 2016. Przetwarzanie i wizualizacje zapisów sąsiedztwa danych katastralnych w strukturach grafowych [Processing and visualization of neighborhood cadastral data notations in the graph structures], Roczniki Geomatyki 14(4): 487–496.
Lisowski, P.; Lewandowicz, E. 2018. Metodyka zapisu topologicznego modelu struktur katastralnych w grafowych bazach danych [Methodology of storing topological models of cadastral structures in graph databases], Roczniki Geomatyki 16(1): 45–54.
Liu, L.; Zlatanova, S. 2015. An approach for indoor path computation among obstacles that considers user dimension, ISPRS International Journal of Geo-Information 4(4): 2821–2841. https://doi.org/10.3390/ijgi4042821
Mortari, F.; Zlatanova, S.; Liu, L.; Clementini, E. 2014. Improved geometric network model (IGNM): A novel approach for deriving connectivity graphs for indoor navigation, ISPRS Annals of the Photogrammetry, Remote Sensing and Spatial Information Sciences, Vol. II-4.
Prinz, F. B.; Cern, J.-H. 1988. Geometric abstractions using medial axis transformation. Pittsburgh: Carnegie Mellon University, Research Showcase @ CMU.
Staats, B. R.; Diakit, A. A.; Voute, R. L.; Zlatanova, S. 2017. Automatic generation of indoor navigable space using a point cloud and its scanner trajectory, ISPRS Annals of the Photogrammetry, Remote Sensing and Spatial Information Sciences, Vol. IV-2/W4.
Stoffel, E. P.; Lorenz, B.; Ohlbach, H. J. 2007. Towards a semantic spatial model for pedestrian indoor navigation, in Advances in Conceptual Modeling – Foundations and Applications. Lecture Notes in Computer Science, Vol. 4802. Berlin, Heidelberg: Springer, 328–337. https://doi.org/10.1007/978-3-540-76292-8_39
Tang, S. J.; Zhu, Q.; Wang, W. W.; Zhang, Y. T. 2015. Automatic topology derivation from IFC building model for in-door intelligent navigation, in Remote Sensing and Spatial Information Sciences, Vol. XL-4/W5.
Teo, T. A.; Cho, K. H. 2016. BIM-oriented indoor network model for indoor and outdoor combined route planning, Advanced Engineering Informatics 30(3): 268–282. https://doi.org/10.1016/j.aei.2016.04.007
Wallgrün, J. O. 2004. Autonomous construction of hierarchical Voronoi-based route graph representations, in Proceedings of the 4th International Conference on Spatial Cognition: Reasoning Action, Interaction, 2004, 413–433.
Wei, L.; Chen, Y. H.; Li, L.; Fu, H. M.; Wei, L. 2012. Application of Thiessen polygon algorithm in cellular network simulation system, Advanced Materials Research 532–533: 1851–1856. https://doi.org/10.4028/www.scientific.net/AMR.532-533.1851
Whiting, E. J. 2006. Geometric, topological & semantic analysis of multi-building floor plan data: Doctoral dissertation. Massachusetts Institute of Technology, USA.
Xu, M.; Hijazi, I.; Mebarki, A.; Meouche, R. E.; Abunemeh, M. 2016b. Indoor guided evacuation: TIN for graph generation and crowd evacuation, Geomatics, Natural Hazards and Risk 7(Sup 1): 47–56. https://doi.org/10.1080/19475705.2016.1181343
Xu, M.; Wei, S.; Zlatanova, S. 2016a. An indoor navigation approach considering obstacles and space subdivision of 2D plan, in ISPRS International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, XLI-B4, 339–346.
Yan, J.; Zlatanowa, S.; Diakite, A. 2018. Seamless pedestrian navigation in indoor/outdoor large spaces with no clear patterns for movement. 3D geoinformation: PhD research proposal. Delft University of Technology.
Yang, L.; Sun, X.; Zhu, A.; Chi, T. 2017. A multiple ant colony optimization algorithm for indoor room optimal spatial allocation, ISPRS International Journal of Geo-Information 6(6): 161. https://doi.org/10.3390/ijgi6060161
Yang, L.; Worboys, M. F. 2015. Generation of navigation graphs for indoor space, International Journal of Geographical Information Science 29: 1737–1756. https://doi.org/10.1080/13658816.2015.1041141
Zhu, Q.; Li, Y.; Xiong, Q.; Zlatanova, S.; Ding, Y.; Zhang, Y.; Zhou, Y. 2016. Indoor multi-dimensional location GML and its application for ubiquitous indoor location services, ISPRS International Journal of Geo-Information 5(12): 220. https://doi.org/10.3390/ijgi5120220
Alattas, A. F.; Zlatanova, S.; Oosterom, P. V.; Chatzinikolaou, E.; Lemmen, C.; Li, K. J. 2017. Supporting indoor navigation using access rights to spaces based on combined use of IndoorGML and LADM models, ISPRS International Journal of Geo-Information 6(12): 384–416. https://doi.org/10.3390/ijgi6120384
Boeters, R.; Ohori, K. A.; Biljecki, F.; Zlatanova, S. 2015. Automatically enhancing CityGML LOD2 models with a corresponding indoor geometry, International Journal of Geographical Information Science 29(12): 2248–2268. https://doi.org/10.1080/13658816.2015.1072201
Bogusławski, P.; Mahdjoubi, L.; Zverovich, V.; Fadli, F. 2016. Automated construction of variable density navigable networks in a 3D indoor environment for emergency response, Automation in Construction 72: 115–128. https://doi.org/10.1016/j.autcon.2016.08.041
Brassel, K. E.; Reif, D. 1979. A procedure to generate Thiessen polygons, Geographical Analysis 11(3): 215–222. https://doi.org/10.1111/j.1538-4632.1979.tb00695.x
Chew, L. P. 1987. Constrained Delaunay triangulations, in Proceedings of the 3rd Annual Symposium on Computational Geometry, 1987, Waterloo, Ontario, Canada. ACM Press, 215–222. https://doi.org/10.1145/41958.41981
Cichociński, P. 2017. Modelowanie ewakuacji z budynków z wykorzystaniem analiz rastrowych [Modelling evacuation of buildings using raster analysis], Roczniki Geomatyki 15(4): 341–351.
Coleman, D. J.; Rajabifard, A.; Kolodziej, K. W. 2016. Expanding the SDI environment: comparing current spatial data infrastructure with emerging indoor location-based services, International Journal of Digital Earth 9(6): 629–647. https://doi.org/10.1080/17538947.2015.1119207
ESRI. 2018. ArcGIS online [online], [cited 10 May 2018]. Available from Internet: http://www.arcgis.com
Franz, G.; Mallot, H. A.; Wiener, J. M. 2005. Graph-based models of space in architecture and cognitive science – A comparative analysis, in Proceedings of 17th International Conference on Systems Research, Informatics and Cybernetics (INTERSYMP-2005), 1–7 August 2005, Baden-Baden, Germany.
Gao, S.; Krogstie, J.; Thingstad, T.; Tran, H. 2017. An empirical study of the adoption of an indoor location-based service: Finding reading rooms, International Journal of Technology and Human Interaction 13(2): 70–88. https://doi.org/10.4018/IJTHI.2017040105
Hahmann, S.; Jakob, M.; Bernd, R.; Lauer, J.; Zipf, A. 2018. Routing through open spaces – a performance comparison of algorithms, Geo-spatial Information Science 21(3): 247–256. https://doi.org/10.1080/10095020.2017.1399675
Hilsenbeck, S.; Bobkov, D.; Schroth, G.; Huitl, R.; Steinbacg, E. 2014. Graph-based data fusion of pedometer and WiFi measurements for mobile indoor positioning, in Proceedings of the 2014 ACM International Joint Conference on Pervasive and Ubiquitous Computing, 2014, 147–158. https://doi.org/10.1145/2632048.2636079
Joan-Arinyo, R.; Pérez-Vidal, L.; Gargallo-Monllau, E. 1997. An adaptive algorithm to compute the medial axis transform of 2-d polygonal domains, in D. Roller, P. Brunet (Eds.). CAD systems development. Tools and methods. Berlin Heidelberg: Springer, 283–298. https://doi.org/10.1007/978-3-642-60718-9_20
Kaliszczuk, L. 2013. Wizualizacja 3D budynku Wydziału Geodezji i Gospodarki przestrzennej UWM w Olsztynie w Google Earth [3D visualization of a building of the Faculty of Geodesy and Spatial management UWM in Olsztyn in Google Earth]: Diploma thesis. Katedra Geodezji Szczegółowej, UWM Olsztyn.
Krūminaitė, M. 2014. Space subdivision for indoor navigation: Master thesis. Delft University of Technology.
Lee, J. 2004. A spatial access-oriented implementation of a 3-D GIS topological data model for urban entities, Geoinformatica 8(3): 237–264. https://doi.org/10.1023/B:GEIN.0000034820.93914.d0
Lee, J. 2007. A three-dimensional navigable data model to support emergency response in microspatial built-environments, Annals of the Association of American Geographers 97(3): 512–529. https://doi.org/10.1111/j.1467-8306.2007.00561.x
Lewandowicz, E. 2014. Network models of 2D and 3D cadastral data. Selection and peer-review under responsibility of the Vilnius Gediminas Technical University.
Lewandowicz, E. 2015. 3D cadastre, building 3D models with navigation network, in New challenges for land information systems in the light of European standards. Croatian Information Technology Society, GIS Forum. Zagreb, Croatia.
Lewandowicz, E.; Packa, A.; Kondratowicz, S. 2013. Przekształcanie danych topologicznych, geometrycznych i atrybutowych GIS do modeli analitycznych [Conversion topological geometric and attribute GIS data to analytical models], Acta Universitatis Lodziensis, Folia Geographica Socio-Oekonomica 14: 33–44.
Lin, Z.; Xu, Z.; Hu, D.; Li, W. 2017. Hybrid spatial data model for indoor space: Combined topology and grid, ISPRS International Journal of Geo-Information 6(11): 343. https://doi.org/10.3390/ijgi6110343
Lisowski, P.; Lewandowicz, E. 2016. Przetwarzanie i wizualizacje zapisów sąsiedztwa danych katastralnych w strukturach grafowych [Processing and visualization of neighborhood cadastral data notations in the graph structures], Roczniki Geomatyki 14(4): 487–496.
Lisowski, P.; Lewandowicz, E. 2018. Metodyka zapisu topologicznego modelu struktur katastralnych w grafowych bazach danych [Methodology of storing topological models of cadastral structures in graph databases], Roczniki Geomatyki 16(1): 45–54.
Liu, L.; Zlatanova, S. 2015. An approach for indoor path computation among obstacles that considers user dimension, ISPRS International Journal of Geo-Information 4(4): 2821–2841. https://doi.org/10.3390/ijgi4042821
Mortari, F.; Zlatanova, S.; Liu, L.; Clementini, E. 2014. Improved geometric network model (IGNM): A novel approach for deriving connectivity graphs for indoor navigation, ISPRS Annals of the Photogrammetry, Remote Sensing and Spatial Information Sciences, Vol. II-4.
Prinz, F. B.; Cern, J.-H. 1988. Geometric abstractions using medial axis transformation. Pittsburgh: Carnegie Mellon University, Research Showcase @ CMU.
Staats, B. R.; Diakit, A. A.; Voute, R. L.; Zlatanova, S. 2017. Automatic generation of indoor navigable space using a point cloud and its scanner trajectory, ISPRS Annals of the Photogrammetry, Remote Sensing and Spatial Information Sciences, Vol. IV-2/W4.
Stoffel, E. P.; Lorenz, B.; Ohlbach, H. J. 2007. Towards a semantic spatial model for pedestrian indoor navigation, in Advances in Conceptual Modeling – Foundations and Applications. Lecture Notes in Computer Science, Vol. 4802. Berlin, Heidelberg: Springer, 328–337. https://doi.org/10.1007/978-3-540-76292-8_39
Tang, S. J.; Zhu, Q.; Wang, W. W.; Zhang, Y. T. 2015. Automatic topology derivation from IFC building model for in-door intelligent navigation, in Remote Sensing and Spatial Information Sciences, Vol. XL-4/W5.
Teo, T. A.; Cho, K. H. 2016. BIM-oriented indoor network model for indoor and outdoor combined route planning, Advanced Engineering Informatics 30(3): 268–282. https://doi.org/10.1016/j.aei.2016.04.007
Wallgrün, J. O. 2004. Autonomous construction of hierarchical Voronoi-based route graph representations, in Proceedings of the 4th International Conference on Spatial Cognition: Reasoning Action, Interaction, 2004, 413–433.
Wei, L.; Chen, Y. H.; Li, L.; Fu, H. M.; Wei, L. 2012. Application of Thiessen polygon algorithm in cellular network simulation system, Advanced Materials Research 532–533: 1851–1856. https://doi.org/10.4028/www.scientific.net/AMR.532-533.1851
Whiting, E. J. 2006. Geometric, topological & semantic analysis of multi-building floor plan data: Doctoral dissertation. Massachusetts Institute of Technology, USA.
Xu, M.; Hijazi, I.; Mebarki, A.; Meouche, R. E.; Abunemeh, M. 2016b. Indoor guided evacuation: TIN for graph generation and crowd evacuation, Geomatics, Natural Hazards and Risk 7(Sup 1): 47–56. https://doi.org/10.1080/19475705.2016.1181343
Xu, M.; Wei, S.; Zlatanova, S. 2016a. An indoor navigation approach considering obstacles and space subdivision of 2D plan, in ISPRS International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, XLI-B4, 339–346.
Yan, J.; Zlatanowa, S.; Diakite, A. 2018. Seamless pedestrian navigation in indoor/outdoor large spaces with no clear patterns for movement. 3D geoinformation: PhD research proposal. Delft University of Technology.
Yang, L.; Sun, X.; Zhu, A.; Chi, T. 2017. A multiple ant colony optimization algorithm for indoor room optimal spatial allocation, ISPRS International Journal of Geo-Information 6(6): 161. https://doi.org/10.3390/ijgi6060161
Yang, L.; Worboys, M. F. 2015. Generation of navigation graphs for indoor space, International Journal of Geographical Information Science 29: 1737–1756. https://doi.org/10.1080/13658816.2015.1041141
Zhu, Q.; Li, Y.; Xiong, Q.; Zlatanova, S.; Ding, Y.; Zhang, Y.; Zhou, Y. 2016. Indoor multi-dimensional location GML and its application for ubiquitous indoor location services, ISPRS International Journal of Geo-Information 5(12): 220. https://doi.org/10.3390/ijgi5120220