Claus Brenner
(a) (b) (c) (d)
Figure 2: (a) Medial axis M (P) for a L-shaped polygon P. (b) Straight skeleton S(P). (c) Edge event (two bisectors
intersect). (d) Split event.
2.2 More general roofs
The straight skeleton graph S(P) is a unique solution, but not the only one. In fact, consider the ground plan in figure
3(a) which looks like two separate buildings having a common border. In this case, the straight skeleton reconstruction
(Fig: 3(b)) leads to a rather high roof of unusual volume and shape. Intuitively, the reconstruction in figure 3(c) would be
considered as being the correct one.
(a) (b) (c)
Figure 3: (a) A (ground plan) polygon P. (b) Straight skeleton of (a). (c) Projection of another possible roof.
How can all solutions be obtained instead of only the one from S(P)? Since the vertices of G are the (projections of the)
intersections of three roof planes and edges form the connections between them, the following algorithm can be used:
(1) intersect all roof planes to obtain a set of all possible vertices of G, and (2) try all connections between the vertices of
G until a valid solution is found. Regarding the first step, the number of intersections of three planes is ( N ) , assuming
a ground plan P with N segments. Although that number grows rapidly in the order of O(N 3), for the value range of N
considered here this poses no problem. Moreover, since ground plans with large N tend also to have complex, concave
shapes, many (often 75% and more) intersection points lie outside P and need not be taken into account. The case is
different for the second step. Except for very small N, we cannot hope to solve the search problem in acceptable time
by a naive search method such as backtracking. Fortunately, using discrete relaxation, we can reduce search complexity
greatly.
2.3 Using discrete relaxation to cut down search space
Consider two intersecting planes e; and e;, none of which is vertical, as shown in figure 4. These planes might actually
form a concave (—) or a convex (+) edge when viewed in negative direction of the z axis. We cannot tell from the plane
equations which type of intersecting edge is present. However, the edge labeling (+/—) directly corresponds to the order
of plane labels (à — 7 or j — 1).
zs 4 £ ug
( (c)
Figure 4: Intersection of two planes (a) can result in a concave (—) or convex (4-) edge (b). In the projection onto the zy
plane (c), the type corresponds to the plane label order.
Now we will turn to the situation at junctions where three planes meet. For line drawing interpretation, there is a classical
work of Waltz (Waltz, 1975) who shows that the number of possible labelings for a junction that make sense is much
smaller than the number of theoretically possible labelings. Also, using discrete relaxation (Haralick and Shapiro, 1993)
it is often possible to obtain a single label for each junction, making a subsequent search unnecessary. In the plane
intersection case described above, the situation is slightly different. Since all possible intersection points of three planes
are generated, the goal is to rule out as many as possible. Any (non-degenerate) intersection of three planes leads to one
of the eight cases shown in figure 5. Incoming and outgoing labeled edges of a node constrain the number of possible
labelings of the junction.
As an example, figure 6(a) shows the simple case of a rectangular ground polygon P. There are 4 edges of P, and
( 1 ) = 4 junctions to label. Figure 6(b) shows the situation at junction j134. Since j134 is connected to 714, only one
International Archives of Photogrammetry and Remote Sensing. Vol. XXXIII, Part B3. Amsterdam 2000. 87