A combinatorial algorithm to construct 3D isothetic covers

Abstract

Three-dimensional (3D) isothetic outer (inner) cover of a digital object is a 3D polytope of minimum (maximum) volume defined w.r.t. an underlying grid, having surfaces parallel to the coordinate planes, and circumscribing (inscribing) the entire object. It is useful for a unique approximation of 3D objects and to obtain shape-related information. We propose here a combinatorial algorithm for construction of such outer and inner covers of a 3D object imposed on the background grid. The algorithm consists of two passes. In the first pass, the unit faces on the surface of the cover are detected and stored in a doubly connected edge list (DCEL). In the second pass, an efficient merging of contiguous and coplanar unit faces from the DCEL produces a compact representation of the cover. The accuracy of the cover can be adjusted by changing the face planes, whether placed uniformly or non-uniformly. Experimental results demonstrate the effectiveness of the algorithm.

Keywords:

• object approximation
• object representation
• isothetic cover
• isothetic polytope
• shape analysis

2010 AMS Subject Classifications::

• 51H99
• 52B10
• 65D18
• 68U05
• 68U10

Acknowledgement

A part of this research is funded by Council of Scientific and Industrial Research (CSIR), Government of India.

Notes

A preliminary version appeared in 22.