A FAST STRAIGHT-SKELETON ALGORITHM BASED ON GENERALIZED MOTORCYCLE GRAPHS
A FAST STRAIGHT-SKELETON ALGORITHM BASED ON GENERALIZED MOTORCYCLE GRAPHS
复制标题
DOI：
10.1142/s0218195912500124
复制
发表时间：
2012-10-01
影响因子：
--
通讯作者：
Held, Martin
中科院分区：
文献类型：
--
作者：
Huber, Stefan;Held, Martin
本文讨论了工业强度水平上的平面直线图（PSLG）的直骨架的快速计算。我们讨论我们的算法和工程方面的理论基础，我们的实施骨。我们的调查开始与三角形为基础的算法Aichholzer和Aurenhammer的分析，我们证明了存在的翻转事件免费斯坦纳三角。这一结果促使摩托车图的仔细推广，使其密切的几何连接直骨架保持。基于广义摩托车图，我们设计了PSLG直骨架的非过程刻画，并讨论了如何通过图形绘制获得直骨架的离散化版本。最重要的是，这种推广使我们能够提出一个快速和易于实现的直骨架算法，我们实现了我们的算法在C++基于浮点运算。在22300个不同特征的数据集上，我们的代码BONE的大量基准测试表明了O（n long n）的时间复杂度和O（n）的内存占用。这是一个比CGAL 4.0提供的实现更好的线性因素，CGAL 4.0显示了O（n（2）log n）的时间复杂度和O（n（2））的内存占用; CGAL代码是迄今为止唯一功能齐全的直骨架代码。特别是，在具有一万个顶点的数据集上，Bone需要大约0.20.6秒，而不是CGAL代码消耗的47分钟，并且BONE仅使用20 MB堆内存，而不是几GB。最后，我们讨论了BONE的工程方面和原理，这些方面和原理使BONE足够可靠，可以在台式计算机上计算包含数百万个顶点的数据集的直骨架。
This paper deals with the fast computation of straight skeletons of planar straight-line graphs (PSLGs) at an industrial-strength level. We discuss both the theoretical foundations of our algorithm and the engineering aspects of our implementation BONE. Our investigation starts with an analysis of the triangulation-based algorithm by Aichholzer and Aurenhammer and we prove the existence of flip-event-free Steiner triangulations. This result motivates a careful generalization of motorcycle graphs such that their intimate geometric connection to straight skeletons is maintained. Based on the generalized motorcycle graph, we devise a non-procedural characterization of straight skeletons of PSLGs and we discuss how to obtain a discretized version of a straight skeleton by means of graphics rendering. Most importantly, this generalization allows us to present a fast and easy-to-implement straight-skeleton algorithm.We implemented our algorithm in C++ based on floating-point arithmetic. Extensive benchmarks with our code BONE demonstrate an O(n long n) time complexity and O(n) memory footprint on 22 300 datasets of diverse characteristics. This is a linear factor better than the implementation provided by CGAL 4.0, which shows an O(n(2) log n) time complexity and an O(n(2)) memory footprint; the CGAL code has been the only fully-functional straight-skeleton code so far. In particular, on datasets with ten thousand vertices, Bone requires about 0.20.6 seconds instead of 47 minutes consumed by the CGAL code, and BONE uses only 20 MB heap memory instead of several gigabytes. We conclude our paper with a discussion of the engineering aspects and principles that make BONE reliable enough to compute the straight skeleton of datasets comprising a few million vertices on a desktop computer.