Click here to Skip to main content
11,645,087 members (64,785 online)
Click here to Skip to main content

Interpolation of BezierSplines and Cubic Splines

, 5 Jan 2008 CPOL 53.7K 1.8K 55
Rate this:
Please Sign up or sign in to vote.
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?

What I'm talking about

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

1/5/08: VB2005-version to zip-file added

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

Mr.PoorEnglish
Germany Germany
No Biography provided

You may also be interested in...

Comments and Discussions

 
Suggestioncan you help me?Write your code in C# Pin
ambitionlike18-Aug-14 22:37
memberambitionlike18-Aug-14 22:37 
GeneralMy vote of 5 Pin
manoj kumar choubey20-Feb-12 2:38
membermanoj kumar choubey20-Feb-12 2:38 
GeneralMy vote of 5 Pin
Jerome Vibert9-Feb-12 10:36
memberJerome Vibert9-Feb-12 10:36 
General123 Pin
konikula6-Jan-10 22:19
memberkonikula6-Jan-10 22:19 
GeneralRe: 123 [modified] Pin
konikula6-Jan-10 22:52
memberkonikula6-Jan-10 22:52 
BTW: there is some system error with your demo. If you make two support points and doubleclick the form to maximize, and doubleclick to minimize it falls unhandled excp. But beautiful sample.

Although I have some problems with this article (I'm pretty poor mathematician), at least playing with your demo is good way to understand (compared to this article, for me) difference between spline and cubic curve. jFYI I had for example big problem to catch the train in BinarySearch article section (just starting), because I don't initially know what are points searched thru for, and why do you search bezier section, it's, for poor-nonmathers just, pretty shortcircuited starting of article, or like yanked from context. I'll give it try with looking in code attached. (Article is informative enough although, but there are some problems with people like me and some sections of article Sigh | :sigh: )

Later: Um, this seem of yanking of context is caused by not notifiing reader that "Bezier general info" section is ended, and repeating for this stupid reader, that you're going to compute some distinct point of bezier from known X. Suspicious | :suss:

Even more later (or laterer for PoorEnglish): OIC, again. You should write better intro, and rethink section names. For example I noticed, that you actually drawn bezier using DrawCurve, and that you are just going to show, how to calculate distinct point on it in this article, somewhere in the middle of article. If this would started this article, with some changes to #captions, it would be as easy to understand, as your more recent articles are. Please forgive me such extensive revision, I actually think that also this article is very good. D'Oh! | :doh:

Even laterer than latest laterer: To not just cast as stupid myself here, I've just noticed, that your demo is limited for X-Y bezier layout (I mean, it can't draw vertical bezier (combined at result), nor compute point for two support points of same X). Maybe it would be helpful to think if there is something interesting for others, if you'd tried to make both computations and drawings possible? I don't know, maybe it will just blur whole article and code, but you will know better if this remark has some value. Cool | :cool:

Finally: OIC Smile | :) //"They are mathematically undefined only if two support-points set on the same X-position (as vertical line)."

P.S.: also code is pretty beautiful. so just try to reconsider my previous remarks on your own, and make your conclusion if there is something to repair in app or update in article. all my previous words here except those two 'beautiful' ratings, those on complicated orientation in article, and system bug with resizing can be just mismatch, because they were written in the middle of reading.

modified on Thursday, January 7, 2010 5:20 AM

QuestionOpen in VS2005? Pin
jronecube4-Jan-08 3:04
memberjronecube4-Jan-08 3:04 
AnswerRe: Open in VS2005? Pin
Mr.PoorEnglish4-Jan-08 12:44
memberMr.PoorEnglish4-Jan-08 12:44 
QuestionDistance along the curve? Pin
Member 5938083-Jan-08 4:41
memberMember 5938083-Jan-08 4:41 
AnswerRe: Distance along the curve? Pin
henk21cm7-Jan-08 11:11
memberhenk21cm7-Jan-08 11:11 
GeneralRe: Distance along the curve? Pin
Mr.PoorEnglish24-Jan-08 6:49
memberMr.PoorEnglish24-Jan-08 6:49 
GeneralRe: Distance along the curve? Pin
henk21cm25-Jan-08 22:50
memberhenk21cm25-Jan-08 22:50 
GeneralRe: Distance along the curve? Pin
petert140112-Mar-08 1:43
memberpetert140112-Mar-08 1:43 
GeneralRe: Distance along the curve? Pin
henk21cm24-Mar-08 4:45
memberhenk21cm24-Mar-08 4:45 
GeneralRe: Distance along the curve? Pin
petert140124-Mar-08 21:10
memberpetert140124-Mar-08 21:10 
Jokethe "inventors of the wheel"... Pin
Mr.PoorEnglish25-Mar-08 0:01
memberMr.PoorEnglish25-Mar-08 0:01 
GeneralHere is teh Spline 3D Code Pin
tridex2-Jan-08 0:27
membertridex2-Jan-08 0:27 
QuestionFantastic [modified] Pin
tridex2-Jan-08 0:11
membertridex2-Jan-08 0:11 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Terms of Use | Mobile
Web01 | 2.8.150731.1 | Last Updated 5 Jan 2008
Article Copyright 2007 by Mr.PoorEnglish
Everything else Copyright © CodeProject, 1999-2015
Layout: fixed | fluid