Decomposition of complex two-dimensional shapes into simple convex shapes

Abstract

Decomposing a complex shape into visually significant parts comes naturally for humans, and turns out to be very useful in areas such as shape analysis, shape matching, recognition, topology extraction, collision detection and other geometric processing methods [1]. After analysis it was found that the Minimum Near-Convex Decomposition (MNCD) method [2] is one of the most promising algorithms currently available that shows room for improvement. The focus of this dissertation is to make an improvement on the time it takes to decompose a complex shape, while keeping the decomposition (number of parts) results the same. One improvement that was implemented was to neglect the Morse function, as this takes a long time to execute. Another improvement was to make use of Delaunay Triangulation (DT) instead of considering all of the vertices, as no overlapping will take place and the need for the non-overlapping matrix is no longer necessary. Experimental results show that an average time reduction of 58%, but an increase in the number of parts. Thus there is an improvement made on the duration of the algorithm, but there is room to improve on the total amount of parts obtained after decomposition.