Medial axis computation for planar free-form shapes

被引：67

作者：

Aichholzer, O. ^{[2
]}

Aigner, W. ^{[2
]}

Aurenhammer, F. ^{[2
]}

Hackl, T. ^{[2
]}

Juettler, B. ^{[1
]}

Rabl, M. ^{[1
]}

机构：

[1] Johannes Kepler Univ Linz, A-4040 Linz, Austria

[2] Graz Univ Technol, A-8010 Graz, Austria

来源：

COMPUTER-AIDED DESIGN | 2009年 / 41卷 / 05期

基金：

奥地利科学基金会;

关键词：

Planar shape; Biarc approximation; Medial axis; Stability; Divide & conquer; Randomized algorithm; Numerical robustness; VORONOI DIAGRAM; CURVED BOUNDARIES; SIMPLE POLYGON; TRANSFORM; ALGORITHM; DOMAINS; APPROXIMATION; SEGMENTS;

D O I：

10.1016/j.cad.2008.08.008

中图分类号：

TP31 [计算机软件];

学科分类号：

081205 [计算机软件];

摘要：

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. (C) 2008 Elsevier Ltd. All rights reserved.

引用

页码：339 / 349

页数：11

共 34 条

[1]

AICHHOLZER O, 2007, LECT NOTES COMPUT SC, P374

[2]

Aigner W., 2007, THESIS U TECHNOLOGY

[3]

The Voronoi diagram of curved objects [J].