woody@rpp386.cactus.org (Woodrow Baker) (02/01/90)
In article <1990Jan31.213001.11641@intercon.com>, amanda@mermaid.intercon.com (Amanda Walker) writes: > In article <17811@rpp386.cactus.org>, woody@rpp386.cactus.org (Woodrow Baker) > writes: > > The little spline routine that was sent to me, was much appreciated. > > Now, a followup question. Given the resulting array of points, > > created by the subdivision of the spline, is is possible to reverse the > > proceedure, and work back to the original set of corrdinates. If so, > It should be possible, since four points will uniquely define a cubic > curve. It's been a while since I took Analytic Geometry :-), but you > should be able to take four points on the curve, spaced as equally as > possible to assure maximum accuracy, and write four equations in four > unknowns (one for each point, with the unknowns being the coefficients > of the cubic), which you can then solve using Gaussian elimination or I have been working on this problem for a while. I have arrived at using a Gauss-Jordan elimination. I still have not got it implemented. I recieved a snippet of 'C' code, that took 2 endpoints and 2 control points and by subdividing the spline recursively until an arbitrary tolerance limit was reached, resulted in an array of coordinates that when plotted draws the spline. My question concernes taking that array, and working it backward through the mirror of the subdivision, and coming to the original points. The subdivision code was implemented by shifting in order to divide by 2. Can a mirror function be readily created such that when passed the array of points, (always a multiple of 2 long), you can reconstruct the original 4 sets of points? I am not sure that a Gauss Jordan curve fitter would be the most effecient way to do this. Any ideas anyone? p PS, thanks for the post... Cheers Woody > > "Many of the truths we cling to depend greatly upon our own point of view." > --Obi-Wan Kenobi in "Return of the Jedi"
hemphill@cit-vax.Caltech.Edu (Scott Hemphill) (02/01/90)
woody@rpp386.cactus.org (Woodrow Baker) writes: > Now, a followup question. Given the resulting array of points, > created by the subdivision of the spline, is is possible to reverse the > proceedure, and work back to the original set of corrdinates. If so, > what are the pitfalls, and where might there be code or references? > It looks possible, given that every thing was done with shifts. amanda@mermaid.intercon.com (Amanda Walker) writes: >It should be possible, since four points will uniquely define a cubic >curve. It's been a while since I took Analytic Geometry :-), but you But *six* points are necessary to uniquely determine a *parametric* cubic curve. The following PostScript fragment shows 4 points with two different Bezier curves passing through them. %! /in {72 mul} bind def 4.25 in 5.5 in translate /dot {currentpoint 0.05 in 0 360 arc fill} bind def -3 in -1 in moveto dot -1 in 1 in moveto dot 1 in 1 in moveto dot 3 in -1 in moveto dot -3 in -1 in moveto -1 in 2 in 1 in 2 in 3 in -1 in curveto stroke -3 in -1 in moveto 7 in 9 div 23 in 9 div -7 in 9 div 23 in 9 div 3 in -1 in curveto stroke showpage kchen@Apple.COM (Kok Chen) writes: >Actually it may be much easier than that (without invoking C. F. Gauss :-), >[interesting algorithm deleted] >This is having less and less to do with comp.lang.postscript These sound like the questions one asks to figure out how to reverse-engineer PostScript fonts. -- Scott Hemphill hemphill@csvax.caltech.edu ...!ames!elroy!cit-vax!hemphill
woody@rpp386.cactus.org (Woodrow Baker) (02/01/90)
In article <38227@apple.Apple.COM>, kchen@Apple.COM (Kok Chen) writes: > amanda@mermaid.intercon.com (Amanda Walker) writes: > Actually it may be much easier than that (without invoking C. F. Gauss :-), > and (A',B',C',D'). Where D = A'. > > Now, construct a point U such that BCU are collinear and BC = CU. > Similarly, construct a point U' s.t. C'B'U' are collinear and > B'C' = C'U'. > > If U != U', the two Beziers cannot be reduced (without error) to a > single Bezier. You are done, and the guy who gave you the original > two Beziers lied to you :-). > > However, if U = U', construct point S s.t. ABS are collinear and > AB = BS. Construct S' s.t. S'C'D' are collinear and S'C' = C'D'. > > You have it - ASS'D' are the control points of a cubic that is the > concatenation of the original two Beziers. > > Solving for approximate answers within some flatness criteria is > left as an exercise for the student. Or, you can be real brave > (a fine line separates bravery from stupidity :-) and ignore the > U = U' check. > > "Tricks" like the above are "played" all the time when you try > to approximate/represent an n-th order Bezier with the control > points of an m-th order Bezier. Much more difficult are problems > that deal with the offsets of Bezier curves. You see attempts > at solving those periodically. > > This is having less and less to do with comp.lang.postscript > (INFO-POSTSCRIPT?). Thanks for the info. As to the above sentence, I'll have to disagree with you. Splines and transformation matrixes are the heart and soul of Postscript. They are what *REALLY* set ps apart. A complete understanding of them leads to not only better postscript code, but bettter applications that use postscript. Cheers Woody
ken@cs.rochester.edu (Ken Yap) (02/01/90)
|Thanks for the info. As to the above sentence, I'll have to disagree |with you. Splines and transformation matrixes are the heart and soul |of Postscript. They are what *REALLY* set ps apart. A complete understanding |of them leads to not only better postscript code, but bettter applications |that use postscript. Well, there was this language called Interpress that also had transformation matrices and many of the features that went into PS. I think the founders of Adobe can tell you all about it and the people at Xerox are sorry that they didn't pay more attention when the story was first told. :-) :-(
woody@rpp386.cactus.org (Woodrow Baker) (02/02/90)
In article <13711@cit-vax.Caltech.Edu>, hemphill@cit-vax.Caltech.Edu (Scott Hemphill) writes: > woody@rpp386.cactus.org (Woodrow Baker) writes: > > Now, a followup question. Given the resulting array of points, > > created by the subdivision of the spline, is is possible to reverse the > > proceedure, and work back to the original set of corrdinates. If so, > > what are the pitfalls, and where might there be code or references? > > It looks possible, given that every thing was done with shifts. > > amanda@mermaid.intercon.com (Amanda Walker) writes: > >It should be possible, since four points will uniquely define a cubic > >curve. It's been a while since I took Analytic Geometry :-), but you I think it is quite clear that Amanda is talking about the 2 knots, and teh 2 control points to define a Bezier curve. > > But *six* points are necessary to uniquely determine a *parametric* cubic curve. > The following PostScript fragment shows 4 points with two different Bezier > curves passing through them. > > %! > /in {72 mul} bind def > 4.25 in 5.5 in translate > /dot {currentpoint 0.05 in 0 360 arc fill} bind def > -3 in -1 in moveto dot > -1 in 1 in moveto dot > 1 in 1 in moveto dot > 3 in -1 in moveto dot > -3 in -1 in moveto > -1 in 2 in 1 in 2 in 3 in -1 in curveto stroke > -3 in -1 in moveto > 7 in 9 div 23 in 9 div -7 in 9 div 23 in 9 div 3 in -1 in curveto stroke > showpage > interesting code. > These sound like the questions one asks to figure out how to reverse-engineer > PostScript fonts. ActuActually, these are questions that one asks, when one is working on creating an interactive spline drawing program. They are also useful for fonts, but my primary quest is for automatic curve fitting, and interactive spline drawing programs. Cheers Woody
amanda@mermaid.intercon.com (Amanda Walker) (02/03/90)
In article <17846@rpp386.cactus.org>, woody@rpp386.cactus.org (Woodrow Baker) writes: > I think it is quite clear that Amanda is talking about the 2 knots, and teh > 2 control points to define a Bezier curve. Actually, I meant any four points *on* the curve--an nth order polynomial is uniquely determined by n+1 points--but I forgot that parametrics need more points, since y isn't a function of x anymore. Ah well, I did say that it's been a while since I took Analytic Geo. :-). My next posting will actually be about PostScript :-). -- Amanda Walker InterCon Systems Corporation "Many of the truths we cling to depend greatly upon our own point of view." --Obi-Wan Kenobi in "Return of the Jedi"