TY - JOUR
T1 - Approximate convex decomposition of polygons
AU - Lien, Jyh Ming
AU - Amato, Nancy M.
N1 - Funding Information:
✩ This research supported in part by NSF Grants ACI-9872126, EIA-9975018, EIA-0103742, EIA-9805823, ACR-0081510, ACR-0113971, CCR-0113974, EIA-9810937, EIA-0079874, and by the Texas Higher Education Coordinating Board grant ATP-000512-0261-2001. A preliminary version of this work appeared in the Proceedings of the ACM Symposium on Computational Geometry 2004 [J.-M. Lien, N. M. Amato, Approximate convex decomposition of polygons, in: Proc. 20th Annual ACM Symp. Computat. Geom. (SoCG), June 2004, pp. 17–26]. * Corresponding author. E-mail addresses: [email protected] (J.-M. Lien), [email protected] (N.M. Amato).
PY - 2006/8
Y1 - 2006/8
N2 - 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/.
AB - 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/.
KW - Convex decomposition
KW - Hierarchical
KW - Polygon
UR - http://www.scopus.com/inward/record.url?scp=33646802342&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=33646802342&partnerID=8YFLogxK
U2 - 10.1016/j.comgeo.2005.10.005
DO - 10.1016/j.comgeo.2005.10.005
M3 - Article
AN - SCOPUS:33646802342
SN - 0925-7721
VL - 35
SP - 100
EP - 123
JO - Computational Geometry: Theory and Applications
JF - Computational Geometry: Theory and Applications
IS - 1-2 SPEC. ISS.
ER -