A dimension-independent extrusion algorithm using generalised maps

Abstract

One solution to the integration of additional characteristics, for example, time and scale, into GIS data sets is to model them as extra geometric dimensions perpendicular to the spatial ones, creating a higher-dimensional model. While this approach has been previously described and advocated, it is scarcely used in practice because of a lack of high-level construction algorithms and accompanying implementations. We present in this paper a dimension-independent extrusion algorithm permitting us to construct from any (n–1)-dimensional linear cell complex represented as a generalised map, an n-dimensional one by assigning to each (n–1)-cell one or more intervals where it exists along the nth dimension. We have implemented the algorithm in C++11 using CGAL, made the source code publicly available and tested it in experiments using real-world 2D GIS data sets which were extruded to construct up to 5D models.

Keywords:

• extrusion
• generalised maps
• n-dimensional
• GIS

Acknowledgements

We are grateful to the anonymous reviewers who provided us with very thorough reviews that helped to greatly improve this article. This research was supported by the Dutch Technology Foundation STW, which is part of the Netherlands Organisation for Scientific Research (NWO), and which is partly funded by the Ministry of Economic Affairs (project code: 11300).

Notes

1. This is equivalent to an edge in Lienhardt et al. (2004) or a 1D polyhedron in Ferrucci (1993).

2. Not in the sense of a stack as a data structure, but as a pile of simplices arranged vertically along the nth dimension.

3. This is always true combinatorially, but it might not be true geometrically if the (n–1)-simplex is not embedded so as to lie in the interior of the cell.

4. More precisely, the sweeping shape used in extruding a $(n-1)$-dimensional space partition is a shape that is unbounded along $n-1$ dimensions in nD space, for example, a line in ${\mathbb{R}}^2$ or a plane in ${ℝ}^3$.

5. That is checking that the links between darts correctly form involutions, and all the darts in the orbit of an i-cell are linked to its correct i-attribute and vice versa. See Lienhardt (1994) for the exact definition of what this means.