# Board index » delphi » Cubic splines somehow?

## Cubic splines somehow?

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.

--
Dave

Define thine enemy and speak for him!

## Re:Cubic splines somehow?

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.

##### Quote
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.

> --
> Dave

> Define thine enemy and speak for him!

## Re:Cubic splines somehow?

##### Quote
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!

Joe
--
Joe C. Hecht
http://home1.gte.net/joehecht/index.htm

## Re:Cubic splines somehow?

There are approximating and interpolating splines.
Both require a couple of equation systems to be solved.
How many datapoints do you have to fit ?

Rene

##### Quote
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.

> --
> Dave

> Define thine enemy and speak for him!

## Re:Cubic splines somehow?

##### Quote
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.

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.

##### Quote
> Dave

> Define thine enemy and speak for him!

--
David Ullrich

## Re:Cubic splines somehow?

##### Quote
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

## Re:Cubic splines somehow?

##### Quote
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.

--
Dave

Define thine enemy and speak for him!

## Re:Cubic splines somehow?

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.  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!

## Re:Cubic splines somehow?

##### Quote
David Wimp wrote:

>     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.

##### Quote
> 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!

--
David Ullrich

## Re:Cubic splines somehow?

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.

Rene

##### Quote
David Wimp wrote:

> 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

## Re:Cubic splines somehow?

You should have had Robert F. Kauffmann's article "Implementing Uniform
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
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

## Re:Cubic splines somehow?

I got out a Numerical Computing book and programmed a cubic spline function.
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;

##### Quote
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.

## Re:Cubic splines somehow?

Two updates: (i) Ralph found the thread I was referring to -
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 Ullrich

## Re:Cubic splines somehow?

##### Quote
David Ullrich wrote:
> Two updates: (i) Ralph found the thread I was referring to -
> 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.

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.
--
Dave

Define thine enemy and speak for him!

## Re:Cubic splines somehow?

##### Quote
Geir Wikran wrote:
> You should have had Robert F. Kauffmann's article "Implementing Uniform
> 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

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.

--
Dave

Define thine enemy and speak for him!

Go to page: