Construction of 3D Orthogonal Cover
(A combinatorial algorithm to find the minimum-volume cover of a 3D voxel set using DCEL)
Algorithm:
N. Karmakar, A. Biswas, P. Bhowmick, and B.B. Bhattacharya,
A
Combinatorial Algorithm to Construct 3D Isothetic Covers,
International Journal of Computer Mathematics, Vol. 90(8), pp. 1571-1606, 2013.
A preliminary version appeared in:
Construction of 3D Orthogonal Cover of a Digital Object,
14th International Workshop on Combinatorial Image Analysis: IWCIA'11, Madrid, Spain,
Lecture Notes in Computer Science (LNCS), Springer, Vol. 6636, pp. 70-83, 2011.
The Idea: The orthogonal cover of a 3D digital object is a minimum-volume 3D polytope
having surfaces parallel to the coordinate planes, and containing the entire object so as to capture
its approximate shape information.
We have designed an efficient algorithm for construction of such an orthogonal cover imposed
on a 3D background grid.
A combinatorial technique is used to classify the grid faces constituting the polytope
while traversing along the surface of the object in a breadth-first manner.
The eligible grid faces are stored in a doubly connected edge list (DCEL),
using which the faces are finally merged to derive the isothetic polygons parallel
to the coordinate planes, thereby obtaining the orthogonal cover of the object.
The complexity of the cover decreases with increasing grid size.
The algorithm requires computations in integer domain only and runs in a time linear in
the number of voxels constituting the object surface.
|
|
