uad1077@dircon.uucp (Ian Kemmish) (05/31/90)
OK, the code to do this is long and VERY boring, so I'm not going to post it, or else I'll burn my supper and get a horrible phone bill, but this should get you started. YOu have a series of splines. This is a series of cubic polynomials. In fact, for auto-tracing type applications, you have TWO series of cubic polynomials, one each for X and Y. If you want C-2 (or G-2) continuity between the segments, that imposes constraints on the coefficients of neighbouring cubics. Select an arbitrary parameterisation for the cubics. This means finding the ends of each cubic within the spline, and the way t varies along the path (x(t), y(t)). In practice, I repeatedly fit the curve between two identifiably shapr corners with 1, 2, 3, etc segments until the residual sum of squares is low enough. The parameterisation I use is to have t proportional to arc length along the cubic. OK, given the number of segments and the parameterisation, you can write the curve as a large matrix equation. Building the matrix of coefficients is a really boring task. Once you have that, find a good matrix-inversion routine (thankfully it's diagonl-dominant) and use it. The right-hand side of your matrix equation is just the data points. BINGO! YOu've got a least squares fit. This is just like fitting a least squares regression line in school, except there are a lot more numbers. If you read "Curves and Surfaces for Computer Aided Geometric Design" by Gerald Farin, ISBN 0-12-249050-9, you will find the equation on p.106 as eqn (9.16). Just solve it! Incidentally, if you read this book thoroughly, you will never be scared of splines again! I got quite a kick out of watching what this procedure made of scanned in character outlines! "Try it, you'll like it" -- Ian D. Kemmish Tel. +44 767 601 361 18 Durham Close uad1077@dircon.UUCP Biggleswade ukc!dircon!uad1077 Beds SG18 8HZ United Kingdom