Analyzing Nonconvex 2D and 3D Patterns

摘要

A nonconvex pattern can be analyzed by describing its concavity regions. These can be identified by computing the difference between the convex hull of the pattern and the pattern itself. A suitable approximation of the convex hull can be obtained by repeatedly filling local concavities of the pattern. Parallel and sequential algorithms are proposed, to fill concavities of 2D and 3D patterns. The resulting approximation of the convex hull is a covering polygon or polyhedron, which is either convex or nearly convex. Exact measures of worst remaining concavities and created protrusions are given. The concavity regions are extracted and different features are presented and computed. Hierarchical pattern descriptions are also suggested, based on the use of concavity trees.