Implementation of Weighted Straight Skeletons

The straight skeleton of a simple polygon in the plane is defined by considering the propagation of a so-called wavefront: Each edge of the polygon emits a wavefront edge moving towards the polygons interior in a self-parallel manner. All edges move at unit speed and start to move at the same time. During this propagation process, the topology of the wavefront changes due to self-interaction: An edge of the wavefront may shrink to zero length and thus vanish, or a vertex of the wavefront may move into the interior of a non-incident wavefront edge, thus splitting the wavefront polygon into two sub-polygons. The straight skeleton is the union of the traces of wavefront vertices over the entire wavefront propagation. Straight skeletons have diverse applications such as in tool-path generation, mathematical origami, automated roof design for buildings, and terrain generation. The definition of a straight skeleton can be extended to a planar straight-line graph, i.e., to a collection of straight-line segments in the plane which may not intersect except at common end points. In the FWF Projects L367-N15 and P25816-N15 we have studied additively and multiplicatively weighted straight skeletons of planar straight-line graphs where the input edges (1) are allowed to move at different speeds and (2) do not need to start moving at the same time. As a result, we get an automated generation of roofs of buildings where the individual roof facets have different inclinations and may start at different heights. My current PhD student Peter Palfrader cast our straight-skeleton algorithm into a proof-of-concept implementation. We propose to use our vast experience with the implementation of geometric algorithms for implementing our algorithm for computing weighted straight skeletons in a reliable and efficient way. We will strive to come up with code that can be either run on a conventional floating-point arithmetic or in conjunction with an EGC library, e.g., CGAL (Computational Geometry Algorithms Library). The resulting code will be made available to the general public under an open re-use license (GPL). In addition, we intend to offer it to CGAL for inclusion in their library. In order to facilitate a large-scale testing of our implementation we will get back to prior work of the applicant on the generation of pseudo-random polygons: We will devise and implement heuristics for generating polygonal test data at various ranges of complexity. While our primary focus is on getting input data for our own tests, the availability of such a test suite can be expected to foster future applied work by researchers and practitioners in computational geometry and its practical application fields, like GIS, CAD/CAM or architecture.

Computational geometry is a field of (theoretical) computer science which is concerned with the efficient solution of problems that bear a geometric flavor. Straight skeletons form a key data structure of computational geometry; they provide the algorithmic basis for efficient solutions to a variety of geometric problems in diverse fields of application, ranging from tool-path planning in CAD/CAM to shape reconstruction in medical imaging, roof modeling in architecture, the computation of centerlines of roads and rivers in geographic information systems, and even to computing so-called crease patterns in mathematical origami. Roughly, the straight skeleton of a simple polygon is defined by a wavefront propagation process. That is, one considers a shrinking process by which each polygon edge moves inwards at unit speed and in a self-parallel fashion. This moving wavefront mimics the input polygon, but its shape changes over time: edges may vanish and the wavefront may be split into parts. The straight skeleton is defined as the set of loci traced out by the vertices of the wavefront. The same principle can also be applied to planar straight-line graphs (PSLGs), i.e., to a set of straight-line segments in the plane that do not intersect each other in the interior. In this project we worked out the mathematical and algorithmical details of multi- plicatively weighted straight skeletons of PSLGs and devised an implementation in the programming language C++. Furthermore we developed and implemented an algorithm geared towards straight skeletons of monotone polygons. (A polygon is called monotone relative to a line ` if every line perdendicular to ` either does not intersect the polygon at all or if it intersects it in a point or single line segment.) The resulting implementa- tions, which are named Surfer2 and Monos, are based on exact arithmetic provided by the Computational Geometry Algorithms Library (Cgal). Both Surfer2 and Monos are provided unter the GPL license (version 3) free of charge on the platform GitHub. (GitHub is an online service that offers storage space and a version control system for software projects.) In addition we developed and implemented various software tools for generating polyg- onal test data. For instance, our tools are able to generate star-shaped and monotone polygons, or polygons whose edges are parallel to the two coordinate axes. Furthermore we implemented generators for some well-known fractal curves such as the Koch snowflake. All implementations of our generators were done in the programming languages C++ or C. They are provided unter the GPL license (version 3) free of charge on the platform GitHub. Sample polygonal datasets can be obtained directly (and for free) from the new Salzburg Database: https://sbgdb.cs.sbg.ac.at/.