three geometric types: nodes, edges and faces
represented by the symbols n, e and f
- three geometric object types: point objects, line
objects, area objects.
The further developments will only use line- and area
objects which will be represented by the symbol O, and
O, . Instances of these entity types will be indicated by
suffixes.
The reader will recognise that the formalization explained
in this paper is to a large extent isomorphic with topologic
data structures defined for GIS such as ATKIS/DLM, DGF,
TIGER and DIME etc., see (Hesse 1992, Walter 1994,
Marx 1990, USBUREAU 1990). This formalization will be
based on the FDS described in (Molenaar 1989).
Relationships Between Nodes, Edges and Faces
The following relationships can be defined between the
geometric elements of a planar graph:
> Edge e, has node n, as the begin node
^ Beginle, n] — 1 otherwise = 0
- Edge e; has node n, as the end node
- Endle, n] = 1 otherwise = 0
We will consider edges as straight line segments. Each
edge will always have one face at its left hand side and
on at its right hand side. These relationships will be
expressed by the following functions:
- Edge e, has face f, at its left-hand side
—1iele,f.lo-7
For any f, z f, we get then Le/e,, f,] = O
- Edge e; has face f, at its right-hand side
- Rile,, f,] - 1
and again for f, z& f, we get then Rile,, f,] = O
If an edge e, has face f, at the right hand side and face
f, at the other side then these faces are adjacent at this
edge, which will be expressed by the function
ADJACENTIY,, f,le;] = 1 (and = O otherwise)
the fact that there is some edge where the faces are
adjacent can then be expressed by
ADJACENTIf,, f,] = 1 (and = O otherwise)
Line Objects
The geometry of a simple line object is represented by a
chain of edges as in figure 1a. The fact that an edge e,
is part of the object can be established by the function
Part,, [e,, O,]. The notation Part, [ ] means that an entity
with spatial dimension u is a part of an entity with
dimension v. If the edge is part of the object then
Part,,[ | = 1, else it has a value = O.
À line object will have a begin node
n, = BEG(O,) and an end node
n, = END(O,). These can be found through the edges of
O,, the direction of the object can then be specified by
DINO Mn}
International Archives of Photogrammetry and Remote Sensing. Vol. XXXI, Part B3. Vienna 1996
a. relationship between edge and line object
chain represents
line object edge part of
pum k Î fine object
edi f oe
k Î eage. part o
sel
b. relationship between edge, face and area object
area object a
FACE right
area object b
fig. 1: Relationships between edges and objects.
Area Objects
The geometry of an simple area object is represented by
one or more adjacent faces as in figure 1b. If a face f, is
part of an area object O, this will be represented by
Part, [f,, O,] — 1. The set of all objects from which a
face fis a part is OA(f) = { O | Part,,[ £ O] = 1}
This function relates two two-dimensional entities. If there
are overlapping area objects then each face might be part
of several objects, but each object will also consist of one
or more faces. Therefore this is a many-to-many relation-
ship. Overlapping objects can be found through their com-
mon faces.
Now it is possible to check whether edge e, is related
through face f, to an area object O,. There is at most one
face for which both Ze/e;, f,] = 7 and Part,,[f,, O,] =1.
If such a face exists then the function relating the edge
to the object will get the value — 1, in all other cases it
will be — O. Hence if edge e, has area object O, at its left-
hand side then Le/e, O,] = 7 else = 0. Similarly if edge
e, has area object O, at its right-hand side then A//e;, O,
] 21 else « O.
The combination of these two functions gives for edge
e; :
Ble,, O,] = Lele;, O,] + Rife,, O,]
If an edge e, is part of the boundary of O, then only one
of the functions Ri and Le is equal to 1 but not both, so
for such an edge we find Ble;, O,] = 1. If e; has O, both
at its left-hand side and at its right-hand side then
Ble;, O,] = 2, in that case it is running through O,. If
Ble;, O,] = O0 there is no direct relationship between e,
and O,.
Adjacent Area Objects
When an edge has an object O, at its left hand side and
not at its right hand side and object O, at its right hand
side and not at its left hand side then these objects are
adjacent at this edge. If the objects overlap not at all, i.e.
if they have no common faces and they are adjacent at
least one edge, then they are adjacent which is expressed
by the function ADJACENT[O,, O,] = 1 (and = O
otherw
Line- a
Severa
and an
edge tt
area ol
Lel0,;
Ri[O,, |
For the
object
B[O, ,.«
If this f
througl
it is ai
relatior
might |
A Hydr
For m
elemen
Casasr
drainac
drainac
Catc
Stai
Froi
Inle
fig.
ment a
Each el
(if the
elemen
sented
The rel
the ser
one we
subcat
dissect
2, but
topoloc
expres:
for wa