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.

Figure 1

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


Demo     Source code

2 comments:

  1. The hosting where the files are uploaded seems to be expired. Is it possible to upload them somewhere else?

    This is exactly what I'm looking for as I've stumbled on several solutions and they are all connected to Graphics Gems book.

    ReplyDelete
  2. 2antitoxic:
    http://tog.acm.org/resources/GraphicsGems/gems.zip : nearestpoint.c

    ReplyDelete