Abstract
Medial axis computation (MAC) has many applications in computer-aided design, computer graphics, automated mesh generation, solid modeling, CNC tool path generation, robotic motion planning, bioinformatics, and shape analysis. There are three key issues that need to be further addressed on MAC of a NURBS(Non-Uniform Rational B-Spline) curve boundary, namely (1) computation of regular medial axis points; (2) efficient detection of the existence of a branch point where two branches intersect; and (3) convergence and correctness on computing the position of a branch point. This paper presents a competition flow method for medial axis computation of a planar simply-connected NURBS boundary. Different from previous methods which trace a Voronoi Diagram Tree (VDT) in depth-first order from a terminal point, the competition flow method (CFM) traces the corresponding tree in breadth-first order. It has three main contributions. Firstly, it utilizes an optimized method based on previous state-of-art algorithms for computing regular medial axis points, which can achieve a higher computational efficiency. Secondly, it implements a divide-and-conquer method in a natural way by proposing a simple tree technique, in which a VDT is divided into several simple tree structures of level l, l=0,1,… for competitive medial axis computation. Finally, by using the competition flow method, possible places where branch points are located, are intuitively and efficiently detected and bounded with high precision, which ensures the convergence and the correctness of the computation of the position of a branch point, and also ensures the correctness of the topological structure of the medial axis tree. Numerical examples show that the new method can achieve a better performance compared with several existing methods.
| Original language | English |
|---|---|
| Pages (from-to) | 342-359 |
| Journal | Journal of Computational and Applied Mathematics |
| Volume | 340 |
| Online published | 13 Mar 2018 |
| DOIs | |
| Publication status | Published - 1 Oct 2018 |
Research Keywords
- Breadth-first order
- Competition flow method
- Medial axis
- NURBS boundary
- Parameter interval interference check
- Robustness
Fingerprint
Dive into the research topics of 'A competition flow method for computing medial axis transform'. Together they form a unique fingerprint.Cite this
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver