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.

A spline is a piecewise-defined function:

  • 1
    $\begingroup$ As a general rule, if a Google search for a term doesn't yield a Wikipedia or MathWorld or PlanetMath article as one of the first hits, and instead your own question appears as one of the first hits, it's a good idea to include a definition of that term in the question. $\endgroup$
    – joriki
    Nov 30 '12 at 10:50
  • 1
    $\begingroup$ Even if the definition is googleable, it is a good idea to make it easy for people to answer the question by providing the definition. $\endgroup$
    – Phira
    Nov 30 '12 at 10:56
  • $\begingroup$ Two links added for more information on Clothoid and Splines. $\endgroup$ Nov 30 '12 at 11:49
  • $\begingroup$ In many practical applications, you only use rather short or rather straight parts of a clothoid, such that any local distance minimum would be a global minimum as well. Is this the case for the individual pieces of your spline as well? If so, you could compute the distance with respect to every piece using some iterative solution, like bisection in the simplest of cases. Otherwise you'd probably need to find the correct “layer” first. $\endgroup$
    – MvG
    Nov 30 '12 at 16:41
  • $\begingroup$ 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. $\endgroup$ Nov 30 '12 at 17:41

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.