Generation of navigation graphs for indoor space
Authors:
- 20 May 2015
- journal article
- research article
- Published by Taylor & Francis in International Journal of Geographical Information Science
- Vol. 29 (10) , 1737-1756
Abstract
This article proposes a comprehensive approach to computing a navigation graph for an indoor space. It focuses on a single floor, but the work is easily extensible to multi-level spaces. The approach proceeds by using a formal model, based on the combinatorial map but enhanced with geometric and semantic information. The process is almost fully automatic, taking as input the building plans providing the geometric structure of the floors and semantics of the building, such as functions of interior spaces, portals, etc. One of the novel aspects in this work was the use of combinatorial maps and their duals to provide a compact formal description of the topology and connectivity of the indoor structure represented by a connected, embedded graph. While making use of existing libraries for the more routine computational geometry involved, the research develops several new algorithms, including one for computing the local kernel of a region. The process is evaluated by means of a case study using part of a university building.Keywords
Funding Information
- US National Science Foundation (IIS-0916219)
This publication has 21 references indexed in Scilit:
- Spatial models for context-aware indoor navigation systems: A surveyJournal of Spatial Information Science, 2012
- Modelling and analysing 3D buildings with a primal/dual data structureISPRS Journal of Photogrammetry and Remote Sensing, 2011
- Qualitative Spatial Reasoning for Topological Map LearningSpatial Cognition & Computation, 2010
- A Three-Dimensional Navigable Data Model to Support Emergency Response in Microspatial Built-EnvironmentsAnnals of the American Association of Geographers, 2007
- A combinatorial data model for representing topological relations among 3D geographical features in micro‐spatial environmentsInternational Journal of Geographical Information Science, 2005
- A Spatial Access-Oriented Implementation of a 3-D GIS Topological Data Model for Urban EntitiesGeoInformatica, 2004
- Sensor-Based Exploration: The Hierarchical Generalized Voronoi GraphThe International Journal of Robotics Research, 2000
- Voronoi diagrams—a survey of a fundamental geometric data structureACM Computing Surveys, 1991
- Visibility of a simple polygonComputer Vision, Graphics, and Image Processing, 1983
- An Optimal Algorithm for Finding the Kernel of a PolygonJournal of the ACM, 1979