Hi Folks,

rc explained his path approximation problem.

 >My needs are...take scanned points and approximate them closely with 
 >a curve, reducing the number of points needed to describe the area,... 

I'm not sure we have the right leads yet.

Since spline approximation for font creation and 
vectorization has been a major programming activity so 
there has to be a lot of good stuff out there though most 
of it is occulted by copyright and patents.

Let me mention a few mountains on my horizon.

1) 'TeXtrace' by Peter Szabo and 'autotrace' Martin Weber 
(see their sites via Google) involve a high performance 
solution to **exactly** rc's problem. Some neat pictures. 
But I was unable to find a conceptual explanation there of 
algorithms.  Tell me if you do.

2) Knuth's metafont program involves an excellent solution 
to half of rc's problem:  Given a sequence of points in the 
plane, find the "most beautiful" geometrically smooth cubic 
spline curve that passes through all of them in order.

The algorithm is found in John Hobby's thesis (under Knuth 
direction) and there is a preprint for the published 
version on Hobby's site at Lucent.

(a) the results are brilliant and give the finest algo in 
Knuth's metafont. You can enjoy the solutions by getting 
OzTeX from the CTAN archive, which includes a variant if 
metafont called matapost (by Hobby) which has PS and PDF 
output.

(b) although the technical details are daunting (and maybe 
not optimal?) there is a clear idea behind the algorithm 
which is in fact an intelligent interpretation of the 
mechanics of a spline as used in the loft of a pre-computer 
naval architect (originally, a spline was a long, thin, 
flexionally elactic, smooth, wooden stick or plank).

The mathematical quantity Hobby minimizes is something like 
the integral of a high (fourth?) power of curvature 
suitably normalized.  That process tends to even out 
curvature eliminating gratuitous bumps.

It would be very nice to have an clear explanation that 
allows an elegant computer implemetnation, for example by 
monte-carlo methods. Our computers are more than adequate 
to simulate that sort relaxation of a combinatorial spline.

So that's a vague idea for a Hobby's nice solution of half 
the problem. Maybe Szabo or Weber understand better, but 
just as likely they have simply gotten their hands on a 
portable C-library that implements these ideas (and more).

Tell us what you find.

Cheers

Laurent S.

PS.  Does Quickdraw include a API offering at least b'zier 
curves readymade???