# Methodology for the Efficient Progressive Distribution and Visualization of 3D Building Objects
## 3 Methodology
### Generalization Methods to Generate a BuildingTree
#### 3.2.2 Generating the CLOD Model from LOD3 ES
To generate the MCR set of a cross-section, we continuously segment the cross-section with edges and select the maximum reduced area; an example is given in Figure 6.  
```
1 procedureDecompose(Cross_Sections)
2 results=[]
3 forallcross_sectioninCross_Sectionsdo
4 ifbbox(cross_section)<min_Areathen
5 remove(Cross_Sections,cross_section)
6 else
7 gcs=Generalize(cross_section)
8 parts=getMCR(gcs)
9 insert(result,parts)
10 endif
11 endfor
12 returnresult
13 endprocedure
```  
**Algorithm 2**Cross Section Decompose. The procedure Generalize is defined as in [36]  
The pseudocode of MCR is given in Algorithm 3 in which getMCRArea is the function to calculate the Minimum Containing Area of a point set. To calculate the MCR area, the rotating calipers method  
Figure 6: Example of MCR detection. (**a**) Ground plan; (**b**) Main MCR; (**c**) All detected MCRs. is employed [59]. The input of the getMCR is generalized cross-section (_gcs_) and the output is decomposed minimum containing rectangles to present the _gcs_. ```
1 proceduregetMCR (_gcs_)
2\(d\_area\_max\) = 0
3 results = [ ]
4\(area\_gcs\) = getMCRArea(_gcs_)
5 ifarea_gcs < d_min_then
6 insert(result, _gcs_)
7 returnresults
8 endif
9 forall\(ls\)in gcs.edgesdo
10\(c1\), \(c2\) = segment(_gcs, \(ls\)_)
11\(area\)1 = getMCRArea(\(c1\))
12\(area\)2 = getMCRArea(\(c2\))
13\(d\_area\) = area_gcs - area1 - area2
14 ifd_area < d_area_max then
15\(c1\_max\) = \(c1\)
16\(c2\_max\) = \(c2\)
17\(d\_area\_max\) = \(d\_area\)
18 endif
19 endfor
20 ifd_area_max < d_ththen
21\(c1\)r = getMCR(\(c1\_max\))
22\(c2\)r = getMCR(\(c2\_max\))
23 insert(result, \(c1\)r)
24 insert(result, \(c2\)r)
25 returnresult
26 endif
27 endprocedure
```  
**Algorithm 3**Minimum Containing Rectangular  
In Algorithm 3, _d_Min_ is the threshold area that the polygon will be further segmented into. If the MCR area of the input polygon is smaller than _d_min_, it will not be further segmented and directly inserted into the result list. getMCRArea is a procedure that calculates the minimum containing rectangle area of the input polygon. _d_area_max_ is used to select the segmentation that can reduce the area most. _d_th_ is a predefined threshold that is used to determine if the segmentation is in effect. For example, after the segmentation, if the reduced area (_d_area_max_) is bigger than _d_th_, it means that the segmentation is worth as shown in following Figure 5(b). Otherwise, in Figure 5(c) the reduced area (_d_area_max_) is too small (_<d_th_) meaning that the segmentation is not necessary. This function computes a set of rectangles that together constitute a simplified cross-section. The computational complexity of the rotating calipers method is O(\(n\)) where \(n\) is the number of points [59]. The segmentation number is the number of edges in the cross-section, which is also less than \(n\). Then the complexity for each around is O(\(n^{2}\)). After the segmentation, the number of points and edges is not increased. Therefore, in worst cases, the overall complexity is less than O(\(n^{3}\)). In further analysis, according to the definition, the time complexity of cross-section decomposition algorithm is mainly composed by generalization and getMCR functions. Suppose a cross-section contains \(n\) points. The generalization algorithm according to [36] is O(\(n^{2}\)). In the getMCR function, the complexity of getMCRArea is O(\(n^{2}\)) according to the [59], so the complexity of segmentation edge selection part in getMCR is n*O(n^2) = O(n^3). Meanwhile, the function getMCR is recursive; it segments the polygon into two parts and computes the getMCR respectively. Because in each segmentation the area reduction is more than _d_th_, the number of segment rounds is smaller than a constant (polygon_area/_d_th_). Therefore, the overall complexity of getMCR is O(\(n^{3}\)).