## Tuesday, January 5, 2010

### Solving the nearest point-on-curve problem in Javascript

I'm currently working on a project that requires quite a bit of geometry, so I downloaded the source code that goes along with the Graphics Gems book. Thankfully, c syntax is very similar to Javascript, so porting the code is easy. The first archive contains nearestpoint.c, which is the example provided for two concepts from the book - "Solving the Nearest Point-on-Curve Problem" and "A Bezier Curve-Based Root-Finder."

Here's the text from the book:
The basic problem can be stated in this manner: given a parametric curve Q and a point P, both in the plane, find the point on the curve closest to P (that is, find the parameter value t such that the distance from P to Q(t) is a minimum). Our approach begins with the geometry observation that the line segment (whose length we wish to minimize) from P to Q(t) is perpendicular to the tangent of the curve at Q(t) as shown in Fig. 1. The equation we wish to solve for t is

[Q(t) - P] * Q'(t) = 0.

Luckily, the example given is for a cubic Bezier curve, which is exactly what I need.