A straightforward algorithm for computing the medial axis of a simple polygon

1 January 1991

journal article
research article
Published by Taylor & Francis in International Journal of Computer Mathematics

Vol. 39 (1-2) , 51-60
https://doi.org/10.1080/00207169108803978

Abstract

A new algorithm for computing the medial axis of a simple polygon is presented. Although the algorithm runs in O(kN) time where k is the hierarchy of the Voronoi diagram of the polygon ranging from O(N) to O(logN) it is simple to implement and it does not require the complex data-structures required for the faster methods. This is an important factor in many applications of the medial axis.

Keywords

This publication has 9 references indexed in Scilit:

A straightforward iterative algorithm for the planar Voronoi diagram
Information Processing Letters, 1990
AnO(n logn) algorithm for the voronoi diagram of a set of simple curve segments
Discrete & Computational Geometry, 1987
Computational Geometry
Published by Springer Nature ,1985
Medial Axis Transformation of a Planar Shape
Published by Institute of Electrical and Electronics Engineers (IEEE) ,1982
Generalization of Voronoi Diagrams in the Plane
SIAM Journal on Computing, 1981
The line-skeleton
Computer Graphics and Image Processing, 1979
Efficient computation of continuous skeletons
Published by Institute of Electrical and Electronics Engineers (IEEE) ,1979
Shape description using weighted symmetric axis features
Pattern Recognition, 1978
The medial axis of a simple polygon
Lecture Notes in Computer Science, 1977