Approved

OGC Standard

OGC® IndoorGML 1.1
Jiyeong Lee, Ki-Joune Li, Sisi Zlatanova, Thomas H. Kolbe, Claus Nagel, Thomas Becker, Hye-Young Kang Editor
Version: 1.1
Additional Formats: XML PDF DOC
OGC Standard

Approved

Document number:19-011r4
Document type:OGC Standard
Document subtype:Implementation
Document stage:Approved
Document language:English

 


License Agreement

Permission is hereby granted by the Open Geospatial Consortium, (“Licensor”), free of charge and subject to the terms set forth below, to any person obtaining a copy of this Intellectual Property and any associated documentation, to deal in the Intellectual Property without restriction (except as set forth below), including without limitation the rights to implement, use, copy, modify, merge, publish, distribute, and/or sublicense copies of the Intellectual Property, and to permit persons to whom the Intellectual Property is furnished to do so, provided that all copyright notices on the intellectual property are retained intact and that each person to whom the Intellectual Property is furnished agrees to the terms of this Agreement.

If you modify the Intellectual Property, all copies of the modified Intellectual Property must include, in addition to the above copyright notice, a notice that the Intellectual Property includes modifications that have not been approved or adopted by LICENSOR.

THIS LICENSE IS A COPYRIGHT LICENSE ONLY, AND DOES NOT CONVEY ANY RIGHTS UNDER ANY PATENTS THAT MAY BE IN FORCE ANYWHERE IN THE WORLD. THE INTELLECTUAL PROPERTY IS PROVIDED “AS IS”, WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE, AND NONINFRINGEMENT OF THIRD PARTY RIGHTS. THE COPYRIGHT HOLDER OR HOLDERS INCLUDED IN THIS NOTICE DO NOT WARRANT THAT THE FUNCTIONS CONTAINED IN THE INTELLECTUAL PROPERTY WILL MEET YOUR REQUIREMENTS OR THAT THE OPERATION OF THE INTELLECTUAL PROPERTY WILL BE UNINTERRUPTED OR ERROR FREE. ANY USE OF THE INTELLECTUAL PROPERTY SHALL BE MADE ENTIRELY AT THE USER’S OWN RISK. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR ANY CONTRIBUTOR OF INTELLECTUAL PROPERTY RIGHTS TO THE INTELLECTUAL PROPERTY BE LIABLE FOR ANY CLAIM, OR ANY DIRECT, SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES, OR ANY DAMAGES WHATSOEVER RESULTING FROM ANY ALLEGED INFRINGEMENT OR ANY LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR UNDER ANY OTHER LEGAL THEORY, ARISING OUT OF OR IN CONNECTION WITH THE IMPLEMENTATION, USE, COMMERCIALIZATION OR PERFORMANCE OF THIS INTELLECTUAL PROPERTY.

This license is effective until terminated. You may terminate it at any time by destroying the Intellectual Property together with all copies in any form. The license will also terminate if you fail to comply with any term or condition of this Agreement. Except as provided in the following sentence, no such termination of this license shall require the termination of any third party end-user sublicense to the Intellectual Property which is in force as of the date of notice of such termination. In addition, should the Intellectual Property, or the operation of the Intellectual Property, infringe, or in LICENSOR’s sole opinion be likely to infringe, any patent, copyright, trademark or other right of a third party, you agree that LICENSOR, in its sole discretion, may terminate this license without any compensation or liability to you, your licensees or any other party. You agree upon termination of any kind to destroy or cause to be destroyed the Intellectual Property together with all copies in any form, whether held by you or by any third party.

Except as contained in this notice, the name of LICENSOR or of any other holder of a copyright in all or part of the Intellectual Property shall not be used in advertising or otherwise to promote the sale, use or other dealings in this Intellectual Property without prior written authorization of LICENSOR or such copyright holder. LICENSOR is and shall at all times be the sole entity that may authorize you or any third party to use certification marks, trademarks or other special designations to indicate compliance with any LICENSOR standards or specifications. This Agreement is governed by the laws of the Commonwealth of Massachusetts. The application to this Agreement of the United Nations Convention on Contracts for the International Sale of Goods is hereby expressly excluded. In the event any provision of this Agreement shall be deemed unenforceable, void or invalid, such provision shall be modified so as to make it valid and enforceable, and as so modified the entire Agreement shall remain in full force and effect. No decision, action or inaction by LICENSOR shall be construed to be a waiver of any rights or remedies available to it.

