## Materials and Methods
### Room Segmentation
#### 3.3.1 Cell Decomposition  
In this step, the floor plane in each story is partitioned into decomposed cells by the extracted wall lines. The partitioned cells determine the geometric shape of the rooms, and the extracted wall lines determine the shape of the partitioned cells. Thus, we expect that all of the wall lines can be detected as integrated and accurate in the indoor environment. However, detecting complete wall lines directly from the original point cloud is difficult because indoor environments exhibit extremely high levels of clutter and occlusion [1; 15]. Moreover, certain portions of walls are not sampled because the sight of the laser scanner is occluded by clutter [1; 36]. To ensure that almost all wall lines in the building can be detected, the points in each story are first split into several horizontal slices [1; 42; 52; 53] that share the same floor plan structure, as shown in Figure 3a. Then, the wall segments in all slices are extracted and projected onto a horizontal plane. The identification is split into four steps: (one-slicing) the points are sliced into a set of pieces; (two-line extraction) a region-growing line extraction method and an IRLS line fitting algorithm are proposed to extract a segment hypothesis that represents the wall direction by extending a previous work [46]; (three-line projection & fusion) the extracted segments are projected into the horizontal plane and merged by a line fusion algorithm; and, (four-cell decomposition) the plane spaces are partitioned into a two-dimensional (2D) cell decomposition by extended lines from extracted segments. Figure 2: Result of story segmentation. (**a**) Point distribution along the z-axis. (**1**) The floor of the first floor. (**2**) The ceiling of the first floor. (**3**) The floor of the second floor. (**4**) The ceiling of the second floor. (**b**) Result of story segmentation (one color per floor). **One-Slicing:** Each story is first split into several horizontal slices, as shown in Figure 3a. In this dataset, each story is split into ten pieces. The number of slices is influenced by the height and density of the input point cloud. **Two-Line extraction:** The points along every linear wall are separated by the region-growing method [54; 55]. In this study, an initial seeding point is selected in the area with the smallest curvature. The k-Nearest Neighbors (kNN) points that satisfy \(\|n_{p}\cdot n_{s}\|>\cos(\theta_{th})\) are added to the current region, and the kNN points that satisfy \(r_{p}<r_{th}\) are added to the list of potential seed points and continue to grow from these points in the list of potential seed points. The process is iteratively applied until all of the points are segmented and grouped. \(n_{p}\) is the normal of the current seed and \(n_{s}\) is the normal of its neighbor. \(\theta_{th}\) is a smoothness threshold, which should be specified in terms of the angle between the normals of the current seed and its neighbors. \(r_{p}\) is the residual of a point in the list of potential seed points. \(r_{th}\) is a residual threshold, which should be specified by the percentile of the sorted residuals. Then, an IRLS algorithm [46] that uses the M-estimator is proposed for line fitting in each separated region. For a point cloud \(P=\{p_{1}\dots\dots p_{n}\}\in R^{3}\), the line-fitting problem can be considered to fit points to a line. Least-squares line fitting is known to suffer from outliers. The standard least-squares (LS) algorithm maintains \(\sum\limits_{i}dis(P_{i},\;Seg)^{2}\) at a minimum, where \(dis(P_{i},\;Seg)\) is the distance of the ith point to the segment [56]. Therefore, even a single outlier can cause the results to deviate from the ground-truth value. However, the M-estimator is robust for outliers.