New Framework for Decomposing a Polygon with Zero or More Holes

ABSTRACT

In this paper, we propose a unified framework for decomposition of a polygon with or without holes, enlightened by approximate convex decomposition. We transform target polygon containing holes into the polygon without holes by merging holes into external boundary, thus only need to partition the polygon without holes. Several constraints are enforced to ensure generate more visually meaningful decompositions, more elegant final components than that of other methods. Moreover, we estimate tolerance 􀀁 from geometry information of target polygon to obtain a naturally visual decomposition, a polished hierarchical representation. Our approach computes a decomposition of a polygon, containing zero or more holes, 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 much more time. Many experimental results and applications are presented to show the superiority, applicability and flexibility of our approach.

Keywords:

approximate convex decomposition, constraints, hierarchical representation, holes, naturally visual decomposition, Polygon, tolerance δ.