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