Geoscience Reference
In-Depth Information
(a)
(b)
(c)
Fig. 1 a Six map objects and their boundaries. b The same map stored as a graph and its dual
(dotted lines). c The dual graph is used to describe the relationships between adjacent polygons.
(Figure after Gold (
1991
))
However, in his paper Gold (
1998
), in the context of automating the maps
production for the forest industry, Gold acknowledges that there are far too many
points in a discretization of forest polygons (in the sense that not so many points
are required to retain the shape and topology of these forest polygons), and that the
only arcs that should be retained are those that are critical to respect the polygonal
structure. This approach can be generalized to 3D, or more generally to nD.
In this chapter, we propose a very general data structure for storing any real or
abstract cell complex in a minimal way in the sense of memory space utilization.
The originality and quality of this novel data structure is to be the most compact
data structure for storing the geometric topology of any geometric object, or more
generally, the topology of any topological space. We achieved this purpose by
providing a data structure that generalizes the Quad-Arc data structure to 3D and
realizes the synthesis between that 3D Quad-Arc data structure and the Dual Half-
Edge (DHE) data structure, in order to get a more efficient data structure that stores
the geometry of 3D objects (and particularly their ramification) and their topo-
logical relationships in a pair of dual subdivisions with much fewer elements than
the original DHE. One might think that this is only of theoretical interest, but in
fact, it is very important practically for any 3D GIS, because the efficiency of 3D
GIS systems is currently very limited by the amount of necessary input/output
operations, which take much longer than any operation in the Central Processing
Unit or in between the Random Access Memory and the Central Processing Unit.
Therefore, this most compact geometric topology storing data structure is central to
the development of efficient 3D GIS systems that can process quickly large spatial
data sets (for example a 3D city model or any local or regional development model).
We first review the key data structures related to our research including the
Dual Half-Edge in
Sect. 2
and the concepts of geometric topology (ramification) in
Sect. 3
.In
Sect. 4
, we generalize the 2D Quad-Arc data structure to 3D. We
present our new synthesis of these two data structures (the Dual Half-Arc data
structure) in
Sect. 5
. Finally, in
Sect. 6
, we analyze potential applications of this
data structure.
