2
$\begingroup$

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)

  • 0
    This is true for my problem: we use rather short and straight parts of the clothoid. The problem domain is road and rail geometry; a road/rail is built of straight lines, arcs and "non-aggressive" clothoids. We need this to be solved as a part of an extensive optimization algorithm, hence the method need to be as fast as possible. **Analytic solution is preferrable if such exists?** Bisection seems to be slow, but may be used to generate a starting guess for a faster algorithm.2012-11-30

1 Answers 1

1

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).