Graphics Reference
In-Depth Information
All three of these distance functions define a metric on
Z
n
, called the
Euclidean
,
taxicab
, and
max metric
, respectively. (They actually also define a metric on
R
n
.) For
example, consider the points
p
= (2,1) and
q
= (5,3). Then the distances between these
two points are:
Euclidean distance:
Taxicab distance:
13
5
Max distance:
3
The points that are a distance of 1 from a given point are its 4-neighbors when we
use the taxicab distance and the 8-neighbors when we use the max distance.
Finally, the rest of this chapter deals with two-dimensional sets and, unless stated
otherwise, all our sets will be (discrete) subsets of some given picture
P
in
Z
2
. We shall
use the terminology above.
2.3
Border-Following Algorithms
Algorithms that can compute the borders of regions in a picture are important in a
variety of places, in particular in animation. We describe one such algorithm here to
give the reader a flavor of what they are like. See [RosK76] for more details. Other
contour-following algorithms are described in [Pavl82]. See also [Herm98].
Assume that each point of a picture has a value associated to it and that in our
case this is either 0 or 1, with the region of interest in it being the points with value
1. We shall show pictures by showing the values at their points and, to simplify the
discussion, we often identify the point with its value. (“Setting a point to 3” will mean
setting its value to 3.)
Definition.
If
C
is a component of
S
,
D
a component of
S
c
, then the
D
-border of
C
is the set of points of
C
that are adjacent to a point of
D
.
For example, consider the connected set
S
of 1's below:
1 1 1 1
1 0 1 1 0
1 1 1 1
Let
D
1
and
D
2
be the components of
S
c
that contain the left and right “0,” respectively.
Then
1 1 1
1 1 1 1
1 1
and
1 1
1 1 1
1 1 1 1
are the
D
1
-border and
D
2
-border of
S
, respectively.
Algorithm 2.3.1 is one
border-following
algorithm.
