Fast Approach For Computing The Medial Axis Of Simple Polygons

The computation problem of medial axis has a wide range of applications in the fields of model analysis,computer vision and geometric modeling,such as feature extraction.The medial axis computation problem of simple polygons has attracted more and more research interest.In this paper,a fast method based on tree reconstruction for computing the medial axis of a simple polygon is proposed.The main contents include the following two points:(1)A fast method for computing the medial axis of a simple polygon.A simple polygon is a closed polygon composed of straight line segments that are not self-intersecting,and has no inside holes.It is pointed out that the medial axis of a simple polygon can be represented as a tree structure,and each branch of the tree denotes a line segment or a parabolic segment.The whole medial axis can be analytically represented.In this paper,a tree reconstruction based method is proposed.The medial axis is reconstructed from the leaf nodes according to breadth-first strategy.A lot of numerical experiments have shown that the proposed method achieves linear computational complexity.Numerical results show that the method achieves much higher computational efficiency than those of prevailing methods.(2)A fast method for computing the medial axis of a curvilinear polygon.A simple curvilinear polygon is a closed curvilinear polygon which consists of arc segments and line segments,at the same time,it is not self-intersecting and contains no inside holes.The histogram based methods cannot be directly extended to the curvilinear polygon case.The medial axis of a simple curvilinear polygon can also be represented as a tree structure,in which each branch denotes a line segment,a parabolic segment,an elliptical arc,or a hyperbolic segment.In this paper,the tree reconstruction based method is proposed for the case of curvilinear polygons.In principle,the medial axis of the curvilinear polygon can also be represented analytically.The computational complexity for the curvilinear polygon case should be equal to that of the simple polygon case.Numerical examples show that the proposed algorithm has linear algorithm complexity and achieves much higher computational efficiency than those of prevailing method.