Přejít k hlavnímu obsahu
top

Bibliografie

Journal Article

CLOSE-TO-OPTIMAL ALGORITHM FOR RECTANGULAR DECOMPOSITION OF 3D SHAPES

Höschl Cyril, Flusser Jan

: Kybernetika vol.55, 5 (2019), p. 755-781

: GA18-07247S, GA ČR

: 3D binary object, voxels, decomposition

: 10.14736/kyb-2019-5-0755

: http://library.utia.cas.cz/separaty/2019/ZOI/flusser-0518087.pdf

: https://www.kybernetika.cz/content/2019/5/755

(eng): In this paper, we propose a novel algorithm for a decomposition of 3D binary shapes to rectangular blocks. The aim is to minimize the number of blocks. Theoretically optimal brute-force algorithm is known to be NP-hard and practically infeasible. We introduce its suboptimal polynomial heuristic approximation, which transforms the decomposition problem onto a graph-theoretical problem. We compare its performance with the state of the art Octree and Delta methods. We show by extensive experiments that the proposed method outperforms the existing ones in terms of the number of blocks on statistically signifficant level. We also discuss potential applications of the method in image processing.

: JD

: 10201