Designing Roofs of Buildings

By David Bélanger

Computational Geometry 308-507A
McGill University
Fall 2000


Content


Introduction

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.

Content


Straight Skeleton

Definition

A Shrinking Process

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.

Wave Propagation

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.

Terms

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

Some Properties

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.

Content


Algorithm

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).

Overview

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.

Description

We initially generate wavefronts by making a copy of each figures of G. Then we triangulate G. We will call spokes the diagonals of the triangulation. Triangles can collapse in one of 3 ways (figure 8):
EventWhen it occursWhat 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 eventEdge 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.

3 ways that a triangle can collapse
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.

Content


Complexity Analysis

Time Complexity

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).

Space Complexity

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.

A Subquadratic Algorithm

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.

Content


From Straight Skeletons to Roofs

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.

Content


Examples

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.

Content


Other Applications

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.

Content


Applet

Description

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.

Quick Start

  1. 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).
  2. Click on the RUN button to start the simulation.

Other Features

Colours Used

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.

The Roof Applet

We need to have Java enabled to run the applet.

About the Implementation

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:
OSBrowserWorking?
LinuxNavigator 3No
LinuxNavigator 4Yes
Win95Navigator 4Yes

Limitations

Although straight skeletons can be defined for planar straight line graph and for polygons with holes, to simplify the implementation the applet will work only for simple polygons with no holes. Note that the applet does not perform a simplicity test.

Known Bug

The applet was tested with several polygons. On convex polygons, it seems to always work. On some non-convex polygons, sometimes it does not work for some unknown reason. It might be due to rounding errors and some adjustments might be required. I was able to make it work on these polygons, by drawing the polygon again with vertices in slightly different positions.

Content


References

  1. [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.

  2. [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.

  3. [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.

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

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

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

Content


Links

Content


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

Last updated on December 5, 2000.


Home