A simplex-based approach to implement dimension independent spatial analyses

Many applications in geosciences need to deal with 3D objects. For this, among other requirements, 2D spatial analyses must be extended to support 3D objects. This extension is an important research topic in GIS and computational geometry. Approaches that extend an existing algorithm for a 2D spatial analysis to work for 3D or higher dimensions lead to different algorithms and implementations for different dimensions. Following such approaches the code for a package that supports spatial analyses for both 2D and 3D cases is nearly two times the code size for 2D. While dimension independent algorithms are an alternative toward generalization, they are still implemented separately for each dimension. The main reason is that each dimension is modeled using a different data structure that requires its own implementation details. In this article we use the list data structure to implement n-simplexes—as a data type that supports spatial objects of any dimension. Primitive operations on n-simplexes become manipulating functions over lists, which are independent of the number and type of the elements. We define spatial analyses as combinations of primitive operations on n-simplexes. Since the primitive operations on n-simplexes have been implemented independently of dimension, the spatial analyses are dimension independent, too. Construction of Delaunay triangulation of nD points, as the basic data structure for many geoscientific researches, is used here as the running example. The implementation results for Delaunay triangulation of some 2D and 3D points are presented and discussed. As a case study the implementations are used to calculate the area and volume of the reservoir of a dam at different water levels, which leads to a level–surface–volume diagram.