## 3 Methodology
### Spaces Division and Extraction
#### 3.3.2 Generation of Wall Candidates
The fitted line segment consists of two endpoints \(\left\{p_{st}^{i},p_{end}^{i}\right\}\). To determine the inclusion of a fitted line segment in the 2D boundary polygon, the cross number method is applied. This method counts the number of times a ray starting from a point crosses a polygon boundary edge separating its inside and outside. If this crossing number cn is even, then the point is outside. If the crossing number cn is odd, the point is inside. In this paper, three kinds of situations are considered. (a) When the crossing number of two endpoints are odd, the fitted line segment is inside a 2D polygon boundary. It means that the corresponding point cloud cluster is from the interior elements (Figure 6a); (b) when the crossing number of two endpoints are even, the fitted line is outside the 2D polygon boundary. Thus, the corresponding point cloud cluster is taken from the wall components (Figure 6b); (c) by considering the measurement errors in a low-quality RGB-D point cloud, we can encounter a situation where one  
Figure 5: Sample of generation of wall candidates. endpoint is inside and one endpoint is outside. An intersection point \(p_{iters}\) between the fitted line and the polygon boundary can be obtained. The distance \(\{d_{st},d_{end}\}\) from each endpoint \(\{p_{st}^{i},p_{end}^{i}\}\) to the intersection point \(p_{iters}\) can be calculated. When the percentage of the distance obtained from the outside endpoint and the distance obtained from the inside endpoint is higher than the defined threshold \(per_{t}\), we determine it to be a wall plane. Otherwise, we determine it to be an interior element (Figure 6c):  
\[R^{2}=\sum_{i=0}^{n}[y_{i}-f(x_{i},a,b)]^{2}\text{Where }f(x_{i},a,b)=ax_{i}-b \tag{1}\]  
```
Input: Projected potential wall planes: \(\{\text{P}\}=\{P_{i}|1\leq i\leq N\}\)
2D polygon consist of points: \(\text{Poly}=\left\{pn_{i}\middle|1\leq j\leq M\right\}\) Percentage threshold of length in interior and external of polygon: \(per_{1}\) Line fitting function based RANSAC method: \(\text{F}(. )\) Fitted line: \(\text{L}=\left\{p_{st}^{i},p_{end}^{i}\right\}\) Distance calculation function: \(\text{D}(. )\) Distance from endpoints to intersection point: \(d_{st},d_{end}\) Intersection function of two line segments: \(\mathcal{L}(. )\) Intersection point of two line segments: \(p_{iters}\) Crossing number function to determine the inclusion of a point in a 2D polygon: \(\Omega(. )\) Crossing number from a ray of endpoint to the polygon boundary edges: \(cn_{st},cn_{end}\) Output: index of interior planes: \(\{\text{indexIA}\}=\{\text{id}|1\leq i\leq N\}\); index of wall planes: \(\{\text{indexEA}\}=\{\text{id}|1\leq i\leq N\}\); 1. \(\text{indexA}=\varnothing,\text{L}=\varnothing\) While \(\{\text{P}\}\) is not empty do
3. \(cn_{st}=0,cn_{end}=0\) Do line fitting for \(P_{i}\) \(\text{L}\leftarrow\text{F}(P_{i})\) Detection the crossing number of the ray from the endpoint and the polygon boundary \(cn_{st}\leftarrow\Omega\Big{(}p_{st}^{i},\text{Poly}\Big{)}\), \(cn_{end}\leftarrow\Omega\Big{(}p_{end}^{i},\text{Poly}\Big{)}\) If \(cn_{st}\) is odd && \(cn_{end}\) is odd then
4. \(\{\text{indexIA}\}\leftarrow\{\text{indexIA}\}\cup i\)
5. **else if \(cn_{st}\) is even && \(cn_{end}\) is even then** \(\{\text{indexEA}\}\leftarrow\{\text{indexEA}\}\cup i\)
6. **else**
7. Do intersection for the fitted line and the polygon boundary \(\text{14}\)\(p_{iters}\leftarrow\mathcal{L}(\text{I})\) Calculate the distance between endpoints \((p_{st}^{i},p_{end}^{i})\) and \(p_{iters}\) \(d_{st}\leftarrow\text{D}\Big{(}p_{st}^{i},p_{iters}\Big{)}\) \(d_{st}\leftarrow\text{D}\Big{(}p_{end}^{i},p_{iters}\Big{)}\) if (\(cn_{st}\) is even && \(\frac{d_{st}}{d_{end}}>per_{1}\)) | (\(cn_{end}\) is even && \(\frac{d_{end}}{d_{st}}>per_{1}\)) then
8. \(\{\text{indexEA}\}\leftarrow\{\text{indexEA}\}\cup i\)
9. **else** \(\{\text{indexIA}\}\leftarrow\{\text{indexIA}\}\cup i\)
10. **endif**
11. **endif**
12. **endif**
13. **end while**
14.