Geoscience Reference
In-Depth Information
The Dual Half-Arc Data Structure:
Towards the Universal B-rep Data
Structure
François Anton, Pawel Boguslawski and Darka Mioc
Abstract In GIS, the use of efficient spatial data structures is becoming
increasingly important, especially when dealing with multidimensional data. The
existing solutions are not always efficient when dealing with big datasets, and
therefore, research on new data structures is needed. 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. For this purpose, we generalize an existing data structure
from 2D to 3D and design a new 3D data structure that realizes the synthesis
between an existing 3D data structure (the Dual Half-Edge (See Footonote 1) data
structure) and the generalized 3D Quad-Arc data structure, (See Footonote 2) and
at the same time, improves the Dual Half-Edge towards a simpler and more
effective representation of cell complexes through B-rep structures. We generalize
the idea of the Quad-Arc data structure from 2D to 3D, but instead of transforming
a simple edge of the Quad-Edge data structure to an arc with multiple points along
it, we group together primal edges of the Dual Half-Edge that have the same dual
Half-Edge vertex tags (volume tags) into one Dual Half-Arc whose dual is the
common Dual Half-Edge and primal faces corresponding to dual. This corresponds
to grouping together straight line segment edges into arcs. This allows us to trans-
form the Dual Half-Edge data structure into a 3D data structure for cell complexes