next up previous contents index
Next: 10.6 Numerical applications Up: 10. Geodesics Previous: 10.4.2 Circular arc approximation   Contents   Index


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 $ A$ and a curve $ C$ on a parametric surface $ {\bf r}(u,v)$ defined as $ {\bf r}^c(t) = {\bf r}(u^c(t), v^c(t))$ , we want to compute the shortest path between point $ A$ and curve $ C$ 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 $ C$ and the shortest path by $ B$ . Wolter [449] developed a necessary condition to have a shortest path from point $ A$ to curve $ C$ , provided that the point $ B$ is not an end point of the curve $ C$ . The condition is given by the orthogonality of the tangent vector of the geodesic curve, connecting $ A$ and $ C$ , at $ B$ and the tangent vector of $ C$ at $ B$ . If point $ B$ were known, the problem could be reduced to an IVP, since at point $ B$ , $ u$ , $ v$ , $ p$ and $ q$ are all known. However, point $ B$ can be found only by solving the problem. We guess a parameter value $ t=t_B$ for point $ B$ and solve the BVP. In general the unit tangent vector of the curve $ {\bf r}^c(t)$ and the unit tangent vector of the arc length parametrized geodesic curve $ {\bf r}^g(s)$ at the guessing point will not be orthogonal to each other. Consequently, we need to adjust the parameter value $ t_B$ 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 $ {\bf t}^c$ and $ {\bf t}^g$ , then they can be expressed as follows:
$\displaystyle {\bf t}^c = \frac{\frac{d{\bf r}^c(t)}{dt}}{\left\vert\frac{d{\bf... ...t}x_u + \frac{dv^c}{dt}x_v)^2+ (\frac{du^c}{dt}y_u + \frac{dv^c}{dt}y_v)^2}}\;,$     (10.66)
$\displaystyle {\bf t}^g = \frac{d{\bf r}^g(s)}{ds} = {\bf r}_u\frac{du^g}{ds} + {\bf r}_v\frac{dv^g}{ds}\;.$     (10.67)

Figure 10.4: Shortest path between point $ A$ and curve $ C$ (adapted from [247])
\begin{figure}\centerline{ \psfig{figure=fig/ortho.PS,height=2.5in} }\end{figure}
Therefore the orthogonality condition can be written as
$\displaystyle \omega(t) = {\bf t}^c \cdot {\bf t}^g = \frac{\frac{du^g}{ds}\fra... ...u + \frac{dv^c}{dt}x_v)^2+ (\frac{du^c}{dt}y_u + \frac{dv^c}{dt}y_v)^2}} = 0\;.$     (10.68)

Consequently we need to find a parameter value $ t_B$ such that $ \omega(t_B)=0$ . Since the relationship described above is implicit, we use the secant method [69] instead of Newton's method to obtain $ t_B$ . The secant method can be derived from Newton's method by replacing the derivative $ \frac{d\omega^{(i)}}{dt}$ by the quotient $ (\omega^{(i)} - \omega^{(i-1)})/(t^{(i)} - t^{(i-1)})$ where superscripts $ (i)$ denote $ i$ -$ th$ iteration. This leads to the following scheme
$\displaystyle t^{(i+1)} = t^{(i)} + \Delta t^{(i)},\;\;\;\;\;\Delta t^{(i)}=-\f... ...i)} - \omega^{(i-1)}}\omega^{(i)} ,\;\;\;\;\;\omega^{(i)}\neq \omega^{(i-1)}\;.$     (10.69)

Notice that the secant method requires two initial approximations $ t^{(1)}$ and $ t^{(2)}$ . Since the secant method has an order of convergence of $ \frac{1}{2}(1+\sqrt{5})\simeq 1.618$ [69], it converges within a reasonable number of iterations. If the correction $ \Delta t^{(i)}$ is large, it is again an indication that the problem is highly nonlinear. In such case we also employ a step correction procedure
$\displaystyle t^{(i+1)} = t^{(i)} + \nu\Delta t^{(i)}\;,$     (10.70)

where $ \nu$ is a correction factor $ 0< \nu\leq 1$ , 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 $ 0\leq t \leq 1$ , we start from both ends of the curve (i.e. $ t^{(1)}$ =0, $ t^{(2)}$ =0.02 and $ t^{(1)}=1$ , $ t^{(2)}$ =0.98). Then we recursively find the solutions. Although we may have several footpoints $ B$ in different locations of the curve, for each footpoint there is only one unique solution between $ A$ and $ B$ , since this can be viewed in the context of an initial value problem.

next up previous contents index
Next: 10.6 Numerical applications Up: 10. Geodesics Previous: 10.4.2 Circular arc approximation   Contents   Index
December 2009