Geoscience Reference
In-Depth Information
Fig. 12
A cup modeled with the simplified dual half-arc data structure
6 Discussion
In this chapter, we have generalized the Quad-Arc data structure from 2D to 3D
and we have designed a novel 3D topological data structure called the Dual Half-
Arc, that provides a synthesis between the newly generalized 3D Quad-Arc data
structure and the Dual Half-Edge data structure. This is done by applying the idea
of generalization of the newly generalized 3D Quad-Arc data structure using
volume tags to the Dual Half-Edge data structure. The ultimate goal is to represent
both the geometric (primal) subdivision of space induced by the geometric objects
and the topological relationships among the geometric cells of the primal subdi-
vision (dual subdivision) as a minimal (in the sense of set inclusion and number of
cells of each dimension) geometrical/topological data structure. In our future work,
we will prove the minimality of this data structure among the set of all boundary
representations. The Dual Half-Arc data structure could have significant impact in
GIS and spatial databases because it will induce more compact representations of
the geometry and topology of geometric objects. This is crucial in applications,
since most of the running time of any algorithm is lost in input/output operations
(even with solid state disks). It is worth exploring potential future applications.
Potential applications include emergency management (fires, earthquakes, tsuna-
mis) with dynamic evacuation routes with changing building topology, mobile
telecommunication networks modeling with addition of base stations, robotic
injured evacuation, etc.
