Information Technology Reference
In-Depth Information
c
c
c
a
b
d
a
b
d
a
b
d
q
q
p
p
z
z
z
y
y
r
r
y
s
s
w
w
w
x
x
x
Fig. 14.
Fig. 15.
Fig. 16.
the second of these holds. Then, if we break edge
xy
at point
r
and translate
the second arc, including the point
r
, along the first bridge edge, the point
r
must encounter the circle associated with the third arc before
p
reaches
b
.Ifwe
stop the translation at this point (see Fig.
16
) we see that the second bridge has
been replaced by two edges (
xr
and
ry
) which become part of the second and
third discrete arc respectively; i.e. vertex
r
is a degenerate bridge, taking us to
Case II. (As before, we note that the translation produces a path that violates
the discrete bounded curvature property initially, but it is restored just when
s
coincides with
r
.)
Case II: one bridge is degenerate and the other is not.
We assume, without loss
of generality, that the first bridge is degenerate. There are two sub-cases again
that depend on the span of the second arc. In the first sub-case (see Fig.
17
)the
total turn from the first edge (
bc
) after the degenerate bridge (
b
) to the second
bridge edge (
xy
)islessthanorequalto
ˀ
. If we translate the middle discrete arc,
excluding the first bridge point, (i.e. the vertices
c
through
x
) along the second
bridge edge (taking
x
towards
y
) (see Fig.
18
), we maintain the discrete bounded
curvature property until the first of two events occurs: (i)
x
(respectively,
y
) joins
the third (respectively, second) circle, or (ii) the successor (
c
) of the degenerate
bridge (
b
) joins the first circle. The first event coincides with the degeneration of
the second bridge, while the second event leaves us with a new degenerate first
bridge (vertex
c
), and hence a new instance of Case II with a smaller second arc.
In the second sub-case (see Figs.
19
and
21
), where the total turn from the
first edge (
bc
) after the degenerate bridge (
b
) to the second bridge edge (
xy
)is
greater than
ˀ
, we again slide the middle discrete arc, this time including the
first bridge point, (i.e. the vertices
b
through
x
) along the second bridge edge
(taking
x
towards
y
). The discrete bounded curvature property is maintained at
x
and
y
unless
x
(respectively,
y
) joins the third (respectively, second) circle (i.e.
the second bridge becomes degenerate). Meanwhile, if
b
moves outside of the first
circle (see Fig.
20
), then the discrete bounded curvature property is maintained
at
a
and
b
until
a
joins the second circle, at which point
a
replaces
b
as a
degenerate bridge, so we can continue in Case II. Alternatively, if
b
moves inside
the first circle, we maintain feasibility of the transformed path by (continuously)
Search WWH ::
Custom Search