Graphics Reference
In-Depth Information
Definition.
Let
p
Œ
Z
n
and let d be a fixed integer satisfying 0 £ d £ n - 1. Suppose
that k is the number of points of
Z
n
that are the centers of cubes that meet the cube
with center
p
in a face of dimension larger than or equal to d. Each of those points
will be called a
k-neighbor
of
p
in
Z
n
.
Note:
The general definition for k-neighbor is not very satisfying because it is rela-
tively complicated. It would have made more sense to call the point a “d-neighbor.”
Unfortunately, the terminology as stated is too well established for the two- and three-
dimensional case to be able to change it now.
Two points in
Z
n
are said to be
k-adjacent
if they are k-neighbors.
Definition.
k-adjacency is the key topological concept in the discrete world. All the terms
defined below have an implicit “k-” prefix. However, to simplify the notation this prefix
will be dropped. For example, we shall simply refer to “adjacent” points rather than
“k-adjacent” points. It must be emphasized though that everything depends on the
notion of adjacency that is chosen, that is, for example, whether the intended k is 4
or 8, in the case of
Z
2
, or 6, 18, or 26, in the case of
Z
3
. To make this dependency
explicit, one only needs to restore the missing “k-” prefix.
There is a nice alternate characterization of k-adjacency in two special cases that
could have been used as the definition in those cases.
Alternate Definition.
Let
p
= (p
1
,p
2
,...,p
n
),
q
= (q
1
,q
2
,...,q
n
) Œ
Z
n
. The points
p
and
q
are
2n-adjacent
in
Z
n
if and only if
n
Â
qp
-=
1
i
i
i
=
1
They are
(3
n
1)-adjacent
in
Z
n
if and only if
p
π
q
and |q
i
- p
i
|£1 for 1 £ i £ n.
-
Properties of 2n- and (3
n
- 1)-adjacency are studied extensively in [Herm98].
Definition.
A (
discrete
or
digital
)
curve
from point
p
to point
q
in
Z
n
is a sequence
r
s
, 1 £ s £ k, of points such that
p
=
r
1
,
q
=
r
k
, and
r
s
is adjacent to
r
s+1
, 1 £ s £ k - 1.
Furthermore, with this notation, we define the
length
of the curve to be k - 1.
For example, the points
p
1
,
p
2
,
p
3
, and
p
4
in Figure 2.3 form a discrete curve of
length 3 with respect to 8-adjacency but not with respect to 4-adjacency because
p
1
and
p
2
are not 4-adjacent.
Definition.
A set
S
is
connected
if for any two points
p
and
q
in
S
there is a curve
from
p
to
q
that lies entirely in
S
. A maximal connected subset of
S
is called a
component
.
Figure 2.3.
An 8-connected discrete curve.