By David Bélanger
Computational Geometry 308-507A
McGill University
Fall 2000
Roof construction is one of the many applications of a straight skeleton, a relatively new type of skeleton for polygonal figures, first introduced in 1995 by Aichholzer et al. in [NTSP]. The problem is stated as follows:
Given walls of all the same height we would like to construct a polygonal roof such that all faces have the same slope (figure 1).
In this project, we will describe the algorithm found in Aichholzer and Aurenhammer 1996 paper [SSGPFP]. Although, an algorithm with a better worst case performance exists, it will not be presented here. The interested reader may find it in [RRCCPP].
Figure 1 (from [SASS]) : The problem.
We will start by defining the straight skeleton of a polygon, then we will describe an algorithm to compute it. Finally, we will show how to construct a roof from the resulting skeleton.
Unlike a Voronoi-type diagram defined by a distance function, we cannot characterize the straight skeleton for a general simple polygon by some function. Instead, it is defined by a shrinking process where edges move inwards in a direction normal to itself and vertices move along angular bisectors of edges (figure 2 (a)). Egdes will decrease or increase, P will become smaller and smaller until either its area become zero or one of two events occur:
1) An edge event occurs when an edge length decreases to 0. The egdes neighbour to that edge, if they still have a positive length, become adjacent (figure 3a).
2) A split event occurs when a reflex vertex collides into an edge. This splits the edge and changes adjacencies. Let edge e be the edge split by a reflex vertex vr. Edge e is split in two parts ea and eb, each becoming adjacent to one of the edges incident at vr (figure 3b).
Figure 2 (from [NTSP] : (a) Polygon hierarchy and (b) straight skeleton.
Figure 3 (from [RRCCPP, revised version]) : (a) Two simultaneous edge events. (b) A split event.
In any of the two cases, the newly created polygon(s) (one for an edge event or two for a split event) continue(s) to shrink, possibly leading to other events, until finally the area of all polygons becomes zero.
A 3rd type of event, called a vertex event (described in [RRCCPP]), can occur for some polygons. This event happens when two or more reflex vertices and nothing else reach the same point at the same time (figure 4). We will not pursue further discussion on that event as our algorithm does not handle these degenerated polygons. Note that simply perturbing vertices of the polygon to remove the degeneracies will not do (figure 4).
Figure 4 (from [RRCCPP, revised version]) : (a) A vertex event. (b) Perturbing a degenerate polygon can radically alter its skeleton.
The straight skeleton of a simple polygon P, denoted by S(P), can be viewed as the "paths" followed by vertices of P and all newly formed vertices during the shrinking process (figure 2b). This is more formally defined: "as the union of the pieces of angular bisectors traced out by polygon vertices during the shrinking process."[NTSP]. Note that each edge event and each split event adds a new node of degree 3 to the straight skeleton.
The straight skeleton can also be defined as a propagation of wavefronts. This view is particularly useful if we are generalizing the straight skeleton to a planar straight line graph. A planar straight line graph G is a set of non-crossing line segments spanned by n points (figure 5). Vertices of degree one are called terminals. A wavefront starts on each side of each edge and propagates moving away from the edge in a direction normal to it. Also, there is a wavefront associated with each terminal t moving away from it in a direction normal to the perpendicular line at t. The straight skeleton of G, denoted S(G), is then defined as the "paths" followed by the vertices of the wavefronts (figure 6).
Figure 5 (from [SSGPFP]) : Initial wavefronts for a planar straight line graph G.
Figure 6 (from [SSGPFP]) : Straight skeleton for three figures.
We will use the following terms introduced by Aichholzer et al. in [NTSP]:
Let P be a simple n-gon and let S(P) denote its straight skeleton.
Figure 7 (from [RRCCPP]) : (a) The medial axis. (b) The straight skeleton.
We will follow the description found in [SSGPFP] of an algorithm to compute the straight skeleton S(G) of a planar straight line graph G (Figure 5, 6). Then we will discuss how to compute the polygonal roof from S(G).
The algorithm simulates the propagation of wavefronts for G by keeping at all time a triangulation of regions not yet reached by some wavefront. All regions already swept are not triangulated. Vertices of the triangulation are vertices of the wavefronts. As the vertices move on angular bisectors of the edges, triangles will change shape. Each edge event and each split event will correspond to a collapsing triangle. We can then hold all the triangles in a priority queue by collapsing time and do a discrete event simulation.
| Event | When it occurs | What needs to be done |
|---|---|---|
| 1. Flip event | A vertex v runs across a spoke s. | Remove s and add spoke t. |
| 2. Edge event | Edge e shrinks to length 0, vertex v merging with another vertex. | Identify both vertices and remove edge e. |
| 3. Split event | Edge e is split by vertex v. | Duplicate v. Assign the resulting edges e' and e" and the formerly incident spokes of v to v and its duplicate accordingly. Remove e. |
Figure 8 (from [SSGPFP]) : Flip event, edge event, and split event.
A new node of S(G) is introduced by each edge event and split event. We keep track of them in some way. The algorithm will terminates when the collapsing time of the remaining triangles is infinite.
Remark: The number of triangles remains unchanged after a flip event but decreases by 1 after each edge event and split event.
We start by stating three lemmas and proving the second one.
Let G have n vertices and t terminals.
Lemma 1: The initial triangulation has exactly 2n+t-2 triangles (including unbounded).
Proof: Omitted. See [SSGPFP] for a proof.
Lemma 2: The total number of edge events and split events is bounded by 2n+t-2.
Proof: Each edge event and each split event decreases the number of triangles by 1. A flip event does not change the number of triangles. There are 2n+t-2 triangles when the algorithm starts. Therefore, the total number of edge events and split events can be no more than 2n+t-2.
Lemma 3: The total number of flip events is O(n2).
Proof: Omitted.
As the algorithm proceeds, events will occur. Flip events do not change the direction of vertices but each edge event and each split event do change the direction of the vertices involved. All the triangles having these vertices as a vertex will need to have their collapsing time recomputed. O(n) edges are incident to a vertex and we have O(n) number of edge events and split events. Therefore, O(n2) triangles need to have their collapsing time recomputed. Updating the priority queue to take into account these changes will take O(n2log n). This is more than any other priority queue operations. The running time is therefore O(n2log n).
The algorithm uses O(n) space because, at any time, at most 2n+t-2 triangles are stored.
Proof: By lemma 1, at the beginning we have 2n+t-2 triangles. No event increases the number of triangles.
There exists a subquadratic algorithm with a better worst case running described in [RRCCPP]. It uses advanced data structures to compute the straight skeleton of a n-gon with r reflex vertices in O(n1+eps+n8/11+epsr9/11+eps) time. In general, it is less efficient in practice than the simpler algorithm discussed above.
We will now show how we can construct a polygonal roof from a straight skeleton.
Consider a point x inside a face f of S(G). Suppose f is defined by an edge e then we define d(x,G) to be the normal distance from x to the edge e. Otherwise, if f is defined by a terminal t, we define d(x,G) to be the distance normal to a perpendicular at t. Let oG(x)=d(x,G). oG is continuous and piece-wise linear, in fact oG defines a polygonal surface S in R3 where the faces of S(G) correspond to the projections of S, and G is the intersection of S with the plane. Let G be a simple polygon representing a set of walls and let's restrict ourselves to the interior of G, then S is a polygonal roof of G with n-2 nodes and 2n-3 arcs, a minimum for all roofs on G.
Note that rain falling on a face f will run off to its defining edge e. Also, each face has slope 1 (or 45o). To get an arbitrary slope 1/k for an edge e, we need to propagate the wavefront of that edge with speed k. Also, it is possible to have the vertices of the walls at different heights by propagating the waves at a certain angle from the edges. In both cases, S(G) will look different but the same algorithm with small modifications to take into account these parameters will work.
Simple polygons and their corresponding straight skeleton and roof.
Figure 9 (from [SASS]) : A roof corresponding to the straight skeleton of a polygon.
Figure 10 (from [SSGPFP]) : Skeleton and corresponding roof.
Figure 11 (from [SSI]) : Straight skeleton of a polygon with a hole.
We will conclude by stating two other applications of straight skeletons.
Reconstruction of terrains
Given a geographical map of rivers and lakes represented in G by line segments and polygonal figures, we would like to construct a polygonal terrain.
Study of impact of rain water fall on floodings
Given a map of rivers and slopes, the straight skeleton can be constructed to model water flow in a more realistic way than Voronoi diagram because it takes into account the slopes.
This applet let you design your own roofs! Given a polygon, it computes its straight skeleton. The shrinking process is simulated and the user can see the straight skeleton built as the algorithm is running.
All the applet was coded by David Bélanger. Triangulation code including area sign, left, between, collinear and intersection is from O'Rourke [CGC] and was adapted to my implementation of polygons and to real value coordinates. The applet is an implementation of the algorithm described above.
The applet was tested with the following configurations:
| OS | Browser | Working? |
|---|---|---|
| Linux | Navigator 3 | No |
| Linux | Navigator 4 | Yes |
| Win95 | Navigator 4 | Yes |
Please send any comment, question or correction concerning this page to dbelan2(à)po-box.mcgill.ca.
Last updated on December 5, 2000.