By David Bélanger

Computational Geometry 308-507A

McGill University

Fall 2000

- Introduction
- Straight Skeleton
- From Straight Skeletons to Roofs
- Examples
- Other Applications
- Applet
- References
- Links

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 v_{r}. Edge *e* is split in two parts e_{a} and e_{b}, each becoming adjacent to one of the edges incident at v_{r} (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 3^{rd} 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]:

- arc
- an edge of S(P)
- node
- a vertex of S(P) (excluding vertices of P)
- face of edge e
- the area swept by an edge
*e*of P

Let P be a simple n-gon and let S(P) denote its straight skeleton.

- S(P) is unique for a given simple polygon P.
- S(P) partitions P into
*n*monotone polygons. - S(P) consists of straight line segment only, hence the name. A medial axis diagram of a nonconvex polygon can have parabolic curves and therefore is not suitable for some applications (figure 7).
- If P is convex, then the medial axis of P and S(P) are the same in the interior of P.
- If P is rectilinear (i.e. consists of edges orthogonal) then S(P) and the medial axis using Minkowski metric p = INFINITY for distances are the same.
- S(P) is a tree that has 2
*n*- 3 arcs,*n*- 2 nodes and*n*faces.

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 2*n*+*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 2*n*+*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 2*n*+*t*-2 triangles when the algorithm starts. Therefore, the total number of edge events and split events can be no more than 2*n*+*t*-2.

**Lemma 3**: The total number of flip events is O(n^{2}).

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(n^{2}) triangles need to have their collapsing time recomputed. Updating the priority queue to take into account these changes will take O(n^{2}log n). This is more than any other priority queue operations. The running time is therefore O(n^{2}log n).

The algorithm uses *O(n)* space because, at any time, at most 2*n*+*t*-2 triangles are stored.

Proof: By lemma 1, at the beginning we have 2*n*+*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(n ^{1+eps}+n^{8/11+eps}r^{9/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 o_{G}(x)=d(x,G). o_{G} is continuous and piece-wise linear, in fact o_{G} defines a polygonal surface S in **R**^{3} 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 45^{o}). 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.

- Draw a simple (i.e. non-intersecting) polygon in the drawing area.
- Click to set a vertex.
- Close the polygon by clicking on the first vertex (in red).

- Click on the
**RUN**button to start the simulation.

- The
**STEP**button runs the simulation but stops at each event. Click on**STEP**again to go to the next event. - The
**RESET**button erases the drawing area and resets the simulator. - The
**Select a house**drop down list let you choose a polygon. - The
**Message Box**displays the points entered and some processing information.

**Black**- The polygon used as input
**Blue**- The shrinking polygon
**Cyan**- At a split event, one of the 2 resulting polygons get this colour.
**Magenta**- The straight skeleton.
**Green**- Diagonals of the triangulation
**Red**- Bisectors of the vertices
**Orange**- Triangle having its collapsing time computed.
**Pink**- Point where last event occured.

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 |

- [NTSP] O. Aichholzer, F. Aurenhammer, D. Alberts, and B. Gärtner. A novel type of skeleton for polygons.
*J. Universal Computer Science*. 1(12):752-761, 1995.

- [SSGPFP] O. Aichholzer and F. Aurenhammer. Straight skeletons for general polygonal figures in the plane.
*Proc. 2nd Annual International Conference Computing and Combinatorics*, pp. 117-126. Lecture Notes in Computer Science 1090, Springer, 1996.

- [RRCCPP] D. Eppstein and J. Erickson,
*Raising Roofs, Crashing Cycles, and Playing Pool: Applications of a Data Structure for Finding Pairwise Interactions*. PS file on the web.

- [SASS] D. Eppstein,
*A Subquadratic Algorithm for the Straight Skeleton*, PDF file on the web.

- [CGC] J. O'Rourke, Computational Geometry in C, Second Edition, Cambridge University Press, (1998).

- [SSI] P. Felkel and S. Obdrzálek,
*Straight Skeleton Implementation*. PS file on the web.

- Straight skeleton of a simple polygon
- Raising roofs, crashing cycles, and playing pool -- Abstract
- The Fold-and-Cut Problem : Straight-Skeleton Solution
- Project: 2D Skeletonisation
- Godfried Toussaint's links on skeletons of polygons
- Medial Axis by Ayelet Shemesh
- The Voronoi Web Site

Please send any comment, question or correction concerning this page to dbelan2(à)po-box.mcgill.ca.

Last updated on December 5, 2000.