III: Small: Geospatial Data Representation and Analysis through the Stellar Decomposition

This library includes the implementation of the Indexed data structure with Adjacencies (IA data structure) for the representation of triangle meshes. The IA data structure is a triangle-based data structure that encodes the vertices and the triangles of the mesh. The vertices of the meshes with their attributes are encoding in a vertex table. Each triangle is encoded in a triangle table as a triple of indexes to its vertices in the vertex table. The IA data structure also explicitly encodes, for each triangle, the indexes in the triangle table of its three bounding vertices, and for each vertex, the index of one triangle incident in the vertex. This enables the efficient retrieval of all connectivity relations. This library is developed based on the LibTri for terrain analysis, which includes state-of-the-art estimators for slope and curvature for triangulated surfaces (Triangulated Irregular Networks - TINs), and for the extraction of critical points from a TIN. For a description of the required libraries for building the library, the compilation process, the run-time options and of the supported input format, please refer to the github page of the repository listed above.

In this library we address the problem of performing efficient spatial and topological queries on large tetrahedral meshes with arbitrary topology and complex boundaries. Such meshes arise in several application domains, such as 3D Geographic Information Systems (GISs), scientific visualization, and finite element analysis. To this aim, we have defined the Tetrahedral trees, a family of spatial indexes based on a nested space subdivision (an octree or a kD-tree) and defined by several different subdivision criteria. In this library, we provide efficient algorithms for spatial and topological queries on Tetrahedral trees and it has been used for generating the results of the paper "Tetrahedral Trees: A Family of Hierarchical Spatial Indexes for Tetrahedral Meshes" by Riccardo Fellegara, Leila De Floriani, Paola Magillo, and Kenneth Weiss in ACM Transaction on Spatial Algorithms and Systems 6, 4, Article 23, 34 pages, 2020 [doi]. For a description of the required libraries for building the library, the compilation process, the run-time options and of the supported input format, please refer to the github page of the repository listed above.

In this library we address the problem of the efficient representation and management of simplicial and cell complexes in arbitrary dimension and with arbitrary domain. Managing complexes in three dimensions and higher is not a simple task, since the topological data structures proposed in the literature do not scale when the size and the dimension of a complex become high. We propose the Stellar library as a topological C++ framework for performing efficient topological queries on simplicial and non-simplicial meshes. The Stellar tree library provides a scalable and compact representation that encodes the minimal information to locally reconstruct the topological connectivity of its indexed elements. This provides the flexibility to efficiently construct the optimal data structures to solve the task at hand using a fraction of the memory required for a corresponding topological data structure on the global mesh. The efficiency of the Stellar library increases with the execution of successive queries, as the construction costs of these runtime data structures are amortized over multiple accesses while processing each node. This library has been used for generating the results of the paper "The Stellar decomposition: A compact representation for simplicial complexes and beyond" by Riccardo Fellegara, Kenneth Weiss, and Leila De Floriani in Elsevier Computer & Graphics journal, 98: 322-343, 2021 [doi]. A preprint of this article can be also fund on arXiv here. For a description of the required libraries for building the library, the compilation process, the run-time options and of the supported input format, please refer to the readme file available in the repository archive.

This library includes the implementation of the Indexed data structure with Adjacencies (IA data structure) for the representation of triangle meshes. The IA data structure is a triangle-based data structure that encodes the vertices and the triangles of the mesh. The vertices of the meshes with their attributes are encoding in a vertex table. Each triangle is encoded in a triangle table as a triple of indexes to its vertices in the vertex table. The IA data structure also explicitly encodes, for each triangle, the indexes in the triangle table of its three bounding vertices, and for each vertex, the index of one triangle incident in the vertex. This enables the efficient retrieval of all connectivity relations. This library is developed based on the LibTri for terrain analysis, which includes state-of-the-art estimators for slope and curvature for triangulated surfaces (Triangulated Irregular Networks - TINs), and for the extraction of critical points from a TIN. For a description of the required libraries for building the library, the compilation process, the run-time options and of the supported input format, please refer to the github page of the repository listed above.

Terrain trees are a new in-core family of spatial indexes for the representation and analysis of Triangulated Irregular Networks (TINs). Terrain trees combine a minimal encoding of the connectivity of the underlying triangle mesh with a hierarchical spatial index, implicitly representing the other topological relations among vertices, edges and vertices. Topological relations are extracted locally within each leaf block of the hierarchal index at runtime, based on specific application needs. Based on Terrain trees, we have developed a set of tools for terrain analysis and named this toolset as Terrain Trees library (TTL). TTL contains a kernel for connectivity and spatial queries, and modules for extracting morphological features, including edge and triangle slopes, roughness, curvature. It also contains modules for extracting topological structures, like critical point, critical net, watershed segmentation, based on the discrete Morse gradient, and a technique for multivariate data visualization, which enables the analysis of multiple scalar fields defined on the same terrain. By working on TINs generated from big LiDAR (Light, Detection and Ranging) data sets, we demonstrate the effectiveness and scalability of the Terrain trees against state-of-the-art compact data structures.