Graphics Reference
In-Depth Information
Definition.
A d-dimensional cell is said to be adjacent to an e-dimensional cell if
(1) d π e and one is contained in the other,
(2) d = e > 0, and they have a (d-1)-dimensional cell in common, or
(3) d = e = 0, and they are the two ends of some 1-dimensional cell (edge).
In our discussion here we shall restrict ourselves to two-dimensional complexes.
Algorithms dealing with such complexes typically need adjacency information such
as the set of edges of a face or the set of faces that contain a given vertex. We shall
use the following notation:
notation
what it means
x Æ y
x is adjacent to y
x Æ Y
the set of objects of type Y adjacent to x, that is,
{y | y is an object of type Y and x Æ y}
X Æ Y
the sets {x Æ Y | x is an object of type X}
In the context of this notation, capital letters such as X and Y will be one of the types
V (vertex), E (edge), or F (face). |X| will denote the number of objects of type X. We
shall refer to X Æ Y as an adjacency relation .
The nine possible types of adjacency information between vertices, edges, and
faces are shown in Figure 5.36. If a data structure contains one of these adjacency
relations explicitly, then we shall say that one has direct access to that information.
For example, the notation E Æ V means that each edge has direct access to both of
its vertices and V Æ V means that each vertex has direct access to all of the vertices
adjacent to it. Call a relation X Æ X a self-relation .
Two questions which need to be addressed when choosing a data structure are:
(1) Does the data structure adequately describe the topology of the spaces that
are represented? If so, then we shall say that it is topologically adequate .
(2) What is the complexity of determining the truth of x Æ y or computing some
x Æ Y given the adjacency relations defined explicitly by the data structure.
[Weil85] has an extensive discussion of question (1). The topologically adequate adja-
cency relationships are identified and proved to be that. We shall not repeat those
Figure 5.36.
Possible face-edge-vertex adjacency
data.
Search WWH ::




Custom Search