Article

# Interpolation of BezierSplines and Cubic Splines

, 5 Jan 2008
 Rate this:
Algorithms to compute the Y - Value at an X - Position of a curve, constructed by some support-points

## Introduction

Its easy to draw a BezierSpline with GDI+ ( call `Graphics.DrawCurve(Points)` ), but how get any arbitrary Point on that drawn curve?

Please take a look at what the screenshot shows:
A Bezier-Splines-Curve (brown), constructed by 7 support-points, which subdivide the BezierSplines into 6 Bezier-Segments.
The 19 construction-points, which model the curve (orange).
The "Curve-Pointer" (red). It can be moved along the BezierSplines and its location is displayed, computed by interpolating the BezierSplines.

## How BezierSplines is constructed

Each segment between two supportpoints is constructed as BezierCurve with 4 construction-points:
The two support-points themselfes and two additional, which take care, that the grade of the bezier arriving the support-point is the same as the grade of the bezier, which leaves the support-point.

## Now interpolate it

To get the Y-value of an X-position I interpolate the BezierSplines in two steps:
First I search the Bezier-Segment, which contains the X-position. This is quickly done by a binary search:

```Dim Indx = _Points.BinarySearch(New PointF(X, 0), Function(P1, P2) P1.X.CompareTo(P2.X))
```

(The Comparison of this search only compares the Point.X-Values.)
Indx will be the bit-complement of the index of the first point with `point.X > X`.

This data I pass to the second step, to `InterpolateSegment() `

```Protected Overrides Function InterpolateSegment( _
ByVal X As Single, ByVal Indx As Integer) As PointF
'Since for Beziers there's no Y = f(X) function available, I aproximate X
'by binary try and error.
'note: Indx references the support-point *after* X
Indx = Indx * 3 'now Indx references the last *construction-point* of the
'                   BezierSegment in Me.DrawPath, which is to interpolate
Dim Pts = Me.DrawPath.PathPoints
Dim BezierSegment = New PointF() { _
Pts(Indx - 3), Pts(Indx - 2), Pts(Indx - 1), Pts(Indx)}
'binary aproximation
Dim Range = New Single() {0, 0, 1}  'elsewhere known as: Bottom, Mid, Top
Dim Dlt = -2.0F
Dim Pt As PointF
Do
Range(If(Dlt < 0, 0, 2)) = Range(1)          'set Bottom or Top to Mid
Range(1) = (Range(0) + Range(2)) / 2                    'recompute Mid
Pt = PointOfFraction(Range(1), BezierSegment)                     'try
Dlt = Pt.X - X        'for drawing an "error" smaller 0.5 is tolerable
Loop Until Math.Abs(Dlt) < 0.5
Return Pt
End Function

```

Ups! Didn't I mention DrawPath? Its a GraphicsPath, which stores all the construction-points of the BezierSplines, I'd like to get drawn. Very useful! The construction-points are stored in the ".PathPoints" - Property.

Now we come to the Casteljau-algorithm, which computes a point on a Bezier.
I'm lucky: The commentation is sufficient, so I can do without to make still more words.

```Private Shared Function PointOfFraction( _
ByVal Fraction As Single, ByVal ptBeziers() As PointF) As PointF
'Calculating a point on a BezierCurve bases on a given *Fraction* of the curve (half,
'third, else). For each two construction-points the proportionate between-point is
'computed, and is taken as new construction-point.
'So in each loop there will be found one point less, until there's only one left
'Strongly recommended: search "Casteljau" on Wikipedia. Surve to "Bezier-curve" and to
'"Casteljau-algorithm" (which is implemented here)
Dim Pts(ptBeziers.Length - 2) As PointF
For I = 0 To ptBeziers.Length - 2   'first loop copies the points to a temporary array
Pts(I) = PointBetween(ptBeziers(I), ptBeziers(I + 1), Fraction)
Next
For UBord = Pts.Length - 2 To 0 Step -1           'following loops overwrite the array
For I = 0 To UBord
Pts(I) = PointBetween(Pts(I), Pts(I + 1), Fraction)
Next
Next
Return Pts(0)
End Function

Private Shared Function PointBetween( _
ByVal Pt1 As PointF, ByVal Pt2 As PointF, ByVal Fraction As Single) As PointF
'compute the to Fraction proportionate between-point between Pt1 and Pt2
Return Pt1.Add(Pt2.Subtract(Pt1).Mult(Fraction))      'Pt1 + (Pt2 - Pt1) * Fraction
End Function
```

