In this section we solve a problem of finding a shortest path between
a point and a curve on a free-form non-periodic parametric surface
[247], which utilizes the method we have developed in
Sects. 10.3 and
10.4. This concept is important in robot motion planning and
constructing a medial axis on a free-form surface. Suppose we have a
point
and a curve
on a parametric surface
defined as
, we want to
compute the shortest path between point
and curve
as shown in
Fig.
10.4. The existence of such a shortest path follows from results
shown in [448]. Let us denote the intersection point of the
curve
and the shortest path by
. Wolter [449]
developed a necessary condition to have a shortest path from point
to curve
, provided that the point
is not an end point of the
curve
. The condition is given by the orthogonality of the tangent
vector of the geodesic curve, connecting
and
, at
and the
tangent vector of
at
. If point
were known, the problem
could be reduced to an IVP, since at point
,
,
,
and
are all known. However, point
can be found only by solving the
problem. We guess a parameter value
for point
and solve
the BVP. In general the unit tangent vector of the curve
and the unit tangent vector of the arc length parametrized
geodesic curve
at the guessing point will not be
orthogonal to each other. Consequently, we need to adjust the
parameter value
and iterate until those two unit tangent vectors
become orthogonal. Therefore for each iteration, we need to solve a
two point boundary value problem, which also requires iterations
(i.e., nested iteration). If we denote these two unit tangent vectors
as
and
, then they can be expressed as follows:
(10.66)
(10.67)
Figure 10.4:
Shortest path between point
and curve
(adapted from [247])
Therefore the orthogonality condition can be written as
(10.68)
Consequently we need to find a parameter value
such that
. Since the relationship described above is implicit,
we use the secant method [69] instead of Newton's
method to obtain
. The secant method can be derived from Newton's
method by replacing the derivative
by the
quotient
where superscripts
denote
-
iteration. This leads to the following
scheme
(10.69)
Notice that the secant method requires two initial approximations
and
.
Since the secant method has an order of convergence of
[69], it converges
within a reasonable number of iterations. If the correction
is large, it is again an indication that the problem is highly
nonlinear. In such case we also employ a step correction procedure
(10.70)
where
is a correction factor
, determined as for
the modified Newton's method. Since we do not know how many solutions
exist and the corresponding parameter values of the curve
beforehand, we can use a similar algorithm to the circular arc
approximation. If the range of the parameter value of the
curve is
, we start from both ends of the curve (i.e.
=0,
=0.02 and
,
=0.98). Then we
recursively find the solutions. Although we may have several footpoints
in different locations of the curve, for each footpoint there is
only one unique solution between
and
, since this can be viewed
in the context of an initial value problem.