# Development of Navigation Network Models for Indoor Path Planning Using 3D Semantic Point Clouds
## 2 Methodology
### Node Extraction and Edge Construction  
In this section, we detail the process of extracting nodes from 3D semantic point clouds. Nodes representing spaces with connected topological relationships are subsequently linked to form edges. The nodes and edges form the backbone of our indoor navigation network, representing key locations and the paths connecting them.  
The theoretical foundation for our approach relies on two key concepts: The Node-Relation Graph (NRG) [6] and Poincare duality [34]. The NRG is a framework representing topological relationships, such as adjacency and connectivity, among indoor objects. It implements these relationships as a graph without requiring geometrical properties, enabling efficient path planning in indoor navigation systems. Poincare duality provides the theoretical basis for mapping indoor spaces to an NRG. According to Poincare duality, a k-dimensional object in N-dimensional primal space maps to an (N-k) dimensional object in dual space. For example, 3D rooms are represented as 0D nodes, and 2D surfaces between  
\begin{table}
\begin{tabular}{c c c} \hline \hline
**Space** & **Category of Space** & **Components** \\ \hline Navigable & General space & e.g., office, conference room, storage, copy room, open space, pantry, lounge, lobby, and WC \\ space & Connection space & door and virtual door \\  & Transition space & hallway, stairwell, and elevator lobby \\ \hline \hline \end{tabular}
\end{table}
Table 1: The semantic point clouds space classification.  
Figure 5: An example of the file tree structure after data preprocessing.  
rooms become 1D edges. This simplification allows for a combined topological network model that effectively manages complex spatial relationships indoors.  
Due to the different structural features, the importance of different types of navigable spaces is also different, e.g., hallways connecting many rooms and staircases connecting different floors are more important than general and connection spaces. Therefore, the node extraction strategies for general space, connection space, and transition space are slightly different.  
For each semantic point cloud representing general, connection, or some transition spaces (e.g., elevator lobbies), we extract the centroid to serve as the node corresponding to each space in the NRG. For a group of points \(P=\{p_{1},p_{2},\ldots,p_{n}\}\) in a semantic point cloud (e.g., offices, doors), where \(p_{i}=(x_{i},y_{i},z_{i})\), the centroid is calculated as  
\[\text{Centroid}=\left(\frac{1}{n}\sum_{i=1}^{n}x_{i},\frac{1}{n}\sum_{i=1}^{n }y_{i},\frac{1}{n}\sum_{i=1}^{n}z_{i}\right) \tag{1}\]  
However, for staircases and hallways, which belong to transition space, a single representative node sometimes fails to accurately reflect the geometric relationships, making it impossible to generate the shortest paths. Since hallways could be long and connect many rooms, and staircases link different floors, it is necessary to refine the nodes for both hallways and staircases. In the following, we will detail the extraction of nodes for staircases and hallways in Section 2.3.1 and Section 2.3.2, respectively.