HiVG: A hierarchical indoor visibility-based graph for navigation guidance in multi-storey buildings
Open accessAbstract
A hierarchical data model is needed in mobile navigation systems to generate route instructions on multiple levels of detail (LODs), thereby adapting to users' various information needs during navigation. In complex multi-storey indoor environments, existing hierarchical data models mainly rely on logical graphs that represent indoor cellular spaces as nodes and adjacency as edges. Due to the lack of precise geometry, however, they have limited capability to support the accurate computation of walking distance and directions, which are essential in route instructions. This article proposes a hierarchical indoor visibility-based graph (HiVG) for navigation guidance in multi-storey buildings and presents a HiVG generation algorithm. The algorithm's input is an indoor visibility graph (iVG) in which the orientations of nodes to corridor areas are represented. In the algorithm, first the functions of edges in indoor route instructions are identified, after which an edge function-based graph partitioning iteration is performed to generate each level of the HiVG. Experiments with three buildings of different geometric configurations demonstrate the potential of our HiVG generation algorithm. Furthermore, the conducted case studies show that the proposed HiVG is appropriate for generating indoor route instructions on multiple LODs.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
Cites
Community structure in social and biological networks
Girvan, M., & Newman, M. E. J. (2002) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.122653799 · Cited by 15,502 · see citing works
Finding and evaluating community structure in networks
Newman, M. E. J., & Girvan, M. (2004) · Physical Review E · doi:10.1103/physreve.69.026113 · Cited by 13,931 · see citing works
From Isovists to Visibility Graphs: A Methodology for the Analysis of Architectural Space
Turner, A., Doxa, M., O'Sullivan, D., & Penn, A. (2001) · Environment and Planning B: Planning and Design · doi:10.1068/b2684 · Cited by 969 · cited 1× · see citing works
“Conventionally, these nodes are generated based on isovist fields, namely centroids of grid cells occupying walkable areas of a floor (Franz, Mallot, & Wiener, 2005; Haumont, Debeir, & Sillion, 2003; Turner et al., 2001).”
BackgroundNetwork and Psychological Effects in Urban Movement
Hillier, B., & Iida, S. (2005) · Lecture notes in computer science · doi:10.1007/11556114_30 · Cited by 657 · see citing works
Up the down staircase: Wayfinding strategies in multi-level buildings
Hölscher, C., Meilinger, T., Vrachliotis, G., Brösamle, M., & Knauff, M. (2006) · Journal of Environmental Psychology · doi:10.1016/j.jenvp.2006.09.002 · Cited by 350 · see citing works
Elements of Good Route Directions in Familiar and Unfamiliar Environments
Lovelace, K. L., Hegarty, M., & Montello, D. R. (1999) · Lecture notes in computer science · doi:10.1007/3-540-48384-5_5 · Cited by 343 · see citing works
Proceedings of the 2016 International Conference on Management of Data
(2016) · doi:10.1145/2882903 · Cited by 273 · see citing works
Would you follow your own route description? Cognitive strategies in urban route planning
Hölscher, C., Tenbrink, T., & Wiener, J. M. (2011) · Cognition · doi:10.1016/j.cognition.2011.06.005 · Cited by 183 · see citing works
Network effects and psychological effects: a theory of urban movement
Hillier, B., & Iida, S. (2005) · UCL Discovery (University College London) · Cited by 165 · see citing works
Spatial models for context-aware indoor navigation systems: A survey
Afyouni, I., Ray, C., & Claramunt, C. (2012) · Journal of Spatial Information Science · doi:10.5311/josis.2012.4.73 · Cited by 161 · see citing works
Graph Model Based Indoor Tracking
Jensen, C. S., Lu, H. C., & Yang, B. (2009) · doi:10.1109/mdm.2009.23 · Cited by 159 · see citing works
A survey of qualitative spatial representations
Chen, J., Cohn, A., Liu, D., Wang, S.-S., Ouyang, J.-H., & Yu, Q.-Y. (2013) · Knowledge engineering review (Print) · doi:10.1017/s0269888913000350 · Cited by 139 · see citing works
Generation of navigation graphs for indoor space
Yang, L., & Worboys, M. (2015) · International Journal of Geographical Information Systems · doi:10.1080/13658816.2015.1041141 · Cited by 126 · see citing works
A Standard Indoor Spatial Data Model—OGC IndoorGML and Implementation Approaches
Kang, H.-K., & Li, K.-J. (2017) · ISPRS International Journal of Geo-Information · doi:10.3390/ijgi6040116 · Cited by 115 · see citing works
Worboys, M. (2011) · doi:10.1145/2077357.2077358 · Cited by 110 · see citing works
International Conference on Spatial Information Theory
Dieberger, A. (1995) · ACM SIGWEB Newsletter · doi:10.1145/219608.219614 · Cited by 98 · see citing works
A Hybrid Spatial Model for Representing Indoor Environments
Lorenz, B., Ohlbach, H. J., & Stoffel, E.-P. (2006) · Lecture notes in computer science · doi:10.1007/11935148_10 · Cited by 96 · see citing works
Experiential hierarchies of streets
Tomko, M., Winter, S., & Claramunt, C. (2007) · Computers Environment and Urban Systems · doi:10.1016/j.compenvurbsys.2007.03.003 · Cited by 91 · see citing works
A Model for Context-Specific Route Directions
Richter, K., & Klippel, A. (2005) · Lecture notes in computer science · doi:10.1007/978-3-540-32255-9_4 · Cited by 90 · see citing works
Self-citationVariable Granularity in Route Directions
Tenbrink, T., & Winter, S. (2009) · Spatial Cognition and Computation · doi:10.1080/13875860902718172 · Cited by 89 · see citing works
Landmark Hierarchies in Context
Winter, S., Tomko, M., Elias, B., & Sester, M. (2008) · Environment and Planning B Planning and Design · doi:10.1068/b33106 · Cited by 88 · see citing works
Simplest Instructions: Finding Easy-to-Describe Routes for Navigation
Richter, K., & Duckham, M. (2008) · Lecture notes in computer science · doi:10.1007/978-3-540-87473-7_18 · Cited by 75 · see citing works
Self-citationCORAL: Using Natural Language Generation for Navigational Assistance
Dale, R., Geldof, S., & Prost, J.-P. (2003) · Cited by 74 · see citing works
Computing Walking Distances within Buildings Using the Universal Circulation Network
Lee, J.-K., Eastman, C. M., Lee, J., et al. (2010) · Environment and Planning B Planning and Design · doi:10.1068/b35124 · Cited by 72 · see citing works
Urban granularities—a data structure for cognitively ergonomic route directions
Klippel, A., Hansen, S., Richter, K., et al. (2008) · GeoInformatica · doi:10.1007/s10707-008-0051-6 · Cited by 67 · see citing works
Self-citation(2005) · Cited by 62 · see citing works
Daniel, M., & Denis, M. (2003) · Applied Cognitive Psychology · doi:10.1002/acp.941 · Cited by 61 · see citing works
Towards a Semantic Spatial Model for Pedestrian Indoor Navigation
Stoffel, E.-P., Lorenz, B., & Ohlbach, H. J. (2007) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-76292-8_39 · Cited by 61 · see citing works
From Descriptions to Depictions: A Conceptual Framework
Vasardani, M., Timpf, S., Winter, S., & Tomko, M. (2013) · Lecture notes in computer science · doi:10.1007/978-3-319-01790-7_17 · Cited by 59 · see citing works
Towards an Indoor Level-of-Detail Model for Route Visualization
Hagedorn, B., Trapp, M., Glander, T., et al. (2009) · doi:10.1109/mdm.2009.118 · Cited by 58 · see citing works
Pragmatic Construction of Destination Descriptions for Urban Environments
Tomko, M., & Winter, S. (2009) · Spatial Cognition and Computation · doi:10.1080/13875860802427775 · Cited by 57 · see citing works
Lee, K., Lee, J., & Kwan, M. (2016) · Computers Environment and Urban Systems · doi:10.1016/j.compenvurbsys.2016.10.009 · Cited by 57 · see citing works
Architectural features and indoor evacuation wayfinding: The starting point matters
Natapov, A., Parush, A., Laufer, L., & Fisher-Gewirtzman, D. (2021) · Safety Science · doi:10.1016/j.ssci.2021.105483 · Cited by 57 · see citing works
Wayfinding choremes - conceptualizing wayfinding and route direction elements.
Klippel, A. (2004) · Künstliche Intell. · Cited by 55 · see citing works
Structural Salience of Elements of the City
Claramunt, C., & Winter, S. (2007) · Environment and Planning B Planning and Design · doi:10.1068/b32099 · Cited by 53 · see citing works
How good are these directions? Determining direction quality and wayfinding efficiency
Padgitt, A. J., & Hund, A. M. (2012) · Journal of Environmental Psychology · doi:10.1016/j.jenvp.2012.01.007 · Cited by 50 · see citing works
A dialog-driven process of generating route directions
Richter, K., Tomko, M., & Winter, S. (2008) · Computers Environment and Urban Systems · doi:10.1016/j.compenvurbsys.2008.02.002 · Cited by 48 · see citing works
Self-citationHierarchical Representations of Indoor Spaces
Richter, K., Winter, S., & Santosa, S. (2011) · Environment and Planning B Planning and Design · doi:10.1068/b37057 · Cited by 47 · see citing works
Self-citationApplying hierarchical graphs to pedestrian indoor navigation
Stoffel, E.-P., Schoder, K., & Ohlbach, H. J. (2008) · ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (SIGSPATIAL GIS) · doi:10.1145/1463434.1463499 · Cited by 47 · see citing works
A "door-to-door" path-finding approach for indoor navigation
Liu, L., & Sisi Zlatanova, B. (2011) · Research Repository (Delft University of Technology) · Cited by 46 · see citing works
Volumetric cell‐and‐portal generation
Haumont, D., Debeir, O., & Sillion, F. X. (2003) · Computer Graphics Forum · doi:10.1111/1467-8659.00677 · Cited by 46 · see citing works
A unified 3D space-based navigation model for seamless navigation in indoor and outdoor
Yan, J., Sisi Zlatanova, B., & Diakité, A. (2021) · International Journal of Digital Earth · doi:10.1080/17538947.2021.1913522 · Cited by 42 · see citing works
Visibility matters during wayfinding in the vertical
Gath-Morad, M., Thrash, T., Schicker, J., Hölscher, C., Helbing, D., & Aguilar, L. (2021) · Scientific Reports · doi:10.1038/s41598-021-98439-1 · Cited by 39 · see citing works
A human-centered semantic navigation system for indoor environments
Tsetsos, V., Anagnostopoulos, C. B., Kikiras, P. K., et al. (2005) · doi:10.1109/perser.2005.1506403 · Cited by 34 · see citing works
Direction Concepts in Wayfinding Assistance Systems
Klippel, A., Dewey, C., Knauff, M., et al. (2004) · MPG.PuRe (Max Planck Society) · Cited by 33 · see citing works
A Wearable Virtual Usher for Vision-Based Cognitive Indoor Navigation
Li, L., Xu, Q.-L., Chandrasekhar, V., Lim, J.-H., Tan, C., & Mukawa, M. (2017) · IEEE Transactions on Cybernetics · doi:10.1109/tcyb.2016.2530407 · Cited by 31 · see citing works
Generation of navigation networks for corridor spaces based on indoor visibility map
Pang, Y., Zhou, L., Lin, B., et al. (2019) · International Journal of Geographical Information Systems · doi:10.1080/13658816.2019.1664741 · Cited by 31 · see citing works
Granularity of locations referred to by place descriptions
Richter, D., Winter, S., Richter, K., et al. (2013) · Computers Environment and Urban Systems · doi:10.1016/j.compenvurbsys.2013.03.005 · Cited by 26 · see citing works
Self-citationTscheligi, M., Kranz, M., Weinberg, G., et al. (2011) · doi:10.1145/2381416 · Cited by 21 · see citing works
Route directions generation using visible landmarks
Russo, D., Sisi Zlatanova, B., & Clementini, E. (2014) · doi:10.1145/2676528.2676530 · Cited by 18 · see citing works
Semantic Trajectory Modelling in Indoor and Outdoor Spaces
Noureddine, H., Ray, C., & Claramunt, C. (2020) · Proceedings/IEEE International Conference on Mobile Data Management · doi:10.1109/mdm48529.2020.00035 · Cited by 16 · see citing works
Indoor Routing on Logical Network Using Space Semantics
Liu, L., Sisi Zlatanova, B., Li, B., et al. (2019) · ISPRS International Journal of Geo-Information · doi:10.3390/ijgi8030126 · Cited by 15 · see citing works
Zhou, Z., Weibel, R., & Huang, H. (2021) · International Journal of Geographical Information Systems · doi:10.1080/13658816.2021.1946542 · Cited by 15 · see citing works
Self-citationLearning indoor space perception
Sedlmeier, A., & Feld, S. (2018) · Journal of Location Based Services · doi:10.1080/17489725.2018.1539255 · Cited by 13 · see citing works
Generation of Adaptive Route Descriptions in Urban Environments
Dethlefs, N., Wu, Y., Kazerani, A., & Winter, S. (2011) · Spatial Cognition and Computation · doi:10.1080/13875868.2010.525272 · Cited by 12 · see citing works
Location K-anonymity in indoor spaces
Kim, J., & Li, K.-J. (2015) · GeoInformatica · doi:10.1007/s10707-015-0241-y · Cited by 12 · see citing works
A topology-based graph data model for indoor spatial-social networking
Rahimi, M., Malek, M. R., Claramunt, C., et al. (2021) · International Journal of Geographical Information Systems · doi:10.1080/13658816.2021.1912349 · Cited by 12 · see citing works
Proceedings of the 3rd ACM SIGSPATIAL International Workshop on Indoor Spatial Awareness
Kulik, L., Güting, R. H., & Lu, H. C. (2011) · doi:10.1145/2077357 · Cited by 12 · see citing works
Generating route instructions with varying levels of detail
Ziegler, J., Hussein, T., Münter, D., Hofmann, J., & Linder, T. (2011) · International Conference on Automotive User Interfaces and Interactive Vehicular Applications (AutomotiveUI) · doi:10.1145/2381416.2381422 · Cited by 11 · see citing works
A Graph Representation for Verbal Indoor Route Descriptions
Winter, S., Hamzei, E., de Weghe, N. V., & Ooms, K. (2018) · Lecture notes in computer science · doi:10.1007/978-3-319-96385-3_6 · Cited by 11 · see citing works
Turn calculations for the indoor application of the fewest turns path algorithm
Vanclooster, A., Vanhaeren, N., Viaene, P., Ooms, K., Cock, L. D., Fack, V., de Weghe, N. V., & Maeyer, P. D. (2019) · International Journal of Geographical Information Systems · doi:10.1080/13658816.2019.1630629 · Cited by 10 · see citing works
A comparison of network model creation algorithms based on the quality of wayfinding results
Park, J.-W., Goldberg, D. W., & Hammond, T. (2020) · Transactions in GIS · doi:10.1111/tgis.12632 · Cited by 7 · see citing works
Zhou, Z., Weibel, R., Fu, C., Winter, S., & Huang, H. (2021) · Spatial Cognition and Computation · doi:10.1080/13875868.2021.1959595 · Cited by 7 · see citing works
Self-citationOhlbach, H. J., & Stoffel, E.-P. (2008) · Cited by 4 · see citing works
Li, Y., Su, H., Demiryurek, U., et al. (2016) · Proceedings - ACM-SIGMOD International Conference on Management of Data · doi:10.1145/2882903.2899384 · Cited by 4
Flagged first, then by citations
Cited by
Sorted by citations
Indoor view graph: A model to capture route and configurational information
Hamzei, E., De Cock, L., Tomko, M., Van de Weghe, N., & Winter, S. (2024) · Environment and Planning B: Urban Analytics and City Science · doi:10.1177/23998083241241598 · Cited by 3 · see citing works
- Authors
- Zhou, Z., Weibel, R., Richter, K.-F., & Huang, H.
- Affiliations
- University of Zurich (CH)
- Umeå University (SE)
- Ghent University (BE)
- Corresponding author
- Zhou, Zhiyong
- Huang, Haosheng
- Venue
- Computers, Environment and Urban Systems
- Publisher
- Elsevier BV
- Published
- 2022-04
- Volume
- 93
- Pages
- 101751
- ISSN
- 0198-9715 (ISSN-L)
- OpenAlex
- W4205238063
- Cited by
- 22
- References
- 68
- Citations by year
- 2026: 2 · 2025: 6 · 2024: 6 · 2023: 5 · 2022: 3
- FWCI
- 1.35
- Type
- journal article
- Language
- en
- Open access
- hybrid
- doi.org
- Licence
- Locations
- Computers Environment and Urban Systems (publishedVersion, cc-by-nc-nd)
- Zurich Open Repository and Archive (University of Zurich) (acceptedVersion, cc-by-nc-nd)
- DiVA at Umeå University (Umeå University) (submittedVersion, other-oa)
- Ghent University Academic Bibliography (Ghent University) (submittedVersion, cc-by-nc-nd)
- Zurich Open Repository and Archive (University of Zurich) (submittedVersion, cc-by-nc-nd)
- Zurich Open Repository and Archive (University of Zurich)
- Topics
- Physical Sciences › Engineering › Automotive Engineering › Spatial Cognition and Navigation
- Physical Sciences › Engineering › Building and Construction › Urban Design and Spatial Analysis
- Physical Sciences › Engineering › Building and Construction › 3D Modeling in Geospatial Applications
- Keywords
- hierarchical graph model, indoor navigation, route directions, multi-storey buildings, levels of detail, graph partitioning, mobile navigation systems
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
