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:
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.
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".