# A Modified Methodology for Generating Indoor Navigation Models
## 1 Introduction  
Route navigation is being expanded to cover the entire geographic space, and outdoor navigation is emerging as a separate concept from indoor navigation. The role of indoor navigation (navigation inside buildings) [1, 2] is to complement outdoor navigation, and it is implemented mainly in large public utility buildings. Flat 2D network models are developed based on floor plans. Their height can be represented by attribute H, and such systems are referred to as 2.5D models. 3D models are generated by taking into account the plans of successive building floors. Navigation relies on a geometric model of networks written in mathematical graph structures in the form of a geometric graph [3] with nodes N (NOD) and edges E (EDGE). In a graph model of a network, nodes N represent significant elements of the plan, such as:  
* structures (rooms, corridors, stairs),
* lines (doors, windows, entrances). Nodes representing structures are generally the centroids of those structures. Lines are also represented by centroids, which are the midpoints of entrance lines. Nodes are described by coordinates in a given reference system. Semantic data describing objects are represented by node attributes. In the model, edges represent route sections and possible traffic flows. In indoor navigation, digital geometric network models for navigating people should account for natural movement patterns inside a building. The generated routes should not run close to walls or obstacles. For many years, researchers have sought to develop a methodology for the automatic generation of indoor navigation models [4; 5; 6]. Two main types of methods have been proposed: geometric methods that support the generation of Geometric Network Models (GNM) and grid methods for developing Regular Grid Models (RGM) [7]. Geometric methods rely on the topological relations between neighboring structures [4; 8], and they are referred to as Node-Relation Structure (NRS) models. A Node-Relation Structure is represented by graphs composed of nodes and edges. The nodes are usually centroids that identify structures. Network edges are lines connecting the centroids of the neighboring structures. A similar method of representation is used in the grid model. The elements of the grid constitute structures [9; 10; 11]. Structures are usually described with the use of semantic data, such as type of use. A building can be composed of corridors, rooms, and stairs. The NRS model features sub-graphs describing only the relations that are based on semantic data, such as (corridor-room) relations. [PERSON] [4; 8] developed a method for transforming the NRS model into a network with the use of the Medial Axis Transformation (MAT) algorithm, which has been extensively described in the literature [12; 13; 14]. The MAT algorithm has also been deployed in other solutions [7; 15]. The results were generally satisfactory, but in open spaces (crossing paths), the generated lines were curved. Certain modifications, such as increasing the density of the initial model, are required to eliminate curved lines [16]. However, this method generates lines that only approximate the real middle line [17]. Numerous solutions have been proposed to deal with this problem [18; 19]. Other geometric solutions [19; 20; 21; 22; 23] take into account openings, such as doors. In the network model, openings are represented by nodes. In this case, models are constructed based on corridor-entrance, entrance-room, or corridor-corridor relations. The relevant methodology can be referred to as a Node-Relation Structure and Entrance (NRSE) model. Many solutions of this type have been discussed in the literature [24; 25; 26]. They account for the attributes describing room and entrance functions. Other methods for generating models are based on structure segmentation. Delaunay triangulation algorithms for generating Triangulated Irregular Networks (TINs) [15; 27] or Thiessen polygons, referred to as Voronoi diagrams (VDs) [1], are used for segmentation.