Using the discrete 3D Voronoi diagram for the modelling of 3D continuous information in geosciences

Abstract

In this thesis the use of the discrete 3D Voronoi diagram in modelling continuous fields in geosciences will be assessed. The Voronoi diagram is a structure that divides a certain space into cells, called Voronoi cells. These cells are created so that every location within each cell is closest to the corresponding data point, or seed, of that cell. Every location in that cell is assigned the value of the corresponding seed. Throughout history, the Voronoi diagram has been widely used. In general, the Voronoi diagram is used in three spatial operations. • Using the Voronoi diagram to determine spatial distribution and neighbourhood relations between points in a dataset. • Using the Voronoi diagram to determine the area of influence of points in a dataset. • Using the Voronoi diagram as a basis for the natural neighbour interpolation method. In geosciences, data is sampled in many different ways. Sometimes by means of a regular grid for instance, but measuring continuous fields is often done in an anisotropically distributed pattern. Most often this is due to the way in which samples are collected. The Voronoi diagram can be a good means of visualizing and determining the distribution of data points, and therefore it can be a useful tool when working with anisotropically distributed data. The exact 3D Voronoi diagram is a data model in vector format that has been investigated for quite some years now, often in different areas of sciences. The properties, the advantages and the disadvantages of this data model have been documented. The discrete 3D Voronoi diagram is a data structure in raster format, and, although it has been investigated, it has not been properly documented with respect to its properties, advantages and disadvantages. In this thesis these properties are described, especially in light of the modelling of continuous field data in the realm of geosciences, to perform for instance the natural neighbour interpolation, visualize the data distribution and other spatial operations. To do so, first a new algorithm has been devised, based on literature reviews of different articles on the 3D discrete Voronoi diagram. The new algorithm presented in this thesis has been implemented through the Python programming language. In order to use the discrete 3D Voronoi diagram in combination with geo-scientific, continuous data, a GIS that handles 3D raster data was identified, namely GRASS, and the possibilities and functionalities of GRASS with respect to the discrete 3D Voronoi diagram were investigated. Some functionality, such as resampling and natural neighbour interpolation, that was not found in the GIS but that is considered necessary, has also been implemented. By using test data, the entire process has been tested, from creating a discrete 3D Voronoi diagram, through interpolation it, to visualizing and analyzing it. The outcome shows that the discrete 3D Voronoi diagram is a proper tool for handling and analyzing 3D continuous field data. It enables user to go from a dataset of 3D points to a 3D continuous field, in the environment of a GIS, which allows for even further spatial analyses and operations. One of the advantages of the implemented algorithm is the effectiveness in adding, moving and removing points. This makes it very suitable for dynamic modelling, as well as natural neighbour interpolation. The algorithm also shows other interesting future possibilities, such as creating 3D generalized Voronoi diagrams. Some of these advantages and future uses are currently difficult or not yet possible to implement in an exact environment. Besides the possibilities of the presented algorithm, practical implementation of the algorithm is not yet feasible, due to calculation-time related issues. However, it is expected that if a compiled programming language such as C++ is used, as opposed to the interpreted language Python, the efficiency of the algorithm will increase.