A graph-theoretic method for decomposing two-dimensional polygonal shapes into meaningful parts

Area of Science:

• Computer Vision
• Computational Geometry
• Graph Theory

Background:

• Existing shape decomposition methods face challenges with complex shapes.
• Graph-theoretic clustering offers a framework for shape analysis.
• Artificial separation and concavities complicate decomposition.

Purpose of the Study:

• To present a novel graph-theoretic shape decomposition procedure.
• To extend prior work on shape decomposition by Shapiro and Haralick.
• To address limitations in handling shape separations and concavities.

Main Methods:

• Utilizes a binary matrix to represent the LI relation.
• Extends graph-theoretic clustering for shape analysis.
• Proposes solutions for artificial separations and regular concavities.

Main Results:

• Achieves nonoverlapping shape parts.
• Demonstrates significantly reduced execution time.
• Provides a robust decomposition for complex shapes.

Conclusions:

• The proposed graph-theoretic procedure offers an efficient and effective method for shape decomposition.
• The algorithm successfully handles challenging cases like artificial separations and concavities.
• This work advances the field of computational shape analysis with practical improvements.