Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
440455 | Computer-Aided Design | 2009 | 11 Pages |
Abstract
We present a simple, efficient, and stable method for computing—with any desired precision—the medial axis of simply connected planar domains. The domain boundaries are assumed to be given as polynomial spline curves. Our approach combines known results from the field of geometric approximation theory with a new algorithm from the field of computational geometry. Challenging steps are (1) the approximation of the boundary spline such that the medial axis is geometrically stable, and (2) the efficient decomposition of the domain into base cases where the medial axis can be computed directly and exactly. We solve these problems via spiral biarc approximation and a randomized divide & conquer algorithm.
Related Topics
Physical Sciences and Engineering
Computer Science
Computer Graphics and Computer-Aided Design
Authors
O. Aichholzer, W. Aigner, F. Aurenhammer, T. Hackl, B. Jüttler, M. Rabl,