Motorcycle Graphs and Straight Skeletons

Aichholzer et al. (1995) introduced the straight skeleton of a simple polygon as a skeleton structure similar to Voronoi diagrams. Roughly speaking, the straight skeleton of a simple polygon is defined by a wavefront propagation process where the edges move inwards in a self-parallel manner. The traces of the moving vertices of this process form the straight skeleton.

Straight skeletons share a large number of applications with Voronoi diagrams, with straight-line offsetting of simple polygons being just one illustrative example. The list of applications also includes roof and terrain generation, mathematical origamis, polygon decomposition, surface reconstruction and a few more applications in geographical information systems (GIS).

A motorcycle is a point moving on a straight line with a given start point and a fixed velocity. While each motorcycle drives it leaves a trace behind. However, when a motorcycle reaches the trace of another motorcycle then it stops driving -- it "crashes" -- but the trace remains. The arrangement of these traces is commonly known as motorcycle graph. Note that not every motorcycle necessarily crashes into another motorcycle. Rather, some motorcycles may "escape".

Motorcycle graphs bear a close relation to straight skeletons for several reasons: first of all, it can be shown that those parts of the straight skeleton of a simple polygon which emanate from reflex vertices are a subset of the motorcycle graph, where the motorcycles correspond to the moving reflex vertices during the offset propagation process. Secondly, the fastest algorithm known for computing the straight skeleton of simple polygons, by Cheng and Vigneron, uses the motorcycle graph as a preprocessing step.

In joint work with Stefan Huber, we proved that the edges of a properly generalized motorcycle graph cover a specific subset of the edges of the straight skeleton of a planar straight-line graph, and that they form the basis of 3D slabs such that the projection of the lower envelope of those slabs to the plane forms the straight skeleton. This result allow us to employ the motorcycle graph in order to improve the classical wavefront-type algorithm by Aichholzer and Aurenhammer (1998).

Our algorithm is easy to implement and fast enough to be applicable to complex real-world data. As it turns out, our implementation, STALGO, achieves on average a performance boost of one to two orders of magnitude, or of a multiplicative factor in the size of the input, for moderate-sized datasets of up to 10000 vertices. Moreover, in contrast to the CGAL implementation, our code is able to handle datasets with a million (or more) vertices on a standard PC. Thus, the implementation of our algorithm is the first code which is capable of handling complex real-world datasets.

The source codes for STALGO is available for both academic and commercial use. It consists of MOCA for computing the motorcycle graph, and of BONE for computing the actual skeleton. Send me an email and I will let you know the details of how you could use STALGO. However, in order to avoid disappointment, let me warn you upfront that STALGO has not been released into the public domain!

This research was supported by the Austrian FWF Grant L367-N15. You may also want to see our more recent work on weighted straight skeletons.

				A tribute to STALGO's designer. The left image shows the straight skeleton, while the right image shows a family of polygonal offsets. (Click on the thumbnails to see larger images.)
				A "Bone" watch. The left image shows the straight skeleton, while the right image shows a family of polygonal offsets. (Click on the thumbnails to see larger images.)

A terrain that models the valley of the Danube near Schlögen (Austria). The left image shows a family of polygonal offsets computed by means of the straight skeleton, while the right image shows the corresponding 3D terrain. (Click on the thumbnails to see larger images.)

T. Biedl, M. Held, S. Huber (2013):
"Reconstructing Polygons from Embedded Straight Skeletons".
Proc. 29th Europ. Workshop Computational Geometry, p. 95-98, Braunschweig, Germany, March 2013.

S. Huber, M. Held (2012):
"A Fast Straight-Skeleton Algorithm Based on Generalized Motorcycle Graphs".
Int. J. Computational Geometry and Applications, 22(5):471-498, Oct 2012.

O. Aichholzer, H. Cheng, S.L. Devadoss, T. Hackl, S. Huber, B. Li, A. Risteski (2012):
"What makes a Tree a Straight Skeleton?".
Proc. 24th Canadian Conf. on Computational Geometry, p. 267-272, Charlottetown, P.E.I., Canada, Aug 2012.

S. Huber (2012):
"Computing Straight Skeletons and Motorcycle Graphs: Theory and Practice".
Shaker Verlag, ISBN 978-3-8440-0938-5, Apr 2012.

O. Aichholzer, H. Cheng, S.L. Devadoss, T. Hackl, S. Huber, B. Li, A. Risteski (2012):
"What makes a Tree a Straight Skeleton?".
Proc. 28th Europ. Workshop Computational Geometry, p. 137-140, Assisi, Perugia, Italy, Mar 2012.

S. Huber, M. Held (2011):
"Motorcycle Graphs: Stochastic Properties Motivate an Efficient Yet Simple Implementation".
ACM J. on Experimental Algorithmics, Vol 16, p. 1.3:1.1--1.3:1.17, May 2011.

S. Huber, M. Held (2011):
"Theoretical and Practical Results on Straight Skeletons of Planar Straight-Line Graphs".
Proc. 27th Annual Symp. on Computational Geometry, p. 171-178, Paris, France, June 2011.

S. Huber, M. Held (2011):
"Approximating a Motorcycle Graph by a Straight Skeleton".
Proc. 23rd Canadian Conf. on Computational Geometry, p. 489-494, Toronto, Canada, Aug 2011.

S. Huber, M. Held (2010):
"Computing Straight Skeletons of Planar Straight-Line Graphs Based on Motorcycle Graphs".
Proc. 22nd Canadian Conf. on Computational Geometry, p. 187--190, Winnipeg, Canada, Aug 2010.

S. Huber, M. Held (2010):
"Straight Skeletons and their Relation to Triangulations".
Proc. 26th Europ. Workshop Computational Geometry, p. 189--192, Dortmund, Germany, March 2010.

S. Huber, M. Held (2009):
"A Practice-Minded Approach to Computing Motorcycle Graphs".
Proc. 25th Europ. Workshop Computational Geometry, p. 305--308, Brussels, Belgium, March 2009.

file last modified: Friday, 14-Apr-2023 08:22:39 CEST held@cs.sbg.ac.at Copyright © 2024 Martin Held. All rights reserved.