Fields as found in the geosciences have properties that are not usually found in other disciplines: the phenomena studied are often three‐dimensional (3D), they tend to change continuously over time, and the collection of samples to study the phenomena is problematic, which often results in highly anisotropic distributions of samples. In the geographical information system (GIS) community, raster structures (voxels or octrees) are the most popular solutions, but, as we show in this paper, they have shortcomings for modelling and analysing 3D geoscientific fields. As an alternative to using rasters, we propose a new spatial model based on the Voronoi diagram (VD) and its dual the Delaunay tetrahedralisation (DT), and argue that they have many advantages over other tessellations. We discuss the main properties of the 3D VD/DT, present some GIS operations that are greatly simplified when the VD/DT is used, and, to analyse two or more fields, we also present a variant of the map algebra framework where all the operations are performed directly on VDs. The usefulness of this Voronoi‐based spatial model is demonstrated with a series of potential applications.

This paper proposes a new Free-Lagrange method based on the kinetic Voronoi diagram for fluid simulation. The objective here is to combine the advantages of an adoptive mesh structure with the advantages of kinetic mesh maintenance, and demonstrate their value for dynamic simulation. Despite the theoretical advantages of the Free-Lagrange method, its use has been handicapped with the reconstruction of topology after each time step that considerably reduces the efficiency of the method. In addition, the use of fixed time steps causes problems such as overshoots and undetected collisions. In order to demonstrate the ability of the proposed model to solve these problems, the method is applied to a dam-breaking problem and global tides. With the results obtained from these numerical experiments, the validity of the global kinetic data structure is approved. In particular, the method is found to be more efficient than existing methods. In addition, qualitative comparison of physical results with analytical solutions demonstrates the similarity of the results and confirms the physical validity of the proposed method. Further investigations with real-world data and the complete equation of motion are suggested to compare it with other numerical methods.

Models of spatial relations are a key component of geographical information science (GIS). Efforts have been made to formally define spatial relations. The foundation model for such a formal presentation is the 4-intersection model proposed by Egenhofer and Franzosa (1991). In this model, the topological relations between two simple spatial entities A and B are transformed into pointset topology problems in terms of the intersections of A's interior and boundary with B's interior and boundary. Later, Egenhofer and Herring (1991) extended this model to 9-intersection by addition of another element, i.e. the exterior of an entity, which is then defined as its complement. However, the use of its complement as the exterior of an entity causes the linear dependency between its interior, boundary and exterior. Thus such an extension from 4- to 9-intersection should be of no help in terms of the number of relations. This can be confirmed by the discovery of Egenhofer et al. (1993). The distinction of additional relations in the case where the co-dimension is not zero is purely due to the adoption of definitions of the interior, boundary and exterior of entities in a lower dimensional to a higher dimension of space, e.g. lines in 1-dimensional space to 2-dimensional space. With such adoption, the topological convention that the boundary of a spatial entity separates its interior from its exterior is violated. It is such a change of conventional topological properties that causes the linear dependency between these three elements of a spatial entity (i.e. the interior, boundary and exterior) to disappear, thus making the distinction of additional relations possible in such a case (i.e. the co-dimension is not zero). It has been discussed that the use of Voronoi-regions of an entity to replace its complement as its exterior in the 9-intersection model would solve the problem (i.e. violation of topological convention) or would make this model become more comprehensive. Therefore, a Voronoi-based 9-intersection model is proposed. In addition to the improvement in the theoretical aspect, the Voronoi-based 9-intersection model (V9I) can also distinguish additional relations which are beyond topological relations, such as high-resolution disjoint relations and relations of complex spatial entities. However, high-resolution disjoint relations defined by this model are not purely topological. In fact, it is a mixture of topology and metric.

We wish to extract the topology from scanned maps.In previous work [ 151 this was done by extracting a skeleton from the Voronoi diagram, but this required vertex labelling and was only useable for polygon maps.We wished to take the crust algorithm of Amenta, Bern and Eppstein [3] and modify it to extract the skeleton from unlabelled vertices.We find that by reducing the algorithm to a local test on the simple Voronoi diagram of point sites we may extract both the crust and the skeleton simultaneously.We show that this produces the same results as the original algorithm, and illustrate its utility with various cartographic applications.

. This paper examines the problem of polygon digitizing, and suggests an inversion of the traditional approach for polygons of the environmental type, where each individual polygon, rather than its boundaries, is of primary interest. Many workers in geology, forestry, soil science, etc. have found the tedious specification of boundary arcs and their topological linkage and editing to be a major block to productivity. An alternative digitizing approach is described using Thiessen/Voronoi polygons to generate topology automatically and to reduce map digitizing times significantly. The digitizing of representative points within each polygon is performed using the GIS. The stand-alone Voronoi polygon building and boundary extraction module then generates linked arcs that are returned to the GIS for further analysis. Examples of the productivity enhancement in a production environment are given, along with the algorithms used.

Many data structures are possible for the storage of topological information for computer-based maps. The PAN graph is here suggested as an aid in the selection of a strategy appropriate to the application. Examples are given for the mapping of triangular networks and Thiessen polygons. Application of the technique is appropriate to both education in, and design of, spatial data structures for automated cartography and geographical information systems

A technique is discussed for obtaining a contour tree efficiently as a byproduct of an operational contouring system. This tree may then be used to obtain contour symbolism or interval statistics as well as for further geomorphological study. Alternatively, the tree may be obtained without the computational expense of detailed contour interpolation. The contouring system proceeds by assuming a Voronoi neighbourhood or domain about each data point and generating a dual-graph Delaunay triangulation accordingly. Since a triangulation may be traversed in a tree order, individual triangles may be processed in a guaranteed top-to-bottom sequence on the map. At the active edge of the map under construction a linked list is maintained of the contour ‘stubs’ available to be updated by the next triangle processed. Any new contour segment may extend an existing stub, open two new stubs or close (connect) two previous stubs. Extending this list of edge links backwards into the existing map permits storage of contour segments within main memory until a dump (either to plotter or disc) is required by memory overflow, contour closure, contour labelling or job completion. Maintenance of an appropriate status link permits the immediate distinction of local closure (where the newly-connected segments are themselves not connected) from global closure (where a contour loop is completed and no longer required in memory). The resulting contour map may be represented as a tree, the root node being the bounding contour of the map. The nature of the triangle-ordering procedure ensures that inner contours are closed before enclosing ones, and hence a preliminary contour tree may be generated as conventional contour generation occurs. A final scan through the resulting tree eliminates any inconsistencies.