Medial axis computation for planar free-form shapes

作者：Aichholzer O; Aigner W; Aurenhammer F; Hackl T; Juettler B^*; Rabl M

来源：CAD Computer Aided Design, 2009, 41(5): 339-349.

DOI：10.1016/j.cad.2008.08.008

• Planar shape
• Biarc approximation
• Medial axis
• Stability
• Divide & conquer
• Randomized algorithm
• Numerical robustness

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.

• 出版日期2009-5