Cubic splines somehow?
David Wimp
splines. Is this function available somewhere. 20 years ago, I took a
class in which I learned how to generate the control points for Bezier
curves to produce cubic splines. Guess what. I don't remember. Does
anybody know where I might get this information. I would just do this
from scratch but I need parametric splines and that make it a bit
harder.
--
Dave
Define thine enemy and speak for him!
Charles Hacker
No Delphi does NOT have a cubic spline function directly, and neither does
windows.
You would have to program the cubic spline function in yourself,
OR
get free components that will draw cubic splines.
I saw some somewhere when I was searching for components.
Joe C. Hecht
>
> Delphi comes with a Bezier function but, apparently, no cubic
> splines. Is this function available somewhere. 20 years ago, I took a
> class in which I learned how to generate the control points for Bezier
> curves to produce cubic splines. Guess what. I don't remember. Does
> anybody know where I might get this information. I would just do this
> from scratch but I need parametric splines and that make it a bit
> harder.
Tell me about it! FWIW, You can create beziers from splines,
but you will have a tough time going the other direction!
Joe
--
Joe C. Hecht
http://home1.gte.net/joehecht/index.htm
Rene Tschaggelar
Both require a couple of equation systems to be solved.
How many datapoints do you have to fit ?
Rene
David Wimp wrote:
>
> Delphi comes with a Bezier function but, apparently, no cubic
> splines. Is this function available somewhere. 20 years ago, I took a
> class in which I learned how to generate the control points for Bezier
> curves to produce cubic splines. Guess what. I don't remember. Does
> anybody know where I might get this information. I would just do this
> from scratch but I need parametric splines and that make it a bit
> harder.
>
David Ullrich
>
> Delphi comes with a Bezier function but, apparently, no cubic
> splines. Is this function available somewhere. 20 years ago, I took a
> class in which I learned how to generate the control points for Bezier
> curves to produce cubic splines. Guess what. I don't remember. Does
> anybody know where I might get this information. I would just do this
> from scratch but I need parametric splines and that make it a bit
> harder.
Not sure what a "parametric spline" is, as opposed to just
a spline, but there's no problem using PolyBezier to draw splines.
Um, "spline" means lots of different things: If you have a collection
of points and tangent vectors there's no problem using PolyBezier to
draw a curve through those points with the given tangent vectors
at each point. (It seems to me that bezier curves are more
general than this, you can have different right-hand and
left-hand tangent vectors with a bezier curve, hence corners
if you want.)
The following is not supposed to be elegant code or nice
code or proper or optimal or anything other than an illustration
of how to use PolyBezier to draw a curve through specified points
with specified tangent vectors. Note in particular that using
TPoint for the tangent vectors is absurd, it should be TRealPoint
instead; similarly LC should return a pair of floats. Etc. The
math goes like so:
unit duNewBezier;
interface
uses Windows, Classes, Graphics;
type
PPoints = ^TPoints;
TPoints = array[0..1000000] of TPoint;
procedure DrawCurveFromPointsAndTangents(C:TCanvas; const P,T:array of TPoint);
implementation
uses SysUtils;
function LC(Pt1,Pt2:TPoint; c1,c2:extended):TPoint;
{"LinearCombination"}
begin
result:= Point(round(Pt1.x*c1 + Pt2.x*c2),
round(Pt1.y*c1 + Pt2.y*c2));
end;
procedure DrawCurveFromPointsAndTangents(C:TCanvas; const P,T:array of TPoint);
var j,H:integer; N:PPoints;
begin
H:= High(P);
if High(T)<>H then
raise Exception.Create('Error message');
GetMem(N, (3*H+1)*SizeOf(TPoint));
try
for j:=0 to H - 1 do
begin
N^[3*j] := P[j];
N^[3*j+1]:= LC(P[j],T[j],1,1/3);
N^[3*j+2]:= LC(P[j+1],T[j+1],1,-1/3);
end;
N^[3*H]:= P[H];
PolyBezier(C.Handle, N^, 3*H+1);
finally
FreeMem(N, (3*H+1)*SizeOf(TPoint));
end;
end;
end.
> Dave
>
> Define thine enemy and speak for him!
--
David Ullrich
sig.txt still not found
David Wimp
Rene Tschaggelar wrote:
> There are approximating and interpolating splines.
> Both require a couple of equation systems to be solved.
> How many datapoints do you have to fit ?
>
I need interpolating splines but my reference that derives things in the
form I need only has approximating splines. This is slowly coming back to me
but I am having flashbacks of Jimmy Carter and the oil embargo. I have about
20 points.
--
Dave
David Wimp
Joe C. Hecht wrote:
> David Wimp wrote:
> >
> > Delphi comes with a Bezier function but, apparently, no cubic
> > splines. Is this function available somewhere. 20 years ago, I took a
> > class in which I learned how to generate the control points for Bezier
> > curves to produce cubic splines. Guess what. I don't remember. Does
> > anybody know where I might get this information. I would just do this
> > from scratch but I need parametric splines and that make it a bit
> > harder.
>
> Tell me about it! FWIW, You can create beziers from splines,
> but you will have a tough time going the other direction!
Well, Bezier from splines is actually what I meant, I suppose. I mean
draw a Bezier that is a spline. I whipped out Bezier from Hermite. I am
sure I can do splines when I am up to plodding through it. I realized that
my Foley & Van Damm has this in it but listed under curves. They don't have
interpolating splines, though.
--
David Wimp
the tangent for P[i] as s*(P[i+1] - P[i-1]) (pretending to be able to do vector
arithmetic directly). I am now trying to find a reasonable way to compute the
scale factor s. Eventually, I need to convert it to spline interpolation but this
will do for now. I can appear to have solved the problem. Thanks.
David Ullrich
>
> This is Hermite interpolation, I think. I managed to do that. I am computing
> the tangent for P[i] as s*(P[i+1] - P[i-1]) (pretending to be able to do vector
> arithmetic directly). I am now trying to find a reasonable way to compute the
> scale factor s.
So it's all numeric. What the scale factor should be depends on
where the array P came from originally. If I recall correctly (worked
this out long ago and never actually used it) the code I posted assumes
that the tangents are derivatives with respect to "time", where time
is scaled the same as the array index: P[i+1] is the point on the
curve one second past the time it hit P[i].
So if you're actually sampling a curve in time intervals
of length h, ie P[j] = theCurve[j*h], then I'm pretty sure what you
want to plug in for the tangent would be h*(P[j+1] - P[j]), or better
(h/2)*(P[j+1] - P[j-1]). Pretty sure - if that's way off then I got
something backwards just now and you want 2/h instead.
I posted something here (or in the objectpascal section) a
few weeks or months ago that used PolyBezier to draw _extremely_
round circles from just four points and tangents. I can't find it
(locally) right now - there was an "oops" following where I mentioned
I'd forgotten to specify how to find what you're calling s. If you
can find that you're set (comes complete with a fudge factor valid
for circles that corrects for the difference between P[j+1]-P[j-1]
and the actual derivative.) If the above doesn't work and you can't
find that previous thread I'll try to reproduce it.
> Eventually, I need to convert it to spline interpolation but this
> will do for now. I can appear to have solved the problem. Thanks.
> --
> Dave
>
> Define thine enemy and speak for him!
--
Rene Tschaggelar
can tell them to fit closest.
I have a book called :
Numerik Algorithmen
Engeln-Muellges
Reutter
VDI Verlag
ISBN3-540-62170-9
Unfortunately in German. They have lots of splines,
interpolating, approximating, kubic, renner,.. with various
boundary conditions. There is also a CD available with
C, fortran, Turbopascal code on it. The Turbopascal code
is limited to 30 points due to the DOS memory. It would
have to be rewritten with Delphi for more points.
I didn't rewrite it yet and since there is a copyright on it,
I cannot send you a copy of the code. But as splines are
fairly standard in applied math, I suggest you get a similar
book on math with a CD.
Rene
Geir Wikran
Trigonometric Spline Curves" from the Algorithm Alley of Dr. Dobb's Journal
(http://www.ddj.com) in May 1997 (can be ordered at there web site for
$5.00).
Anyway, the demo-program for the article, which demonstrates different
trigonometric and cubic splines, can still be downloaded. It contains full
source code i pascal.
http://www.ddj.com/ftp/1997/1997.05/aa597.zip
http://www.ddj.com/ftp/1997/1997.05/aa597.asc
Geir
Charles Hacker
I teseted it and it works okay.
The code is given below:
private
{ Private declarations }
pntval: ARRAY [1..2,0..1000] of INTEGER;
pnum: INTEGER;
*
*
( Routine to define X,Y set of points *)
i.e
pnum:= 100
FOR temp:= 0 TO pnum DO
BEGIN
pntVal[1,pnum]:= RANDOM(100);
pntVal[2,pnum]:= RANDOM(100);
END;
procedure TMainWin.DrawSpline(Sender: TObject);
VAR loop,cyc,NVal,X,Y:INTEGER;
xA, xB, xC, xD, yA, yB, yC, yD, t : REAL;
b0, b1, b2, b3, a0, a1, a2, a3 : REAL;
BEGIN
Screen.Cursor:= crHourGlass;
INC(pnum);
pntVal[1,pnum]:= pntVal[1,pnum-1];
pntVal[2,pnum]:= pntVal[2,pnum-1];
NVal:= 100;
pntVal[1,pnum+1]:= pntVal[1,pnum];
pntVal[2,pnum+1]:= pntVal[2,pnum];
FOR loop:= 1 TO pnum-1 DO
BEGIN
xA:=pntVal[1,loop-1]; xB:=pntVal[1,loop];
xC:=pntVal[1,loop+1]; xD:=pntVal[1,loop+2];
yA:=pntVal[2,loop-1]; yB:=pntVal[2,loop];
yC:=pntVal[2,loop+1]; yD:=pntVal[2,loop+2];
a3:= (-xA+3*(xB-Xc)+xD)/6;
a2:= (xA-2*xB+xC)/2;
a1:= (xC-xA)/2;
a0:= (xA+4*xB+xC)/6;
b3:= (-yA+3*(yB-yc)+yD)/6;
b2:= (yA-2*yB+yC)/2;
b1:= (yC-yA)/2;
b0:= (yA+4*yB+yC)/6;
FOR cyc:= 0 TO NVal DO
BEGIN
t:= cyc/NVal;
X:= ROUND(((a3*t+a2)*t+a1)*t+a0);
Y:= ROUND(((b3*t+b2)*t+b1)*t+b0);
IF (cyc=0) THEN
Canvas.MoveTo(X,Y)
ELSE
Canvas.LineTo(X,Y);
END;
END;
DEC(pnum);
Screen.Cursor:= crDefault;
END;
David Ullrich
look for
Newsgroups: borland.public.delphi.graphics
Subject: Re: HELP!!! Drawing curve pls!
Date: Wed, 02 Dec 1998 12:55:08 -0600
and followups on the details I left out there.
(ii) In the situations I've had in mind I've had some points _and_
some tangent vectors as given. If you're just interpolating a sequence
of points then finding the appropriate tangent vectors using
P[j+1] - P[j-1], then sending those tangent vectors to that
routine for conversion to control points and then a Bezier
curve is going in circles. Pretty sure you can accomplish
exactly the same thing much more directly, getting the
control points as simple linear combinations of the
data points.
David Wimp
David Ullrich wrote:
Yes, this is what I learned in class 20 years ago. There is a way to
generate the two Bezier points not interpolated by Bezier curves from 4
data points so that the resulting curve is a spline. I have gotten enough
information to do this now but am busy on something else at the moment. I
will post the solution when I can. Somebody in this thread posted some
code from Dr. Dobbs that has the matrix in it that is needed to do this.
David Wimp
Geir Wikran wrote:
Thanks. The matrix I need to do what I want appears as a comment in the
first link. I forgot the name of it. I would have spent a while figuring it
out.
David Wimp
Charles Hacker wrote:
The reason I want to generate the splines via Bezier curves is so I don't
have to actually render the curves. I don't have to reimplement line styles,
pen colors, and all that. The information I need is imbedded in the code, but
is given explicitly in matrix form in comments in the examples from Dr. Dobbs
posted by Geir Wikrin. This discussion has been very helpful in reviving my
fading memories of the subject. Thanks.
> Rene Tschaggelar wrote:
>
> > You can always use the approximating splines when you
> > can tell them to fit closest.
> >
> > I have a book called :
> > Numerik Algorithmen
> > Engeln-Muellges
> > Reutter
> > VDI Verlag
> > ISBN3-540-62170-9
> > Unfortunately in German. They have lots of splines,
> > interpolating, approximating, kubic, renner,.. with various
> > boundary conditions. There is also a CD available with
> > C, fortran, Turbopascal code on it. The Turbopascal code
> > is limited to 30 points due to the DOS memory. It would
> > have to be rewritten with Delphi for more points.
> > I didn't rewrite it yet and since there is a copyright on it,
> > I cannot send you a copy of the code. But as splines are
> > fairly standard in applied math, I suggest you get a similar
> > book on math with a CD.
> >
--
Volker W. Walter
in German, with FORTRAN source text
Helmuth Späth,
Spline Algorithmen
zu Konstruktion glatter Kurve und Flächen
Oldenbourg Verlag 1973
Helmuth Späth,
Eindimensionale Spline-Interpolations-Algorithmen
Oldenbourg Verlag 1990
in English, "THE SPLINE BIBLE", with sometimes tricky FORTRAN
Carl de Boor
A practical Guide to Splines
Springer Verlag 1978
!! Non-mathemticians have to work on this boook, not only reading it:
Sources at NETLIB:
http://phyvax.ir.miami.edu:8001/chomko/links/netlib_src.html
see
lib pppack
for splines
by Carl de Boor
ref A Practical Guide to Splines, Springer Verlag.
# Some calling sequences differ slightly from those in the book.
rel excellent
age old
editor Eric Grosse
master netlib.bell-labs.com
see also for smoothing
lib dierckx
for spline fitting routines for various kinds of data and geometries
by Paul Dierckx <Paul.D...@cs.kuleuven.ac.be>
# Comp Sci, K. U. Leuven, Celestijnenlaan 200A, B-3001 Heverlee,
Belgium
# also called fitpack, but no connection with Alan Cline's library
master netlib.bell-labs.com
and
lib gcv
for Generalized Cross Validation spline smoothing
editor Eric Grosse
master netlib.bell-labs.com
Volker
David Wimp
Volker W. Walter wrote:
I have "A Practical Guide to Splines" or did, at least. This was the
first book I looked for. I think I have things under control, however.
"Tricky" is probably too kind for DeBoors coding style. His was terrible
even for the times. I looked through some of those ppack routines and some
others that were on line. It seemed that all of them only handled spline
functions, not arbitrary 2d curves. The x-values have to be in ascending
order.
Davie Reed
Dr. Dobb's Journal and it was in NewsPaper form? :)
Davie
P.S. I do, 1979
Volker W. Walter
>
> I have "A Practical Guide to Splines" or did, at least. This was the
> first book I looked for. I think I have things under control, however.
> "Tricky" is probably too kind for DeBoors coding style. His was terrible
> even for the times. I looked through some of those ppack routines and some
> others that were on line. It seemed that all of them only handled spline
> functions, not arbitrary 2d curves. The x-values have to be in ascending
> order.
The base TRICK is using 2 dimensional FORTRAN arrays a[col,row] outside
of a
SUBROUTINE and using this as 1 dimensional array a[i] inside or vice
versa,
I don't remember exactly. Ordering 2d arrays is different in FORTRAN and
Pascal
FORTRAN PASCAL
+--------+ +--------+
| 1 5 9| | 1 2 3|
| 2 6 10| | 4 5 6|
| 3 7 11| | 7 8 9|
| 4 7 12| |10 11 12|
+--------+ +--------+
When this is in your mind, it is not too complicated, but enough
efficient:
CONST
OPNaRRAYmAXiDX=((VwLowL.MEMBlockMax) DIV SizeOf(stdFlt)-1);
ARRAYmAXiDX=OPNaRRAYmAXiDX DIV (5-4);
TYPE
ftnIndexSbr=1..ARRAYmAXiDX; {FORTRAN tradition: OPTION BASE
1}
ftnFltArr=ARRAY[ftnIndexSbr] OF stdFlt;
ftnFltPtr=^ftnFltArr;
TYPE
dynFltBasObj=OBJECT
PUBLIC
p:ftnFltPtr;
fCount,fCapacity:stdInt;
byteSize:stdInt;
PROCEDURE Clear;
CONSTRUCTOR Allocate(CONST x:stdInt);
DESTRUCTOR DeAllocate;
PROCEDURE ReAllocate(CONST x:stdInt);
END; {+object
=dynFltBasObj}
TYPE
ftn1FltObj=OBJECT(dynFltBasObj)
PUBLIC
elms:stdInt;
CONSTRUCTOR Allocate(CONST x:stdInt);
DESTRUCTOR DeAllocate;
FUNCTION I1(CONST x:stdInt):stdInt;
END; {+object
=ftn1FltObj}
TYPE
ftn2FltObj=OBJECT(ftn1FltObj)
PUBLIC
rows,cols:stdInt;
CONSTRUCTOR Allocate(CONST y{zeilen},x{spalten}:stdInt);
DESTRUCTOR DeAllocate;
FUNCTION SetFtnDim(CONST y,x:stdInt):Boolean;
PROCEDURE BecomesFtnDim(CONST x:ftn2FltObj);
FUNCTION I2(CONST y{zeile},x{spalte}:stdInt):stdInt;
END; {+object
=ftn2FltObj}
With this a variable a:ftn2FltObj may be accessed
directly a.p^[ī]
1 dim a.p[ a.I1(j) ]
2 dim a.p[ a.I2(j,k) ]
and deBoors FTN programs cam be translated to BP7.
Volker