Geoscience Reference
In-Depth Information
except themselves). The concept of ramification index e
p
corresponds to the number
of sheets that meet at a point p. Only finitely many points are ramification points.
All other points (where there is only one sheet) have ramification index 1.
4 Generalizing the Quad-Arc Data Structure
from 2D to 3D
The Quad-Arc data structure is a 2D data structure that modifies the Quad-Edge data
structure Guibas and Stolfi (
1985
) in the following way. First, all points that belong
to the same polygon are tagged with the polygon ID. Then, all the primal Quad-
Edges that have the same polygon tag at the end-vertices of their dual Quad-Edge
(polygon IDs) are grouped together into a single Quad-Arc, which is represented by
a single arc composed of several straight line segments through intermediate ver-
tices. The corresponding dual Quad-Arc is a straight Quad-Edge. This construction
process can be easily generated to 3D or more generally to nD. The main difference
between 2D and 3D is that in 3D, instead of considering polygon tags, we are
considering volume tags. It is not only primal Quad-Edges that need to be grouped
together if the end-vertices of their dual Quad-Edges have the same volume tag, but
also these dual Quad-Edges (and possibly also the faces) of the dual subdivision.
5 The Dual Half-Arc Data Structure
The Dual Half-Arc data structure generalizes the Dual Half-Edge data structure by
grouping together primal Half-Edges whose dual Half-Edges have the same vol-
ume tag at their end-vertices and these dual Half-Edges. The relational model
corresponding to the Dual Half-Edge data structure is shown in Fig.
8
, while the
relational model corresponding to the Dual Half-Arc data structure is shown in
Fig.
9
.
This grouping of dual Half-Edges is done in the same way as the 3D Quad-arc
data structure groups together the primal Quad-Edges whose dual Quad-Edges
have the same volume tags at their end-vertices. One illustration of this grouping
on the Dual Half-Edge data structure is provided in Figs.
10
and
11
. Such an object
is simple enough to show very easily the differences between the Dual Half-Edge,
the Dual Half-Arc and the simplified Dual Half-Arc data structures. We could have
shown a house, but the differences between these data structures would have been
more difficult to visualize. Indeed, all the edges that correspond to ramifications
(e.g. three or more walls that meet together) would remain in the Dual Half-Arc
and in the simplified Dual Half-Arc data structure.
As explained in
Sect. 3
, a fundamental concept of geometric topology is the
concept of ramification, i.e., the fact that several sheets (considered as disjoint
path-connected open sets) meet at a point (or at a curve). In fact, we can model any
