Distance to a Quadratic bezier curve

Recently, after viewing this illuminating animated GIFs, I realized that finding the closest point on a quadratic Bezier curve to a given point M might be not so difficult ...and very useful for detecting collision between a disk and a quadratic curve.

Quadratic Bezier curves are familiar to flash programmers, because these are the curves they draw with functions like Movieclip.moveTo() and Movieclip.curveTo().

Such Bezier curve is defined by 3 points: P0, P1, P2.
P0 and P1 are the extreme points, and P1 is a middle point determining curvature.

The curve can be parametrized with the formula:

P(t) = (1-t)²P0 + 2t(1-t)P1 +t²P2.

t is a parameter variable walking from 0 to 1. When t = 0, you are at point P0, and when t = 1, u're at P2.Each point of the curve has a corresponding "t".
The above-mentioned animated GIFs greatly help to "geometrically" grasp not only the quadratic curves, but also higher order Bezier curves .

Now, the key step is to get the derivative (back to school!! ) of P(t):

dP/dt(t) = -2(1-t)P0 + 2(1-2t)P1 + 2tP2

which can be rewritten as:

dP/dt(t) = 2(A+Bt)
where A = (P1-P0) and B = (P2-P1-A)

(note: A and B have a geometric signification: they are the diagonals of the parallelogram defined by P0,P1,P2 and a fourth point kind of "opposite" from P1)

The derivative is a vector representing the "speed" at point defined by P(t). It also has the property to be a tangent to the curve at point P(t).

Now let M(x,y) be our point (which can be anywhere) and we want to find out a point P' (defined by t') on Bezier curve that is the closest possible to M.

P(t') will meet the condition:

MP.dP/dt = 0
(where "." is the dot product of 2 vectors)

that is, MP will be orthogonal to the tangent at P.
Rewritting this condition yields:

(M - (1-t)²P0 + 2t(1-t)P1 +t²P2).(A+Bt) = 0

...After a (boring ) calculus you get a third degree equation (ouch!! ):

at3 + bt² + ct + d = 0,

where a = B², b = 3A.B, c = 2A²+M'.B, d = M'.A, (and M' = P0-M)

If we can solve this equation, we get 3 possible solutions for t !!
How to solve a third degree equation is explained here (in french).
Now we have a maximum of 3 solutions t0, t1, t2 and find the one fitting in [0,1] and minimizing dist(M, P(t)) is easy !!

Here is a demo:

Drag the circled dots
P0 and P2 are the blue points, P1 is green , M is red.
The yellow dot is the closest point, the orange dot indicates the normal to M.

After this, I realized that Andre Michelle had already posted a ball collision detection on his blog a long time ago. But the source wasn't available (at least I didn't work for nothing )...

The source code (AS2, FLA CS3 + Bezier.as).
Translating it into as3 should be no problem .

[UPDATE 2012/08/06] I fixed the issue pointed by makc3d. Now the end points are included as a possible solution, which is more consistent. I added a flad "onCurve" indicating if the closest point is on the curve itself (true), or one of the end points (false). The "oriented distance" is negative when the point is on the right of the path formed by [P0,P1,P2]. For backward compatibility, I kept this info in the variable "orientedDist", but it loses its meaning when the closest point is not on the curve.