Generic Components for Grid Data Structures and Algorithms with C++

Guntram Berti
Institut für Mathematik, BTU Cottbus, Germany

Abstract:

Grids are fundamental data structures for representing geometric structures or their subdivisions. We propose a strategy for decoupling algorithms working on grids from the details of grid representations, using a generic programming approach in C++. Functionality of grid data structures is captured by a small set of primitives, divided into combinatorial and geometric ones. Special attention is paid to the generic implementation of grid functions, which correspond to the notion of mappings from grid elements (e. g. vertices) to entities of a given type. Experiments indicate that the overhead of the generic formulation is low and can be completely eliminated in some cases.