Path: csiph.com!feeder.erje.net!2.us.feeder.erje.net!nntp.club.cc.cmu.edu!micro-heart-of-gold.mit.edu!bloom-beacon.mit.edu!bloom-beacon.mit.edu!panix!panix.com!forkosh From: JohnF Newsgroups: comp.lang.postscript Subject: Re: a smooth curve through given points ? Date: Sun, 14 Aug 2016 06:17:57 +0000 (UTC) Organization: PANIX Public Access Internet and UNIX, NYC Lines: 72 Message-ID: References: <3243f726-6885-4ae2-aac9-f8834261dc73@googlegroups.com> NNTP-Posting-Host: panix3.panix.com X-Trace: reader2.panix.com 1471155477 19640 166.84.1.3 (14 Aug 2016 06:17:57 GMT) X-Complaints-To: abuse@panix.com NNTP-Posting-Date: Sun, 14 Aug 2016 06:17:57 +0000 (UTC) User-Agent: tin/1.6.2-20030910 ("Pabbay") (UNIX) (NetBSD/6.1.5 (i386)) Xref: csiph.com comp.lang.postscript:2771 luser droog wrote: > On Friday, August 12, 2016 at 3:10:09 AM UTC-5, Peter Billam wrote: >> Hi. There must be reasonable ways of constructing a series >> of curveto's that go smoothly through a given array of points >> [x1 y1 x2 y2 ... xN yN] ... Anyone here written stuff like that, >> or know of where it could be found ? >> If I do it, it'll turn out very ad-hoc and heuristic-ish, >> with lots of arrays-of-points that cause wild behaviour :-( > > Somewhat on the same level as tlvp's thoughts, I have a few > observations about Bezier curves. Everybody probably knows > these things already, but perhaps I can describe them in a > novel way. > > A cubic Bezier curve in 2D is determined by 4 coordinate pairs, > x1 y1, x2 y2, x3 y3, x4 y4, and passes through points 1 and 4. > The vectors from the interior points to their adjacent outer > points determine the tangents as the curve passes through those > same outer points. > > In ascii-art, > > . . > . p2 p3 . > p1 p4 > > The trace of the curve from t=0 to t=1 starts at p1, then moves > toward p2, along the vector p2-p1. As the curve progresses, the > weight associated with the p2-p1 tangent vector goes from 1 to 0. > At the same time the weight associated with the p4-p3 tangent > vector goes from 0 to 1. So the instant the curve crosses the > finish t=1, it is wholly under the control of the exiting tangent > vector p4-p3. > > Now with some calculus background, we learn that tangents in general > can be found by taking the derivative of a function. The first > derivative, evaluated at a specific value for t, gives the "slope" > at the corresponding point of the original function for the same t > value. The second derivative gives the "curvature" or acceleration, > how much the slope is changing. > > The practical upshot (and skipping a few steps) is, to smoothly > connect two Bezier curves at a join, first the inner control > points adjacent to the join point need to be collinear. This gives > gives you matching slopes as the curve crosses the join. > > . . > . p2 p3 . . > p1 p4 . . p7 > p5 p6 > > need to be collinear. > > To match curvature, the magnitudes of the adjacent tangent vectors > need to be the same (or not too different). > > |p4-p3| ~= |p5-p4| > > So what remains is the "outer" inner control points, p2 and p6. > With no rigor at all, my guess is they should be collinear with > their adjacent control points. > > So, not an algorithm. But maybe this can help someone else come > up with something. Maybe see http://stackoverflow.com/questions/7715788/find-bezier-control-points-for-curve-passing-through-n-points for additional discussion. -- John Forkosh ( mailto: j@f.com where j=john and f=forkosh )