In this paper, we present a new approximate algorithm for medial axis transform of a plane domain. The underlying phiregion yields an intuitively pleasing skeleton, direct implelosophy of our approach is the localization idea based on the mentation of that definition is typically prohibitive compu-Domain Decomposition Lemma, which enables us to break up tationally' ' [7, p. 491]. In this paper, we show that this is the complicated domain into smaller and simpler pieces. We not the case under mild and realistic assumptions on the then develop tree data structure and various operations on domain. Namely, we present an efficient and reasonably it to keep track of the information produced by the domain robust algorithm for the medial axis transform under the decomposition procedure. This strategy enables us to isolate assumption that the domain has finitely many boundary various important points such as branch points and terminal curves which consist of a finite number of real analytic points. Because our data structure guarantees the existence of pieces.
such important points-in fact, our data structure is devised It is perhaps important to mention the relevance of our with this in mind-we can zoom in on those points. This makes our algorithm efficient. Our algorithm is a ''from within'' ap-domain assumption. Contrary to common belief, it is not proach, whereas traditional methods use a ''from-the-boundenough to assume the boundary curve is C ศ . In fact, as ary'' approach. This ''from within'' nature of our algorithm pointed out in [3], there are plenty of domains with C ศ and the localization scheme help mitigate various instability boundary whose medial axes are infinite graphs. In fact, phenomena, thereby making our algorithm reasonably it is possible to create all kinds of pathological examples robust. ยฉ 1997 Academic Press with the C ศ assumption on the boundary. This kind of pathology makes it very difficult to design a workable algorithm. However, if the boundary curve is made up of real 1. INTRODUCTION analytic pieces, these pathologies disappear. Fortunately, this kind of restriction poses no real loss in most practical The medial axis transform, which was originally procases, since all domains that have practical importance posed in [2], is a very important concept which is widely have this property. For instance, the boundary curves may used in many different contexts: for example, besides being be represented as splines or NURBS curves, which fall useful in computer aided geometric design as a means into this category. We cannot help believing that our asof generating the offset curves in NC machine tool path sumption is the most natural and optimal in practice, beplanning, it is used to represent information of a shape cause it is inclusive enough to cover all practical situations, compactly in vision and pattern recognition. (Historically, while at the same time restrictive enough to yield results before Blum, Dirichlet [5] and Voronoi [22] studied a disas expected in practice. crete point version of the medial axis and this is still called Our algorithm is based on the mathematical theory dea Dirichlet tessellation or a Voronoi diagram.)
veloped in [3], but our algorithmic approach has its own Although the medial axis transform is a very useful dedistinctively different flavor. The underlying philosophy of our algorithm is the localization idea based on the Domain 1 Supported in part by BSRI, GARC, and Hyundai Media Systems Decomposition Lemma, which enables us to break up the Co., Ltd.