TWO METHODS FOR FINDING CONVEX HULLS OF PLANAR FIGURES

Abstract Two new methods are described for finding the vertices of the convex hull of a planar figure. Both were derived conceptually from Rosenfeld and Kak's technique but are much faster. One uses chain coding and the other a list of the vertices of a polygonal approximation of the edge of the figure. Both methods allow the concavities to be isolated easily and specified in the same format as the input data. The methods thus lend themselves admirably to the development of concavity trees as shape descriptors.