None of the Intellectual Property or underlying information or technology may be downloaded or otherwise exported or reexported in violation of U.S. export laws and regulations. In addition, you are responsible for complying with any local laws in your jurisdiction which may impact your right to import, export or use the Intellectual Property, and you represent that you have complied with any regulations or registration procedures required by applicable law to make this license enforceable.

Suggested additions, changes and comments on this standard are welcome and encouraged. Such suggestions may be submitted using the online change request form on OGC web site: http://portal.opengeospatial.org/public_ogc/change_request.php

 



I.  Abstract

This OGC® IndoorGML standard specifies an open data model and XML schema of indoor spatial information. IndoorGML is an application schema of OGC® GML 3.2.1. While there are several 3D building modelling standards such as CityGML, KML, and IFC, which deal with interior space of buildings from geometric, cartographic, and semantic viewpoints, IndoorGML intentionally focuses on modeling indoor spaces for navigation purposes.

II.  Keywords

The following are keywords to be used by search engines and document catalogues.

ogcdoc, ogc documents, indoorgml, gml, indoor, navigation


III.  Preface

The goal of IndoorGML is to represent and allow for exchange of geoinformation that is required to build and operate indoor navigation systems. Several standards such as CityGML[10,28], KML[30], and IFC[31] have been published to describe 3D geometry and semantics of buildings not only for outdoor space but also indoor space, but they lack important features that are required by indoor navigation applications. This standard aims to provide complementary and additional encoding features for indoor spatial information required for indoor navigation.

This OGC standard consists of two components: 1) a core data model to describe topological connectivity and different contexts (e.g. topographic space and sensor space) of indoor space, and 2) a data model for navigation in indoor space.

IndoorGML covers geometric and semantic properties relevant for indoor navigation in an indoor space. These spaces may differ from the spaces described by other standards such as CityGML, KML, and IFC. In this respect, IndoorGML is a complementary standard to CityGML, KML, and IFC to support location based services for indoor navigation.

Attention is drawn to the possibility that some of the elements of this document may be the subject of patent rights. Open Geospatial Consortium shall not be held responsible for identifying any or all such patent rights. However, to date, no such rights have been claimed or identified.

Recipients of this document are requested to submit, with their comments, notification of any relevant patent claims or other intellectual property rights of which they may be aware that might be infringed by any implementation of the standard set forth in this document, and to provide supporting documentation.

IV.  Security Considerations

No security considerations have been made for this standard.

V.  Submitting Organizations

The following organizations submitted this Document to the Open Geospatial Consortium (OGC):

VI.  Submission contact points

All questions regarding this submission should be directed to the editor or the submitters:

Name Affiliation Contact
Ki-Joune Li Pusan National University lik at pnu.edu
Jiyeong Lee University of Seoul jlee at uos.ac.kr
Thomas H. Kolbe Technical University of Munich thomas.kolbe at tum.de
Sisi Zlatanova Univ. New South Wales s.zlatanova at unsw.edu.au
Jeremy Morley Ordnance Survey Jeremy.Morley at os.uk
Claus Nagel Virtual City Systems cnagel at virtualcitysystems.de
Thomas Becker Technical University of Berlin thomas.becker at tu-berlin.de

VII.  Participants in development

Name Institute
Ki-Joune Li, Pusan National University
Jiyeong Lee, University of Seoul
Hye-Young Kang All4Land
Thomas H. Kolbe, Technical University of Munich
Thomas Becker, Technical University of Berlin
Claus Nagel Virtual City Systems
Sisi Zlatanova Technical University of Delft
Jeremy Morley Orndance Survey
Nobuhiro Ishimaru Hitachi Ltd.

OGC® IndoorGML 1.1

1.  Scope

IndoorGML is an OGC® standard for the representation and exchange of indoor navigation network models. IndoorGML is implemented as an application schema of the Geography Markup Language version 3.2.1.

IndoorGML aims to establish a common schema for indoor navigation applications. It models topology and semantics of indoor spaces, which are needed for the components of navigation networks. Nevertheless, IndoorGML contains only a minimum set of geometric and semantic modelling of construction components to avoid duplicated efforts with other standards, such as CityGML and IFC.

IndoorGML defines the following information about indoor space:

2.  Conformance

Conformance targets of this OGC® Standard are IndoorGML instance documents. Conformance with this standard shall be checked whether IndoorGML instance documents achieve the criteria as defined in clause 7 to 9.

In order to conform to IndoorGML, and schema document should:

a) conform to the rules, specifications, and requirements in clauses 7 to 9; and

