cet1@cl.cam.ac.uk (C.E. Thompson) (05/31/90)
In article <7232@jarthur.Claremont.EDU> dhosek@sif.claremont.edu writes: >In article <21535@megaron.cs.arizona.edu>, sham@cs.arizona.edu (Shamim Zvonko Mohamed) writes: >> Does anyone have any code to interpolate a set of points using Bezier curves? >> Ideally, something that takes points and generates the Bezier control points >> usable in Postcript for the interpolation. Any references to something like this > >You may want to look at the source code for Metafont (published >by Addison Wesley under the title _Metafont: The Program_ by >Donald Knuth). There are quite a few interesting routines in here >that do what you want or do things that you want to do but didn't >realize you wanted to. > You should read this in conjunction with the description in the METAFONTbook, pages 130ff. On the other hand, if you want the theoretical background, you can find it in ``Smooth, Easy to Compute Interpolating Splines'' by John D{ouglas} Hobby (Stanford University Report STAN-CS-85-1047, January 1985). From what Donald Knuth says in the METAFONTbook, the essence of this probably also appeared in Discrete and Computational Geometry 1 (1986) pp 123-140, but I have only read the former. Although this is getting away from the question about splines, the theoretical background for many of the *other* algorithms in METAFONT can be found in John Hobby's PhD thesis ``Digital Brush Trajectories'' (STAN-CS-85-1070). Chris Thompson JANET: cet1@uk.ac.cam.phx Internet: cet1%phx.cam.ac.uk@nsfnet-relay.ac.uk
woody@chinacat.Unicom.COM (Woody Baker @ Eagle Signal) (06/04/90)
In article <1910@gannet.cl.cam.ac.uk>, cet1@cl.cam.ac.uk (C.E. Thompson) writes: > > On the other hand, if you want the theoretical background, you can find it > in ``Smooth, Easy to Compute Interpolating Splines'' by John D{ouglas} Hobby > (Stanford University Report STAN-CS-85-1047, January 1985). From what > > Although this is getting away from the question about splines, the theoretical > background for many of the *other* algorithms in METAFONT can be found in > John Hobby's PhD thesis ``Digital Brush Trajectories'' (STAN-CS-85-1070). > I've given considerable thought to this problem (tracing curves), and it seems to me, that one can classify any 4 points in a set of data points (provided they are close enough to a straight line), as sets of control/data points. Consider the subdivision spline technique. When you have subdivided the spline to withing your tolerance limit, you essentialy have a collection of short splines whose control and end points (any given set of 4 points) create an essentialy straight line. It seems to me that it should be possible to reverse the subdivision algo, and go back a given number of iterations, to arrive at a set of control points, that would generate a curve that passes through the data points. Perhaps this is wrong, and if we have any great math guru types out here, perhaps they could tell us if it would work or not. It is an attractive thought, given that the subdivision is accomplished by division by 2 (simple shifts) Cheers Woody
larry@csccat.UUCP (Larry Spence) (06/05/90)
In article <1295@chinacat.Unicom.COM> woody@chinacat.Unicom.COM (Woody Baker @ Eagle Signal) writes: >I've given considerable thought to this problem (tracing curves), and it >seems to me, that one can classify any 4 points in a set of data points >(provided they are close enough to a straight line), as sets of control/data >points. Sure, but you've already stated the drawback: the data points have to be nearly in a straight line for this to work. If that's the case, why not just approximate with a line segment? Your approach would result in lots of nearly-flat Bezier segments. Am I missing something here? -- Larry Spence larry@csccat ...{texbell,texsun}!csccat!larry
woody@chinacat.Unicom.COM (Woody Baker @ Eagle Signal) (06/06/90)
In article <3710@csccat.UUCP>, larry@csccat.UUCP (Larry Spence) writes: > In article <1295@chinacat.Unicom.COM> woody@chinacat.Unicom.COM (Woody Baker @ Eagle Signal) writes: > >I've given considerable thought to this problem (tracing curves), and it > > Sure, but you've already stated the drawback: the data points have to > be nearly in a straight line for this to work. If that's the case, why not > just approximate with a line segment? Your approach would result in lots of > nearly-flat Bezier segments. > > Am I missing something here? Yes. Consider any set of control points and end points for a single spline. The subdivision method of generating the points that are used to draw the spline, basicaly moves the control points closer and closer to the actual curve, and creates more and more of them. Eventualy, when you have done some arbitrary number of iterations, you can consider that the generated points define (for any single point) an endpoint and control point that lay on the same physical spot. You then draw a series of straight lines between the generated points and bingo, you have a spline. Since you are moving the points closer and closer to the final line, it seems to me that you could take the final line, divide it up into segments that are an even power of 2 or whatever, and then start moving points backward, and reducing the number of points until you got back to only 2 end points and 2 control points, at which point you should have your original control and end points back. Whew!. My question, is can the subdivision method be reversed? Cheers Woody > > -- > Larry Spence > larry@csccat > ...{texbell,texsun}!csccat!larry
uad1077@dircon.uucp (06/07/90)
> create an essentialy straight line. It seems to me that it should be possible > to reverse the subdivision algo, and go back a given number of iterations, to > arrive at a set of control points, that would generate a curve that passes > through the data points. No, it doesn't work that way. The reason cubic curves have 4 controls is because you have to completely specify 4 coefficients in the cubic polynomial that gives the curve. If you glue two cubics together, then you have 8 controls (although there may be constraints introduced by whatever order of continuity you are interested in), but that does mean that you get a 7th-order polynomial as a result. YOu are now faced with the problem of approximating a 7th-degree polynomial with a cubic, which is harder than the original problem of apporximating a set of data points with a cubic, before you can proced to the next stage of `unsubdivison'. I agree though: like much of numerical work, it IS a pity! -- Ian D. Kemmish Tel. +44 767 601 361 18 Durham Close uad1077@dircon.UUCP Biggleswade ukc!dircon!uad1077 Beds SG18 8HZ United Kingdom
larry@csccat.UUCP (Larry Spence) (06/07/90)
In article <1304@chinacat.Unicom.COM> woody@chinacat.Unicom.COM (Woody Baker @ Eagle Signal) writes: > >Since you >are moving the points closer and closer to the final line, it seems to me >that you could take the final line, divide it up into segments that are >an even power of 2 or whatever, and then start moving points backward, and >reducing the number of points until you got back to only 2 end points and >2 control points, at which point you should have your original control and >end points back. Uh uh. First, how can you know which sequences of data points correspond to the individual Bezier segments in the original outline? In other words, how do you look at your input data and say, "those points between p[23] and p[98], yeah, those are from exactly one Bezier segment, and p[98] to p[227], that's from another Bezier segment"? Second, you have to calculate a parametrization for the data -- the point in the middle of a curve doesn't necessarily correspond to the parameter value 0.5. So to answer your last question, the subdivision isn't easily reversible; you've lost the parametrization. If you knew the parametrization and where to set the breakpoints, then it _would_ be trivial. Your approach as stated also makes no provision for maintaining tangent continuity between adjacent segments, and would be very susceptible to noise in the input data. -- Larry Spence larry@csccat ...{texbell,texsun}!csccat!larry
woody@chinacat.Unicom.COM (Woody Baker @ Eagle Signal) (06/10/90)
thanks for your input. It was a thought, and being a non-mathmatician I was curious. Now for a diffrent topic. I just recieved a note about release 3.0 of Arts & L. What are the diffrences? Did any of my list of suggestions make it in? And I was hoping to do a beta for release 3.0. Perhaps no one remembered.. Cheers Woody