Geoscience Reference
In-Depth Information
with fewer Dual Half-Edges. Since the input/output operations are the most costly on
any computer (even with solid state disks), this will result in a much more efficient
data structure, where computation of topological relationships is much easier and
efficient, like cell complex homologies (See Footonote 3) are easier to compute than
their simplicial counterparts. This new data structure, thanks to its efficiency, could
have a positive impact on applications that need near real time response, like
mapping for natural disasters, emergency planning, evacuation, etc.
1 Introduction
In GIS, multi-dimensional representations are still not completely functional.
1
In
spite of the new developments in spatial databases, where systems like Oracle and
Post GIS allow for storage,
2
maintenance and query of 3D Information, GIS
systems are still not capable of spatial analysis on 3D objects Ellul and Haklay
(
2009
). For this purpose,
3
the main issue seems to be the representation of the
topological relationships for 3D objects within commercial GIS systems.
There are several ways to represent topological relationships among spatial
objects (i.e., all binary relationships among spatial objects that are invariant by
continuous transformations, i.e., incidence, containment, adjacency) in a com-
puter. One of them is concerned with boundaries of objects, and is known as the
family of boundary representations (B-rep, see Stroud
2006
; Ellul and Haklay
2009
and
Sect. 2
). Another one is concerned with the tessellation of the space into
cells of different dimensions (cell complexes, see Webster (
2003
) for a gentle
introduction on cell complexes and
Sect. 2
).
In two dimensions, a primal subdivision can store the geometry of spatial
objects, while its dual subdivision stores the spatial relationships between adjacent
objects: as shown in Fig.
1
, Gold (
1991
) uses two connected data structures to
store simultaneously a polygonal map (where each polygon has certain attributes)
and its dual (the boundaries between two map objects having certain attributes, e.g.
the boundary type or the flow direction). The data structure used was the quad-
edge structure of Guibas and Stolfi (
1985
). He argues that the boundaries do not
characterise per se any of the objects, but rather the adjacency relationships that
exist between them.
1
An half-edge is an edge with an oriented edge in the primal or dual subdivision.
2
The Quad-Arc data structure groups quad-edges (which are composed of one pair of oriented
edges of the primal subdivision and the corresponding pair of dual edges), whose dual edge
extremities have the same pair of polygon tags.
3
All boundaries are cycles, but not all cycles are boundaries; homologies are equivalence classes
of cycles modulo boundaries, i.e., cycles that are not boudaries, i.e., topological spaces formed by
cycles, where all boundaries have been removed.
