Computing medial axis of a simple polygon in linear time based on R-L sequence

Abstract

Medial axis computation has wide applications in pattern recognition, image processing, finite element mesh generation, and CNC tool path extraction. Aiming to explore intrinsic geometric attributes of the medial axis of a simple polygon which can be accurately represented and faces its challenge of computational efficiency, an R-L sequence-based algorithm of linear computational complexity is proposed for achieving much higher efficiency; especially, it enables the complexity of Delaunay triangulation to be linear. The algorithm is done by reconstructing the Voronoi diagram tree of the given simple polygon, which can be easily performed in a breadth-first manner with a higher computational efficiency. The branches of the medial axis are naturally divided into several panels, such that the branches in the same panel cause no interference with each other and decrease a lot of computational costs. Based on our experiments, the efficiency of the proposed R-L algorithm can be 6 to 17 times greater than that of the state-of-the-art method in TVCG, and up to 419 times greater than the CGAL algorithm. In principle, it can be directly applied to compute the medial axis of curvilinear polygons, which expands the scope of application compared to Chin’s method.

Keywords

• Medial axis transformation
• Simple polygon
• R-L sequence-based method
• Linear complexity