Realistic Roofs over a Rectilinear Polygon Revisited

A common task in automatically reconstructing a three dimensional city model from its two dimensional map is to compute all the possible roofs over the ground plans. A

roof

over a simple polygon in the

xy

-plane is a terrain over the polygon such that each face

f

of the terrain is supported by a plane passing through at least one polygon edge and making a dihedral angle

$\frac{\pi}{4}$

with the

xy

-plane [3]. This definition, however, allows roofs with faces isolated from the boundary of the polygon and local minimum edges inducing pools of rainwater. Recently, Ahn et al. [1,2] introduced “realistic roofs” over a simple rectilinear polygon

P

with

n

vertices by imposing two additional constraints under which no isolated faces and no local minimum vertices are allowed. Their definition is, however, too restrictive that it excludes a large number of roofs with no local minimum edges. In this paper, we propose a new definition of realistic roofs corresponding to the class of roofs without isolated faces and local minimum edges. We investigate the geometric and combinatorial properties of realistic roofs and show that the maximum possible number of distinct realistic roofs over

P

is at most

$1.3211^m{m \choose \lfloor \frac{m}{2} \rfloor}$

, where

$m=\frac{n-4}{2}$

. We also present an algorithm that generates all combinatorial representations of realistic roofs.