b) pass all relevant test cases of the abstract test suite given in Annex A.

The framework, concepts, and methodology for testing, and the criteria to be achieved to claim conformance are specified in the OGC Compliance Testing Policies and Procedures and the OGC Compliance Testing web site1.

3.  Normative references

The following documents are referred to in the text in such a way that some or all of their content constitutes requirements of this document. For dated references, only the edition cited applies. For undated references, the latest edition of the referenced document (including any amendments) applies.

ISO: ISO 8601:2004, Data elements and interchange formats – Information interchange – Representation of dates and times, 2004. ISO (2004).

ISO/TS: ISO/TS 19103:2005, Geographic Information – Conceptual Schema Language, 2005. ISO and TS (2005).

ISO: ISO 19105:2000, Geographic information – Conformance and testing, 2000. ISO (2000).

ISO: ISO 19107:2003, Geographic Information – Spatial Schema, 2003. ISO (2003).

ISO: ISO 19109:2005, Geographic Information – Rules for Application Schemas, 2005. ISO (2005).

ISO: ISO 19111:2003, Geographic information – Spatial referencing by coordinates, 2003. ISO (2003).

ISO: ISO 19115-1:2014, Geographic Information – Metadata – Part 1: Fundamentals, 2014. ISO (2014).

ISO/TS: ISO/TS 19139:2007, Geographic Information – Metadata – XML schema implementation, 2007. ISO and TS (2007).

OGC 08-126, OGC® Abstract Specification Topic 5, The OpenGIS Feature, 2009

OGC 99-108r2, OGC® Abstract Specification Topic 8, Relations between Features, 1999

OGC 99-110, OGC® Abstract Specification Topic 10, Feature Collections, 1999

OGC 07-036, OGC® Geography Markup Language Implementation Specification, Version 3.2.1, 2007

4.  Terms and definitions

For the purposes of this document, the following terms and definitions apply.

This document used the terms defined in Policy Directive 492, which is based on the ISO/IEC Directives, Part 2, Rules for the structure and drafting of International Standards. In particular, the word “shall” (not “must”) is the verb form used to indicate a requirement to be strictly followed to conform to this standard and OGC documents do not use the equivalent phrases in the ISO/IEC Directives, Part 2.

This document also uses terms defined in the OGC Standard for Modular specifications (OGC 08-131r3), also known as the ‘ModSpec’. The definitions of terms such as standard, specification, requirement, and conformance test are provided in the ModSpec.

For the purposes of this document, the following additional terms and definitions apply.

4.1. 

Indoor Space

A space within one or multiple buildings consisting of architectural components.

4.2. 

Coordinates Space

A space where location is identified by (x, y) or (x, y, z) coordinates where x, y, and z are real values.

4.3. 

Cellular Space and Symbolic Space

A space where location is identified by a cell identifier (or symbolic code).

4.4. 

NR (Node-Relation) Graph

A graph (V, E) where V is a set of nodes representing cells in indoor space and E is the set of edges indicating the topological relationship between two cells, which may be connectivity or adjacency.

4.5. 

Accessibility NRG

A NR graph (V, E) where V is a set of nodes representing cells in indoor space and E is the set of edges indicating the accessibility relationship.

4.6. 

Adjacency NRG

A NR graph (V, E) where V is a set of nodes representing cells in indoor space and E is the set of edges indicating the adjacency relationship.

4.7. 

Connectivity NRG

A NR graph (V, E) where V is a set of nodes representing cells in indoor space and E is the set of edges indicating the connectivity.

4.8. 

Logical NRG

A NR graph (V, E), where node v in V and edge e in E do not contain any geometric properties.

4.9. 

Geometric NRG

A NR graph (V, E) where node v in V and edge e in E contain geometric properties.

4.10. 

Multi-Layered Space Model

A space represented by multiple layers of connectivity graphs and inter-layer connections between two nodes from different layers.

5.  Conventions

This section provides details and examples for any conventions used in the document. Examples of conventions are symbols, abbreviations, use of XML schema, or special notes regarding how to read the document.

5.1.  Symbols (and abbreviated terms)

The following symbols and abbreviated are used in this standard.

