# Development of Navigation Network Models for Indoor Path Planning Using 3D Semantic Point Clouds
## 2 Methodology
### Node Extraction and Edge Construction
#### 2.3.2 Node Extraction and Edge Construction for Hallways  
For a more practical extraction of a navigation route in hallways, [PERSON] et al. [35] proposed a method for subdividing corridors based on the positions of doors. By calculating the cutting points between doors and projecting perpendicular lines, they divide the hallway into several segments, thereby generating a more detailed and accurate navigation route. However, this method relies on 2D CAD files for navigation network generation and may not be directly applicable to 3D point clouds. In the study by [PERSON] et al. [26], they used a method for extracting sub-nodes along the hallway. In their method, one key step is determining the hallway centerline, followed by projecting the positions of doors onto the centerline for sub-node extraction, but they did not provide details on how to calculate the centerline of the hallway. In this study, we used PCA [36] to determine the main direction of the hallway. As shown in Figure 7, the red arrow indicates the main direction, which corresponds to the primary axis and aligns with the longer direction of the hallway. The yellow arrow represents the secondary direction, which is perpendicular to the primary axis. By identifying the primary axis of variance in the point cloud data, we projected the points onto this axis to define the central line. However, we observed that the centerline extracted directly using PCA occasionally drifted towards one side of the hallway. This drift occurs mainly due to the asymmetric or irregular distribution of the point cloud, as the direction of maximum variance calculated by PCA may not always perfectly align with the geometric center of the hallway. To optimize the extraction results, we introduced the centroid of the hallway as a reference, calculated by Equation (1). Let the primary direction vector obtained from PCA be denoted as \(\overset{\rightarrow}{d}\), and the centroid of the hall  
However, such endpoints may deviate from the true center of the hallway. Therefore, we correct the endpoints by considering the centroid and adjusting the positions symmetrically around it. The corrected endpoints are calculated using the following equations:  
\[ \begin{array}{c}\overset{\rightarrow}{p}_{min}=\overset{\rightarrow}{c}+ \overset{\rightarrow}{d}\cdot(proj_{min}-\overset{\rightarrow}{c}\cdot \overset{\rightarrow}{d})\\ \overset{\rightarrow}{p}_{max}=\overset{\rightarrow}{c}+\overset{ \rightarrow}{d}\cdot(proj_{max}-\overset{\rightarrow}{c}\cdot\overset{ \rightarrow}{d})\end{array}  \tag{4}\]  
In Equation (4), \(\overset{\rightarrow}{c}\cdot\overset{\rightarrow}{d}\) represents the projection of the centroid onto the primary direction, ensuring that the endpoint correction is made relative to the position of the centroid. \(\overset{\rightarrow}{d}\cdot(proj_{min}-\overset{\rightarrow}{c}\cdot \overset{\rightarrow}{d})\) and \(\overset{\rightarrow}{d}\cdot(proj_{max}-\overset{\rightarrow}{c}\cdot \overset{\rightarrow}{d})\) compute the offsets of the minimum and maximum projection values relative to the centroid's projection. The final endpoints \(\overset{\rightarrow}{p}_{min}\) and \(\overset{\rightarrow}{p}_{max}\) are determined by adding the corrected offsets to the centroid \(\overset{\rightarrow}{c}\), ensuring symmetrical positioning around it. By projecting the points onto the main direction identified by PCA and then adjusting these projections relative to the centroid, this adjustment reduced the drift of the extracted centerline, ensuring the centerline more accurately represents the true central axis of the hallway. Subsequently, the centers of doors parallel to the centerline of each hallway are projected onto the centerline to obtain intersection points, as shown in Figure 8. These intersection points are then sorted, and if the distances between any two intersection points are less than a set threshold of 1 m, they are merged into a new intersection point.