A fast algorithm for constructing approximate medial axis of polygons, using Steiner points

This paper presents a new algorithm for constructing the approximation of a polygon’s medial axis. The algorithm works in three steps. Firstly, constrained Delaunay triangulation of a polygon is done. After that, the obtained triangulation is heuristically corrected by inserting Steiner points. Finally, the obtained triangles are classified into three classes, thus enabling the construction of the polygon’s medial axis. As shown by experiments, the obtained approximate polygon medial axis has better properties than those methods based on a Voronoi diagram.

► A new algorithm for constructing an approximated medial axis is introduced.
► The algorithm constructs medial axis on polygons with or without holes.
► Solution is based on constrained Delaunay triangulation and Steiner points.
► Comparison between presented algorithm and other methods are given.
► Proposed approach exposes better performances.