Abstract
This paper presents a method
based on artificial intelligence (AI) techniques for decomposing
a two-dimensional polygon into a minimal
set of disjoint primitives. Decomposition is accomplished using
a search algorithm based on recursively splitting the given
shape into smaller parts until
a primitive is recognized. The method operates in a primitive-oriented
environment, where each primitive
type must provide three basic member functions, namely (a) a function
for recognizing a shape as the primitive, (b) a function
for suggesting new splitting curves for a given shape, and (c)
a function for optimistically estimating the number of
primitives required to tile
a shape. Optimality in the number of decomposition units can be
guaranteed subject to the domain spanned
by function (b). The proposed method produces a hierarchical decomposition
of the shape. Examples from a working
implementation are shown.