|
Key words: Voronoi Diagrams, Geographical Databases, Cartometry, Automated Spatial Analysis, Computational Geometry
Two-dimensional cartographic wholes are stored in the computer as one-dimensional lists of so-called geographical objects. Although the disposition of objects is as desirable as individual presence for cartographic representation (generalization) and geographical analysis, configurations are only implicitly stored by means of co-ordinates. While the full reconstitution can be said to be left to the eye and appreciation of the human operator upon display, any automated handling of geographical data involves automated reconstruction of some kind.
Reconstruction is often performed with purpose-oriented tools, the more obvious and the more famous of which may well be Delaunay triangulation, which is clearly dedicated to the elicitation of proximity relationships. Either as such, or in the dual form of the Voronoi diagram on points, we consider Delaunay triangulation to be a purpose-oriented tool inasmuch as before triangulation can be computed, specific points from the data that are representative enough for the chosen application must be selected.
A similar yet bias-free structure exists: Voronoi diagrams on segments, brought into geomatics by Christopher Gold. These diagrams also cast separate cartography-worthy objects into a planimetric whole by allocating portions of the plane with closest points to every atomic part from the features (every segment, every junction). But because they involve all the available geometry of the features, they account for them completely, and can thus be said to be data-induced structures. Such diagrams can be pre-computed, and it is the aim of this paper to describe in what form they can be stored to efficiently meet quite a remarkable range of basic spatial queries.
The paper does not deal with how to compute Voronoi diagrams on segments (refer to literature from the field of computational geometry), but with how, once computed, they can be stored in relation to the available spatial data. One "intrinsic" diagram per object, and combination methods for "combined diagrams" when several objects are retrieved together, are advocated. Edges of a Voronoi diagram are geographically classified as "skeleton edges" (within the contour of an object), "growth edges" (left or right from an object, separating components from its own trace), or "fence edges" (separating components from two different objects). Edges are also geometrically classified (segments of lines equidistant between point and point, of lines equidistant between segment and segment, of parabolas equidistant between point and segment). Useful attributes for edges are described (end points, minimal-maximal distances to objects, etc.) as well as basic calculation methods (length of an edge, where to find on it a point at a given distance from the object etc.).
In addition, a variety of basic but recurring and often fastidious spatial queries are simplified, not only by using Voronoi diagrams, but by using them with the advocated structuration. Convex hull, Minimum Spanning Tree, dilation, erosion, opening, closure, skeleton, and Hausdorff distance between lines, described in an earlier paper in 1997, are noted, whereas the Hausdorff distance between areas, the Bouligand-Minkowski fractal dimension, and water-lining (as re-introduced recently by Albert Christensen from a different perspective) are described in more detail.
It is well known that topology (possibly explicitly stored, at least in the awareness we have of it) makes programming spatial queries both more intuitive and more efficacious. The same holds for Voronoi diagrams, and beyond the practical descriptions provided in this paper (which after all may or may not be programmed as such) lie the epistemological argument that the knowledge at least of the properties of Voronoi diagrams on segments provides one (not omnipotent but in the cartometric domain, reliable) context or paradigm for programming spatial queries.