A competition flow method for computing medial axis transform

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review

1 Scopus Citations
View graph of relations



Original languageEnglish
Pages (from-to)342-359
Journal / PublicationJournal of Computational and Applied Mathematics
Online published13 Mar 2018
Publication statusPublished - 1 Oct 2018


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.

Research Area(s)

  • Breadth-first order, Competition flow method, Medial axis, NURBS boundary, Parameter interval interference check, Robustness