AbbreviationWord or Phrase
BIMBuilding Information Modeling
CityGMLCity Geographic Markup Language
GPSGlobal Positioning Systems
CRSCoordinate Reference System
GMLGeographic Markup Language
IndoorGMLIndoor Geographic Markup Language
IFCIndustry Foundation Classes
ISOInternational Organization for Standardization
KMLKeyhole Markup Language
LODLevel of Detail
MLSMMulti-Layered Space Model
MVDModel View Definition
NRGNode-Relation Graph
OGCOpen Geospatial Consortium
RFIDRadio Frequncy IDentifier
SensorMLSensor Model Language
UMLUnified Modeling Language
XMLeXtended Markup Language
1DOne Dimensional
2DTwo Dimensional
3DThree Dimensional

5.2.  UML Notation

The diagrams that appear in this standard are presented using the Unified Modeling Language (UML) static structure diagram. The UML notations used in this standard are described in the diagram below.

Figure 1 — UML notation

In this standard, the following three stereotypes of UML classes are used.

  1. <<Interface>> A definition of a set of operations that is supported by objects having this interface. An Interface class cannot contain any attributes.

  2. <<DataType>> A descriptor of a set of values that lack identity (independent existence and the possibility of side effects). A DataType is a class with no operations whose primary purpose is to hold the information.

  3. <<CodeList>> is a flexible enumeration that uses string values for expressing a list of potential values.

In this standard, the following standard data types are used:

  1. CharacterString – A sequence of characters;

  2. Integer – An integer number;

  3. Double – A double precision floating point number; and

  4. Float – A single precision floating point number.

6.  Overview of IndoorGML

6.1.  Motivation for defining IndoorGML

Indoor space differs from outdoor space in many aspects. Therefore, basic concepts, data models, and standards need to be redefined to meet the requirements of indoor spatial applications. The requirements of indoor spatial information are specified according to the types of applications. In general, the applications of indoor spatial information are classified into two categories as follows:

  • Management of building components and indoor facilities, and

  • Usage of indoor space.

Building construction and management and facility management belong to the first category. While the main focus of the first category is on building components such as roofs and walls, the second category is focused on usage and localization of features (stationary or mobile) in indoor space. The indoor spatial information of the second category includes requirements for representing spatial components such as rooms and corridors, and constraints such as doors. Indoor location-based services, indoor route analysis, or indoor geo-tagging services belong to the second category.

Instead of representing building architectural components, the goal of the IndoorGML standard is to define a framework of indoor spatial information to locate stationary or mobile features in indoor space and to provide spatial information services utilizing their positions in indoor space. IndoorGML is intended to provide the following functions:

  • Representing the properties of indoor space, and

  • Providing spatial reference of features in indoor space.

In summary, IndoorGML version 1 is based on the requirements from indoor navigation due to strong and urgent standardization demands, such as indoor LBS, routing services, and emergency control in indoor space. We expect that other requirements such as facilities management will be handled by future versions of IndoorGML.

7.  General characteristics of IndoorGML

7.1.  Representation of Indoor Objects in IndoorGML

An important difference of indoor space from outdoor space is that an indoor space is composed of complicated constraints such as corridors, doors, stairs, elevators, etc., like a road network space is composed of road constraints. This means that proper representations of indoor constraints are key issues for indoor spatial information modelling and standards. In IndoorGML, indoor constraints are considered from the following aspects:

  • Cellular space (defined below)

  • Semantic representation

  • Geometric representation

  • Topological representation

  • Multi-Layered Representation

7.1.1.  Definition of Indoor Space

Indoor space is defined as space within one or multiple buildings consisting of architectural components such as entrances, corridors, rooms, doors, and stairs. IndoorGML is not concerned about architectural components themselves (e.g., roofs, ceilings, walls), but instead the spaces (e.g., rooms, corridors, stairs) defined by architectural components, where objects can be located and navigate. IndoorGML is also concerned with the relationships between spaces. Components irrelevant to describe the spaces, such as furniture, are not within the scope of IndoorGML.

While indoor space models may be restricted to a single building, they may be comprised of multiple buildings or a complex of connected buildings. All the buildings are not necessarily covered by a roof. For example, an inner court or veranda can belong to an indoor space.

7.1.2.  Cellular notion of space and cells

One of the differences of IndoorGML from previous standards dealing with building interior space such as IFC and CityGML is that it provides a standard for representing indoor spaces rather than architectural components. For this reason, we consider an indoor space as a set of cells, which are defined as the smallest organizational or structural unit of indoor space [28]. A cellular space S is defined as follows:

S = {c1, c2, … , cn }, where ci is ith cell.

Cellular space has important properties. First, every cell has an identifier (namely c.ID), such as a room number. Second, each cell may have a common boundary with other cells but does not overlap with any other cell. Third, position in cellular space can be specified by cell identifier, although we may employ (x, y, z) coordinates to specify a position for more precise location.

While a set of cells is the minimum information to determine a cellular space, additional information can be also included in cellular space as follows:

  • semantics: e.g., classification and interpretation of cells;

  • geometry: e.g., solids in 3D or surfaces in 2D; and

  • topology: e.g., adjacency or connectivity.

7.1.3.  Semantic Representation of Indoor Space

Semantics are an important characteristic of cells. The indoor space can be decomposed into different cells if different criteria are considered. The cell subdivision can represent the topography (construction) of a building, available WiFi coverages, indicate security areas, or public/office areas, etc. Every cell is then given semantics with respect to the semantics used to the space subdivision. For example, in a topographic space it is possible to have ‘room’, ‘door’, ‘window’, in WiFi space — ‘WiFi point A’, ‘WiFi point B’, etc. and in a security space — ‘check-in area’, ‘boarding area’, ‘crew areas’.

In IndoorGML, semantics is used for two purposes: to provide classification and to identify a cell and determine the connectivity between cells. Semantics thus allows us to define cells that are important for navigation. For example, the most commonly used classification of cells in topographic space is into navigable (rooms, corridors, doors) and non-navigable (walls, obstacles) cells.

Cells can be organized in a hierarchical structure according to their semantics, corresponding properties and semantic interrelations (specialization and generalization). For example, ‘room’ is a specialization of ‘navigable cell’ and ‘non-navigable cell’ is a generalization of ‘walls’ and ‘obstacles’. Cells created for one space representation may be aggregated or subdivided for the purpose of another one. For example, in security space ‘check-in area’ cell can be an aggregation of several ‘room’ cells, which have been created for the topography space.

Connectivity, in terms of possibility to navigate through cells, is largely derived from the semantics of cells. For example, to be able to go from one room to another, we need to know that at least one common opening (door, window) cell exists.

The properties of a semantically identified cell have impact on connectivity and can act as a navigation constraint. For example, certain doors might provide access in one direction only (emergency exits), or forbid access to a specific group of users (security areas) or allow access according to specific time intervals (e.g., shops).

IndoorGML allows different space representation to be integrated via the concept of Multi-Layered Space Representation (see 7.1.6).

7.1.4.  Geometric Representation of Indoor Space

Every cell defining indoor space, such as a room or a corridor, owns a form, extension and position that can be collected and modelled. Geometric information can be included in IndoorGML in several ways. In order to represent geometry of cell, we assume 3D or 2D Euclidean spaces. Using the concepts of Euclidean space, the geometry provides the means for the quantitative description of the spatial characteristics of cell, where a metric space is defined as [18].

ISO19107 (Spatial Schema) [1] provides conceptual schemas to describe and model real world objects as features, where cells in indoor space are a type of feature. The geometry package contains various classes for coordinate geometry used in IndoorGML. The mathematical functions which are used for describing the geometry of a cell depend on the type of coordinate reference system (CRS) which is used to define a spatial position.

The geometric representation of 2D or 3D features in indoor space is not a major focus of IndoorGML, since they are clearly defined by ISO 19107, CityGML, and IFC. However, for the sake of self-completeness, the geometry of 2D or 3D object may be optionally defined within IndoorGML according to the data model defined by ISO 19107. As illustrated in Figure 2 there are three options for representing geometry of a cell in indoor space.

  1. External Reference (Option 1): Instead of explicit representation of geometry in IndoorGML, an IndoorGML document only contains external links (namely c.xlink, where c is a cell in IndoorGML) to objects defined in other data sets such as CityGML, where the referenced objects in external data set include geometric information. Then there must be 1:1 or n:1 mappings from cells in IndoorGML to corresponding objects in other dataset.

  2. Geometry in IndoorGML (Option 2): Geometric representation of cell (namely c.geom, where c is a cell in IndoorGML) may be included within an IndoorGML document. It is GM_Solid in 3D space and GM_Surface in 2D space as defined in ISO 19107. Note that solid with holes or surface with holes are allowed in this standard.

  3. No Geometry (Option 3): No geometric information is included in IndoorGML document.

Figure 2 — Three options to represent geometry in IndoorGML

When IndoorGML is independently used without referencing CityGML or IFC, it may contain the full 3D geometry of feature as defined in ISO 19107 but can also include only a 2D footprint. When IndoorGML is used with CityGML or IFC, we recommend making reference to the geometry defined in CityGML or IFC. Note that these options are not exclusive. For example, while IndoorGML document contain external references to the corresponding objects in CityGML, it also contains geometries of features by either the second or the third option. However, the second and third options are apparently exclusive.

