Shape Hierarchies

Shape hierarchies provide a means to deal with complex geometry, such as that created with CAD programs. It is often desirable to access particular submodels of a large geometric model, and hierarchies provide the means to do this. Examples of operations that can be applied to submodels are:

Mapping by an affine transform
Training a vision tool
Rendering (rasterizing)
Selection through a GUI

Hierarchies can also be used to make certain algorithms more efficient. For example, computing the closest point to a complex geometric model is faster if the geometry is arranged in a bounding box hierarchy.

Closed curves may define regions of the plane, these regions may have holes defined by other closed curves, these holes might have solid islands within them, and so on. Hierarchies provide a way to capture the salient relationships among nested regions, and to facilitate functionality such as inside/outside queries.

Hierarchies also provide a way to express the results of certain operations on primitive shapes. For example, clipping an annulus may generate a different annulus, or a C-shaped object without holes, or several disconnected regions. In general, clipping a single shape can lead to an arbitrary number of new shapes, possibly of different types than the original. Hierarchies provide a way to model the significant geometric modifications that can result from operations such as clipping. Mapping by an affine transform is another operation that may lead to a hierarchy of shapes when applied to a primitive shape.

Finally, shape hierarchies provide a general framework to represent boundaries and regions generated, consumed, and returned by vision tools. Having a common representation for describing boundaries and regions makes it easier to write code that uses these tools.