Graphics Reference
In-Depth Information
an 8-component
C
of
S
, a 4-component
D
of
S
c
4-adjacency
adjacent points c Œ
C
, d Œ
D
Input :
Output:
all points of
D-
border of
C
Follow the steps below:
(1) If
C
is an isolated point, then the
D
-border is just c. Change c to 4 and stop.
Otherwise, change c to 3 and d to 2.
(2) List the 8-neighbors of c in clockwise order starting with d and ending with first
occurrence of 1, 3, or 4:
e
1
, e
2
, ... , e
k
(3) If c is 3, e
k
is 4, and e
h
is 2 for some h < k, then set c to 4, e
h
to 0, and stop;
otherwise, set c to 4 (only if it was 1 and not 3), take e
k
as the new c, take e
k-1
as the new d, and go back to (2).
When the algorithm stops, the 4's will be the
D-
border of
C.
Algorithm 2.3.1.
A border-following algorithm.
2.3.1 Example.
We show the various stages of Algorithm 2.3.1 for a set
S
. The
values of points in the pictures below are shown in boldface and
S
starts off as the
points marked with 1's. The current c and d are shown in parentheses to the left of
the point to which they refer. The numbering of the 8-neighbors of c is shown in paren-
theses to the right of the point. We also show the value of k that we get in step (2) of
the algorithm.
(d)
0
(1)
0
(2)
0
2
(d)
0
(1)
0
(2)
2 0 0 0
2 0 0
(c)
1
1
(3)
0
Æ
3
(c)
1
0
(3)
Æ
3 4
(8) (d)
0
(1)
0
(2)
Æ
3
(c)
4 0
Æ
1
0 1
1 0
1
(4)
1 0
(7) (c)
1 0
(3)
1
(2) (d)
0
(1)
4
0 0
(6)
0
(5)
0
(4)
0 0 0
k = 3
k = 4
k = 8
k = 2
0
2
0 0
0
(2)
2
(3)
0
(4)
0
0 0 0
0
(6)
3
(7)
4
0
Æ (d)
0
(1) (c)
3 4
(5)
0
Æ
4 4 0
0
(5) (c)
1
(d)
0
(1)
4
0
4 0 4
4 0 4
0
(4)
0
(3)
0
(2)
0
k = 7
k = 5, h = 3
