3

I have a cubic-Bezier curve defined as A, B, C, D. Where A is the start, B and C are control points, and D is the end. I understand how to find the position at any value t, where 0 <= t <= 1, and that concept in general since it just uses a handful of calls to a linear interpolation function that result in the curve. (Can be visualized easily here on wikipedia just below the heading Higher-order curves)

I am now looking to find a point on the curve that is closest to some point in space, P. Google has led me to multiple discussions, but none of them trigger the neurons in my brain to go "ooh!" Actually, to be quite honest they all fly right over my head. My math knowledge must be a little more limited than I'd like, and falls to pieces when derivatives are mentioned.

Here are some of the places Google has led me:

gamedev.net

stackoverflow.com (quadratic)

stackoverflow.com (close but I don't understand it)

Among others including an implementation in ActionScript that I can't seem to dig up again, I know I found it in a answer/comment somewhere around here...

Does anyone have the knowledge and patience to help this information click into my brain? I am considering doing the "close enough" approach and using the closest point on a line, and just iterating over the curve in very small steps. This will be slow, and accuracy will be lost. In my particular situation the accuracy is less of a concern than the speed, however, I feel there is a way to have both...

Thanks in advance.

Community
  • 1
  • 1
Tim Beaudet
  • 791
  • 7
  • 16
  • Is [this](http://www.tinaja.com/glib/cmindist.pdf) relevant? Looks like an implementation of this in postscript – harold May 25 '14 at 18:44
  • 2
    You've picked quite a complex problem for explaining without use of derivations. I'm even skeptic whether this problem can be solved in a mathematically sound way: I believe it would involve solving a fifth root, and there is no closed formula to compute that (http://en.wikipedia.org/wiki/Quintic_equation#Finding_roots_of_a_quintic_equation). So, doing an approximation is probably the best you can do anyway. – cmaster - reinstate monica May 25 '14 at 19:12
  • I looked into it a while ago and came up empty. Apparently approximations are the best we can do. – BonzaiThePenguin May 25 '14 at 19:46
  • @BlackBird on a plane or in 3d? – 4pie0 May 25 '14 at 22:03
  • I would technically rather 3D, but I suppose it could work on a plane as well? The actual implementation is of a racing circuit, so naturally there are hills, and camber. I'm leaning towards the brute force method at this point although am honestly curious about it. – Tim Beaudet May 26 '14 at 01:34

1 Answers1

4

As cmaster says, this leads to the solution of a fifth degree polynomial to find the minimum of a sixth degree polynomial

It does not really matter if it is 2D or 3D. The function to minimize is the sixth degree polynomial

f(t)=0.5*dot(p(t)-X,p(t)-X) such that 0<=t<=1

where X is the given point and p(t) the polynomial curve, and dot denotes the euclidean scalar product. Minimization can be achieved by finding all of the roots of the derivative 

f'(t)=dot(p'(t), p(t)-X)

inside the interval and comparing the function values of the roots and at the end points of the interval.

There also exist minimization methods that do not use derivatives, mainly intended for functions that are more complicated than polynomials. See for instance chapter 5 in

Brent, R. P. (1973), Algorithms for Minimization without Derivatives, Englewood Cliffs, NJ: Prentice-Hall, ISBN 0-13-022335-2

(which book nevertheless contains extensive sections on derivatives and Taylor polynomials). The method or its principal idea can also be found in "Numerical recipes" as "golden section search".

Lutz Lehmann
  • 25,219
  • 2
  • 22
  • 51