Shortest distance between clothoid spline and point

1.6k Views Asked by At

Is there any way to analytically decide the shortest distance between a spline of clothoids and a point? Both lies in XY-plane. The clothoid spline has G2 continuity. The result should be used in geometric optimzation, so squared distance (xp - xc)2 + (yp - yc)2 may be used.

If there is no analytic solution, can anyone give a good suggestion to an iterative solution.

Definition of clothoid and splines:
Clothoid is also called Cornu spiral or Euler spiral.
http://mathworld.wolfram.com/CornuSpiral.html

A spline is a piecewise-defined function:
http://en.wikipedia.org/wiki/Spline_(mathematics)

1

There are 1 best solutions below

0
On

There is no analytical solution, since that would include solving integral equations. There are however very fast numerical solutions. Those involve minizing distance function $d(t)=\left(\vec{r}(t)-\vec{p}\right)^2$ where $\vec{p}$ is the point you want to calculate distance to and $t$ parametrizes your clothoid which is given by $\vec{r}(t)$.

You have mentioned that your clothoids are "non-agressive" which I presume means that tangent from the start till the end of the clothoid does not rotate by a large angle. That will make $d(t)$ well behaved function of the parameter along the clothoid.

What you can do then is to subdivide your spline in sections where tangent at the beginning and the end make up angle not larger than 60 degrees. You are guaranteed that there will be no more than one extremum of $d(t)$ on that section. You can then check if $d'(t_0)d'(t_1) < 0$, where $t_0$ and $t_1$ are parameters of endpoints of your section. If this condition is satisfied you can apply for example Dekker's method to find a zero of $d'(t)=2\left(\vec{r}(t)-\vec{p}\right)\cdot\vec{r}'(t)$ (you can compute $\vec{r}'(t)$ analytically). It will converge in few iterations and you can then check whether you have minimum or maximum there by checking in final iteration whether $\left(d'(a_{k})-d'(b_{k})\right)/(a_k-b_k)>0$ (see Wikipedia article for the notation).