10.5 Shortest path between a point and a curve

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:

Figure 10.4: Shortest path between point and curve (adapted from [247])

Therefore the orthogonality condition can be written as

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

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

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.