Writing Generic Digital Topology and Geometry Algorithms

This paper proposes a concise representation for the cells of n-dimensional finite regular grids: each cell is coded as one integer number. It induces a simple and generic framework for implementing classical digital topology data structures and algorithms. Discrete subsets of multidimensional images (e.g. regions, digital surfaces, cubical cell complexes) have then a common and compact representation. Moreover, algorithms have a straightforward and efficient implementation, which is independent from the dimension or sizes of digital images. To demonstrate that point, the following classical digital topology and geometry problems are studied: hyper-surface boundary extraction with scanning and tracking, computing geometric characteristics such as tangents and normals on hyper-surfaces, definition of incidence matrices for cubical complexes to compute (co-)homology groups. This framework has been implemented in an object-oriented language and basic operations as well as more complex functionnalities have been benchmarked