## 3 Methodology
### Spaces Division and Extraction
#### 3.3.2 Generation of Wall Candidates
**Return**\(\{\text{indexIA}\}\),\(\{\text{indexEA}\}\)

#### 3.3.3 Determination of Space Layout and Parameterization

As described in Section 3.3.2, the point cloud cluster of wall planes is generated. Due to measurement distance limitations, clutter and occlusion, the detected wall planes can create issues of incompleteness, therefore, we propose a boundary generation algorithm for space layout determination by considering the intersection of all wall candidate centerlines in the horizontal plane. Note that this algorithm is designed for situations where the spaces consist of straight walls (Algorithm 2). First, we use the RANSAC line fitting method to obtain the optimal fitted line \(\{L\}\) for all 2D projected walls, as detailed in Section 3.3.2. For each line, two nearest neighbor lines \(\text{NN}p_{st},\text{NN}p_{end}\) and the two corresponding endpoints are obtained by calculating the minimum distance between the current endpoint and the endpoints of others. To organize the line segment by order, the algorithm starts from the first line and iteratively adds the index of the nearest neighbor line segment into the vector of lines segment index \(\{\text{Ls}\}\). Meanwhile, the corresponding intersection points are calculated and added into the vertex container \(\{p_{iters}\}\). It continues until the algorithm returns back to the starting line. Most of the vertices of the boundary can be generated by line intersection operations. However, some parts of walls might be missed during scanning, which results in disjoint relationships the between two adjacent lines. Figure 7. shows two different situations during boundary vertex determination. In Situation 1 (Figure 7b), two lines are almost orthogonal, and the intersection point can be easily obtained using a line intersection operation. In Situation 2 (Figure 7c), because the connecting wall between line1 and line2 is missing, the two line candidates are almost parallel. The algorithm addresses this situation by checking the normal angle of two lines \(\text{C}\Big{(}L^{\text{Ls}^{j}},L^{\text{IntrL}}\Big{)}\). If the normal angle \(\text{C}\Big{(}L^{\text{Ls}^{j}},L^{\text{IntrL}}\Big{)}\) is less than angle threshold \(\theta_{th}\), then we added the endpoint of the line segment into the vertex container. In our experiments, we set \(\theta_{th}=30^{\circ}\). Finally, based on the boundary generation algorithm, the space layout boundary can be obtained, which consists of the intersection points and the endpoints of segmentation. The space can be parameterized according to the height calculated from floor and ceiling planes. Figure 6: Crossing number method for wall planes extraction. Figure 7: Determination of space layout. ```
1:Input: Projected wall planes: \(\{\mathrm{P}\}=\{P_{i}|1\leq i\leq N\}\) Fitted lines vector: \(\{\mathrm{L}\}\)=\(\left\{p^{i}_{st},p^{i}_{end}\right\}\) Line fitting function based RANSAC method: \(\mathrm{F}(. )\) Minimum Distance calculation between the current point and others function: \(\mathrm{D}(. )\) Enum of the endpoints of line: \(\mathrm{eu}=(\mathrm{st},\ \mathrm{end})\) Map of Index of Nearest Neighbors of the fitted lines and the endpoints of the target line: \(\mathrm{M}p_{st}\{\mathrm{NN}p_{st},\ \mathrm{euEP}\ \}\), \(\mathrm{M}p_{end}\{\mathrm{NN}p_{end},\mathrm{euEP}\}\) Index of the lines by order: \(\{\mathrm{Ls}\}\) Intersection function of two line segments: \(\mathcal{L}(. )\) Angle calculation of two line function: \(\mathrm{C}(. )\) Angle threshold: \(\theta_{th}\)
```
**Output:** Vertex of space boundary: \(\{p_{iters}\}\)
```
1:\(\mathrm{L}=\varnothing\), \(D_{min}=1000\), \(L_{cur}=0\), \(L_{tar}=1\)
2:for i = 0 to size (\(\{\mathrm{P}\}\)) do
3: Do line fitting for \(P_{i}\)
4:\(\{\mathrm{L}\}\leftarrow\mathrm{F}(P_{i})\)
5:endfor
6:for i = 0 to size (\(\{\mathrm{L}\}\)) do
7: Calculate minimum distance between the endpoint \(p^{i}_{st}\) or \(p^{i}_{end}\) and others and output the index of nearest neighbor.