## Reduction

To interpolate Bezier-Spline-Segments as an Y = f(X) - function is mathematically incorrect.
Although I keep the support-points ordered "from left to right" a Segment can take forms, where it shows more than one Y-Value on certain X-positions.
My "interpolation" ignores such, and simply returns the first found Y-Value.
The failure lets itself be seen by some parts of the curve, which cannot be reached by interpolation.

Mathematically correct is to interpolate CubicSplines.
They are mathematically undefined only if two support-points set on the same X-position (as vertical line).

## Polygons, Cubic Splines

while interpolating Polygons is trivial, the same on CubicSplines is - ah - untrivial. There's no GDI+ - Function which draws it for you, so there is to deal with linear algebra to solve linear equation-systems - brrr! - I've done that without real understanding. For that:

## Credits

to Marco Roello.

My exercises on CubicSplines base on his article.

## Implementation-details

The project deals with several ownerdraw-requirements:
move- and highlight-able points, polygons, bezier-splines, cubic-splines, and a caption

I collected them into a little hierarchy of classes:

```               ControlCaption
/
DrawObjectBase --DrawPoint
\
\         BezierSpline
\       /
Polygon
\
CubicSpline
```

You see: programmically I consider a spline as a polygon with different way to draw and interpolate the line between two support-points. And if there are only two support-points - they actually display the same straight line.

## History

30/12/2007: submit article, sample-solution in VB2008 prof, beta

Germany
No Biography provided

 First Prev Next
 My vote of 5 manoj kumar choubey 20-Feb-12 2:38
 My vote of 5 Jerome Vibert 9-Feb-12 10:36
 123 konikula 6-Jan-10 22:19
 Re: 123 [modified] konikula 6-Jan-10 22:52
 Open in VS2005? jronecube 4-Jan-08 3:04
 Re: Open in VS2005? Mr.PoorEnglish 4-Jan-08 12:44
 Distance along the curve? Member 593808 3-Jan-08 4:41
 Re: Distance along the curve? henk21cm 7-Jan-08 11:11
 The Bezier curve is defined by two equation:   x(t) = a_x*t^3 + b_x*t^2 + c_x*t + x_0 y(t) = a_y*t^3 + b_y*t^2 + c_y*t + y_0   The coefficients a_x .. c_x and a_y .. c_y can be found from the 4 points which frame (define) the curve:   x_1 = x_0 + c_x/3 x_2 = x_1 + (c_x+b_x)/3 x_3 = x_0 + c_x + b_x + a_x   The same relations for the y flavour of the points and coefficients.   Now some simple math:   If t == 0: x(t=0) = x_0 if t == 1: x(t=1) = x_3   To calculate the distance along the Bezier curve,   1) divide your t in small steps, e.g. 0.001 (for t=0; t<=1; t+=0.001) and calculate the accompanying x(t) and y(t) values. 1001 X and Y values.   2) calculate the differences between adjacent points, in both X and Y: This gives you a set of 1000 values DX and DY. DX(i) = X(i+1) - X(i)   3) Take the square of these differences DX and DY and then the square root of these. This provide you with 1000 DS values: DS = sqrt(DX*DX + DY*DY)   4) Sum all DS values. This is a fair approximation of the length of the curve.   There is a better analytical solution of this question, but i doubt whether the integral involved can be solved analytically. Then it forves you to a numerical solution for the integral, which is nice as well, but the brute force solution is easier.   21 cm: the universal wavelength of hydrogen
 Re: Distance along the curve? Mr.PoorEnglish 24-Jan-08 6:49
 Re: Distance along the curve? henk21cm 25-Jan-08 22:50
 Re: Distance along the curve? petert1401 12-Mar-08 1:43
 Re: Distance along the curve? henk21cm 24-Mar-08 4:45
 Re: Distance along the curve? petert1401 24-Mar-08 21:10
 the "inventors of the wheel"... Mr.PoorEnglish 25-Mar-08 0:01
 Here is teh Spline 3D Code tridex 2-Jan-08 0:27
 Fantastic [modified] tridex 2-Jan-08 0:11
 Last Visit: 31-Dec-99 18:00     Last Update: 22-Jul-14 19:02 Refresh 1