STABLE COMPUTATION OF THE 2D MEDIAL AXIS TRANSFORM

The medial axis transform of a 2D region was introduced by Blum in the 1960's as an aid to the description of biological shape. It is an alt ernative representation of a region which is often more amenable to an alysis. This property has led to its use in diverse fields including p attern recognition and automatic finite element mesh generation. There are two widely agreed mathematical definitions for the medial axis tr ansform which are closely related. It is shown that these definitions are not in general equivalent, despite being so for many types of regi on. In this paper, precise mathematical definitions of the medial axis transform and its key points (atoms) are given, and an O(n(2)) algori thm for its computation via those atoms presented. This algorithm is d escribed in terms of simple polygons whose sole boundary consists of c ircular arcs and straight line segments, then extended to polygons wit h holes. It is shown how more complex edges could be accommodated. In comparison with existing algorithms it is simple to implement and stab le in the presence of geometric degeneracy.