Approximate convex decomposition of polygons

Jyh Ming Lien, Nancy M. Amato

Research output: Contribution to journalArticlepeer-review

Abstract

We propose a strategy to decompose a polygon, containing zero or more holes, into "approximately convex" pieces. For many applications, the approximately convex components of this decomposition provide similar benefits as convex components, while the resulting decomposition is significantly smaller and can be computed more efficiently. Moreover, our approximate convex decomposition (ACD) provides a mechanism to focus on key structural features and ignore less significant artifacts such as wrinkles and surface texture. We propose a simple algorithm that computes an ACD of a polygon by iteratively removing (resolving) the most significant non-convex feature (notch). As a by product, it produces an elegant hierarchical representation that provides a series of 'increasingly convex' decompositions. A user specified tolerance determines the degree of concavity that will be allowed in the lowest level of the hierarchy. Our algorithm computes an ACD of a simple polygon with n vertices and r notches in O(nr) time. In contrast, exact convex decomposition is NP-hard or, if the polygon has no holes, takes O(n r2) time. Models and movies can be found on our web-pages at: http://parasol.tamu.edu/groups/ amatogroup/.

Original languageEnglish (US)
Pages (from-to)100-123
Number of pages24
JournalComputational Geometry: Theory and Applications
Volume35
Issue number1-2 SPEC. ISS.
DOIs
StatePublished - Aug 2006
Externally publishedYes

Keywords

  • Convex decomposition
  • Hierarchical
  • Polygon

ASJC Scopus subject areas

  • Computer Science Applications
  • Geometry and Topology
  • Control and Optimization
  • Computational Theory and Mathematics
  • Computational Mathematics

Fingerprint

Dive into the research topics of 'Approximate convex decomposition of polygons'. Together they form a unique fingerprint.

Cite this