7.1.5.  Network Representation of Cellular Space

Topology is an essential component of cellular space and IndoorGML. A natural topology such as “neighbourhood, interior, disjoint and boundary” may be induced from geometry in Euclidean space. However, topological properties are not implicitly included in cellular space. Therefore, we need to explicitly describe the topological relationship in IndoorGML.

The Node-Relation Graph (NRG) [25] represents topological relationships, e.g., adjacency and connectivity, among indoor objects. The NRG allows abstracting, simplifying, and representing topological relationships among 3D spaces in indoor environments, such as rooms within a building. It can be implemented as a graph representing the adjacency, connectivity relationships without geometrical properties. It enables the efficient implementation of complex computational problems within indoor navigation and routing systems.

The Poincaré duality [8] provides a theoretical background for mapping indoor space to NRG representing topological relationships. A given indoor space can be transformed into a NRG in topology space using the Poincaré duality. This approach simplifies the complex spatial relationships between 3D by a combinatorial (or logical) topological network model [25]. According to Poincaré duality, a k-dimensional object in N-dimensional primal space is mapped to (N-k) dimensional object in dual space. Thus, solid 3D objects in 3D primal space, e.g., rooms within a building, are mapped to nodes (0D object) in dual space. 2D surfaces shared by two solid objects is transformed into an edge (1D) linking two nodes in dual space. The nodes and edges in dual space form an adjacency graph, where the nodes and the edges of dual space represent cells and adjacency relationships between cells in primal space, respectively. Figure 3-a and Figure 3-b illustrate this duality transformation for the case where the primal space is 3D and 2D respectively. Note that the transformations from 1D object (curve) or 0D object (point) in 3D primal space are not included in IndoorGML since they are not considered as cells in most applications. But the transformation may be applied to 1D or 0D objects of 3D primal space in a similar way if it is required.

Then the adjacency graph Gadj is defined as follows:

Gadj = (V, Eadj), where V and Eadj are sets of nodes and edges in dual space mapped from cells and surfaces in 3D primal space, respectively.

Once adjacency relationships between cells are determined by Poincaré duality, other topological relationships can be defined from adjacency relationships based semantic information. An example of adjacency relationships in dual space is depicted by Figure 4. Figure 4-a shows a primal space with three cells including exterior cell (EXT), and boundaries between cells and the corresponding adjacency graph in dual space is given in Figure 4-b. Adjacency graph of dual space serves as a basic topological graph, since other topological graphs can be derived from the adjacency graph.

While no semantic information is used to generate adjacency graph in Figure 4, a different graph can be derived from adjacency graph by using semantic information. In Figure 5, boundaries are classified into walls and doors, then the graph in Figure 4-b becomes a different graph, called connectivity graph, which represents connectivity between cells as shown in Figure 5. Among adjacency relationships between cells in Figure 4-b, the edges of doors are included in the graph, while walls are removed from the graph since walls are not navigable. In a similar way, we may derive accessibility graph from adjacency graph by using constraint information as shown in Figure 6. If there is a constraint that the width of door D1 is 1.2 meters, then cell R1 is not accessible to tables bigger than 1.2 meters via door D1 and the accessibility graph becomes as Figure 8.

Figure 3 — Principles of Poincaré duality as shown by Lee [21] (mathematical definition of Poincaré duality in [8])

Figure 4

Figure 5 — Derivation of connectivity graph from adjacency graph

Figure 6 — Derivation of accessibility graph

Connectivity graph Gcon and accessibility graph Gacc are defined in similar ways as follows:

Gcon = (V, Econ), where V is a set of nodes in dual space mapped from cells in 3D primal space and E~con ~is a set of edges representing connectivity between cells in primal space. Note that EconEadj.

Gacc = (V, Eacc), where V is a set of nodes in dual space mapped from cells in 3D primal space and E~acc ~is a set of edges representing accessibility between cells in primal space. Note that EaccEadj.

The walls and doors in the primal space are represented as boundaries in Figure 4-a, and they are accordingly mapped to edges in dual space as depicted in Figure 4-b. However, walls and doors may be also represented as cells with certain thickness depending on applications as shown in Figure 7. We call this representation thick wall model and the representation in Figure 4 is called thin (or paper) wall model. Then the NRG in dual space should be differently constructed as shown in Figure 7, where walls and doors are mapped to nodes of dual space.