Concepts, Algorithms, and Evaluation 
In our approach, we assume that the majority of residential 
houses have either one main section or multiple connected 
sections, with additional smaller extensions, and that a partition 
thereof can be properly derived from the outline polygon. Once 
such a partition is found, a general geometrical description of 
the roof can be constructed by assigning a parameterized 
standard shape to each section. However, the difficulty to 
generate correct facade and roof shapes from a partition 
increases with the number, shape and arrangement of its 
elements. We therefore generate a set of non-overlapping, 
mostly quadrilateral shaped polygons that together approximate 
the original footprint (cp. Figure 2). Other ground shapes may 
also occur, but those primitives are then restricted to only bear 
certain roof shapes. 
Cell Decomposition 
As referred to in (Foley et. al, 1996), a spatial partitioning 
representation in solid modelling, where solids are decomposed 
into nonintersecting, typically parameterized primitives, is 
called cell decomposition. 
Serving as the basis for the building reconstruction process, we 
first of all generate such a partition for each building footprint. 
As mentioned above, this is done solely from information found 
in the building’s outline. The big challenge herein is to avoid 
decomposing the area in too many small cells, for which it 
becomes increasingly difficult to reconstruct a well-shaped roof, 
especially if the building outline is very detailed and consists of 
many short line sections (see Figure 4). So instead of using all 
the available lines from the outline polygon and infinitely 
extend them to split the footprint, an adequate subset must be 
found that results in a set of primitives that together reflects 
well the characteristic shape of the building. However, the 
resulting outline will not be identical to the original one, but 
rather be a generalization thereof. So to best resemble the 
outline, the set of decomposition lines should approximate well 
the original points and line segments. 
Figure 2. Building footprint and its decomposition into cells. 
The roof is then reconstructed by determining a shape for each 
cell from the LIDAR points with regard to the neighbour cells 
(cp. Figure 3). After identifying the points inside a cell, the 
normal vectors from the local regression planes of the points are 
tested against all possible shapes. Here, only the orientation is 
used to speed up comparing the many shapes we support. The 
one that best fits is then chosen and its parameters estimated 
from the 3D point coordinates. Cells whose neighbour 
configurations suggest comer-, t- and cross-junctions are 
examined again and replaced if a junction shape can be fitted 
according to the neighbour shapes and parameters. 
Figure 4. Cell decomposition of a building footprint using all 
line segments of the outline and only an averaged subset. 
Our algorithm for generating cell decompositions from given 
outlines has been thoroughly described in the context of 3D 
building generalization (see e.g. (Kada, 2007)). But instead of 
generating 3D decomposition planes from the facade polygons 
of a 3D building model, the 2D decomposition lines are now 
generated from the 2D outline. 
In a nutshell, the line segments are grouped into subsets of 
“parallel” lines that are pair wise a maximum distance away 
from each other. This is the generalization distance, which 
means in this context, that the cells resulting from the footprint 
partitioning will not have sides that are shorter than this length. 
Line segments are considered parallel if the angle between their 
directions is below an angle threshold. This allows for a better 
generalization of connected line segments and therefore helps to 
keep the number of generated cells low. For each subset of line 
segments, the associated decomposition line is computed by 
averaging the line equations of its elements. Short line segments 
of arbitrary direction, but whose endpoints are both closer to 
the decomposition line than the parallel line segments, are 
associated with this subset, but will not contribute to the 
averaging of this or any other decomposition line. 
For example, the green line segments on the left side of Figure 
5 are considered parallel under the chosen angle threshold of 15 
degrees. The added perpendicular distance of any two endpoints