An Internal Direction-Based Algorithm for Medial Axis Transformation of an Arbitrary Polygon

The medial axis is an efficient description of the shape of the polygon, and it is widely used in the communities of geographic information systems, image processing, pattern recognition, computer-aided design, et al. For the purpose of placing annotations in polygons, a new algorithm for extracting medial axis has been proposed in this paper, which includes four procedures: (1) arrange the polygon data in anti-clockwise; (2) triangulate the polygon; (3) compute the diameter so that the start and end points of the medial axis is obtained; and (4) construct the medial axis step by step, using a linked list. The algorithm has been realized in Visual C++, and the experiments shows that it is correct and practical.