Information Technology Reference
In-Depth Information
of the sleeve. The funnel algorithm consists of three components: the
path
,the
apex
, and the
funnel
(see Fig.
2
).
At the start of the funnel algorithm, the apex is set to the starting point
a
.
The funnel is initialized by two line segments from apex to the end points of
the first diagonal. We consider next diagonals of the sleeve to extend the funnel.
At some step a new apex can be established, the path connecting old apexes
to the new apex is a part of the shortest path between
a
and
b
. Once the last
diagonal is processed, we add the destination point
b
to obtain whole shortest
path. We choose the funnel algorithm because it is feasible to implement.
2.3 Multiple Shooting Method for Solving the 2D Shortest
Path Problems
We now describe briefly the direct multiple shooting method for solving shortest
path problems (see [
1
] for more details). Given a simple polygon
D
=
PQ
and
two vertices
a
and
b
of the polygon in which
, respectively) is the polyline
formed by vertices of the polygon from
a
to
b
(
b
to
a
, respectively) in counter-
clockwise order. Without loss of generality we assume that
a
x
<b
x
, where
v
x
denotes the
x
-coordinate of point
v
in 2D. Let us denote by
SP
(
a, b
)the
shortest path between
a
and
b
in
P
(
Q
D
.Given
u
and
v
in 2D and 0
≤
ʻ
≤
1, we
Fig. 1.
Multiple shooting for solving ODE-boundary value problem
Search WWH ::
Custom Search