Click here to Skip to main content
13,551,308 members
Click here to Skip to main content
Add your own
alternative version


83 bookmarked
Posted 29 Aug 2008
Licenced CPOL

Curve Fitting using Lagrange Interpolation

, 12 Sep 2008
Rate this:
Please Sign up or sign in to vote.
Fitting a set of points P to a curve using Lagrange Interpolation Polynomial.


In this article, I will explain curve fitting using the Lagrange interpolation polynomial. Curve fitting is used in a wide spectrum in engineering applications such as cars and air crafts surface design. The main problem is, given a set of points in the plan, we want to fit them in a smooth curve that passes through these points. The order of the curve f(x) depends on the number of points given. For example, if we have two points, the function will be of the first order, and the curve will be the line that passes through these two points, while if you have three points, the function will be of the second order f(x) = x2 . Let's first explain the Lagrange polynomial, then we will proceed to the algorithm and the implementation. In this article, I am using C# for coding.


Lagrange Polynomial

An interpolation on two points, (x0, y0) and (x1, y1), results in a linear equation or a straight line. The standard form of a linear equation is given by y = mx + c, where m is the gradient of the line and c is the y-intercept.

m = y1 − y0 / x1 − x0
c = y0 − mx0

which results in:

y = (y1 − y0 / x1 − x0) * x + (x1 y0 − x0 y1 )/ (x1 − x0)

The linear equation is rewritten so that the two interpolated points, (x0, y0) and (x1, y1), are directly represented.

With this in mind, the linear equation is rewritten as:

P1(x) = a0(x − x1) + a1(x − x0)

where a0 and a1 are constants . The points x0 and x1 in the factors of the above equation are called the centers. Applying the equation at (x0, y0), we obtain:

y0 = a0(x0 − x1) + a1(x0 − x0)


a0 = y0/ x0−x1 

At (x1, y1), we get:

y1 = a0(x1 − x1) + a1(x1 − x0), or a1 = y1/ x1−x0

Therefore, the linear equation becomes:

P1(x) = y0 (x− x1) /(x0 − x1) + y1 (x− x0) / (x1 − x0)

The quadratic form of the Lagrange polynomial interpolates three points, (x0, y0), (x1, y1), and (x2, y2). The polynomial has the form:

P2(x) = a0(x− x1)(x− x2) + a1(x− x0) (x− x2) + a2(x− x0)(x− x1)

with centers at x0, x1, and x2. At (x0, y0):

y0 = a0(x0 − x1)(x0 − x2) + a1(x0 − x0)(x0 − x2) + a2(x0 − x0)(x0 − x1),


a0 = y0/ (x0 − x1)(x0 − x2)
a1 = y1 / (x1 − x0)(x1 − x2)
a2 = y2/ (x2 − x0)(x2 − x1)
P2(x) = y0 (x− x1)(x− x2) / (x0 − x1)(x0 − x2) + y1 (x − x0)(x − x2)/ 
       (x1 − x0)(x1 − x2) + y2 (x− x0)(x− x1)/ (x2 − x0)(x2 − x1)

In general, a Lagrange polynomial of degree n is a polynomial that is produced from an interpolation over a set of points, (xi , yi ) for i = 0, 1, . . ., n, as follows:

Pn(x) = y0L0(x) + y1L1(x) + ··· + ynLn(x)

Using the Code

The Algorithm

Given the interpolating points (xi , yi ) for i =0, 1, . . . ,n;

for i = 0 to n
  //the cumulative multiplication from k = 1 (and k not equal i) to n 
  Evaluate Li (x) = ∏nk=1,k != i (x−xk ) / (xi−xk ) ;

Evaluate Pn(x) = y0L0(x) + y1L1(x) + ··· + ynLn(x);

Download the source code from the top of this page to view the code.

Points of Interest

Numerical computing is a very interesting field in software development. This article is related to that field ... And, I will post more articles soon about Computational Geometry ...such as Convex Hull algorithm and Triangulation.


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


About the Author

Fady Aladdin
Software Developer
Egypt Egypt
No Biography provided

You may also be interested in...


Comments and Discussions

GeneralA compact version Pin
gustavtr20-Feb-12 11:24
membergustavtr20-Feb-12 11:24 
GeneralRe: A compact version Pin
Member 1194359329-Aug-15 9:18
memberMember 1194359329-Aug-15 9:18 
GeneralMy vote of 5 Pin
MarkDaniel5-Jan-12 12:21
memberMarkDaniel5-Jan-12 12:21 
Questionhow to get all pixels coordinate from curve fitting using Lagrange interpolationan on an image Pin
MrKyaw24-Oct-11 16:18
memberMrKyaw24-Oct-11 16:18 
GeneralRadius of curve Pin
M i s t e r L i s t e r25-Aug-10 9:48
memberM i s t e r L i s t e r25-Aug-10 9:48 
Generalneed help plz Pin
d_e_e_o6-Aug-10 4:33
memberd_e_e_o6-Aug-10 4:33 
GeneralCorrected an Overflow error Pin
SBGTrading22-Jul-10 5:05
memberSBGTrading22-Jul-10 5:05 
GeneralContact Pin
icae27-Apr-09 5:42
membericae27-Apr-09 5:42 
GeneralRe: Contact Pin
Fady Aladdin27-Apr-09 7:19
memberFady Aladdin27-Apr-09 7:19 
GeneralArea under the curve Pin
Dorisvaldo16-Sep-08 15:06
memberDorisvaldo16-Sep-08 15:06 
Generalpiecewise bezier Pin
Sarath.14-Sep-08 21:54
memberSarath.14-Sep-08 21:54 
GeneralRe: piecewise bezier Pin
catbertfromgilead15-Sep-08 9:31
membercatbertfromgilead15-Sep-08 9:31 
GeneralI don't mean to quibble but this looks like interpolation Pin
MicroImaging11-Sep-08 11:15
memberMicroImaging11-Sep-08 11:15 
GeneralRe: I don't mean to quibble but this looks like interpolation Pin
axelriet12-Sep-08 5:30
memberaxelriet12-Sep-08 5:30 
GeneralRe: I don't mean to quibble but this looks like interpolation Pin
MicroImaging12-Sep-08 9:20
memberMicroImaging12-Sep-08 9:20 
GeneralAwesome! Just what I've been looking for! Pin
dybs6-Sep-08 7:42
memberdybs6-Sep-08 7:42 
GeneralRe: Awesome! Just what I've been looking for! Pin
Fady Aladdin11-Sep-08 2:36
memberFady Aladdin11-Sep-08 2:36 
GeneralRe: Awesome! Just what I've been looking for! Pin
dybs11-Sep-08 6:32
memberdybs11-Sep-08 6:32 
GeneralRe: Awesome! Just what I've been looking for! Pin
axelriet12-Sep-08 5:26
memberaxelriet12-Sep-08 5:26 
GeneralComputational Geometry Pin
abombardier2-Sep-08 14:37
memberabombardier2-Sep-08 14:37 
GeneralRe: Computational Geometry Pin
axelriet12-Sep-08 5:10
memberaxelriet12-Sep-08 5:10 
GeneralRe: Computational Geometry Pin
abombardier12-Sep-08 9:26
memberabombardier12-Sep-08 9:26 
Generalgetting back values Pin
KJJ22-Sep-08 10:21
memberKJJ22-Sep-08 10:21 

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

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

Permalink | Advertise | Privacy | Terms of Use | Mobile
Web04-2016 | 2.8.180515.1 | Last Updated 12 Sep 2008
Article Copyright 2008 by Fady Aladdin
Everything else Copyright © CodeProject, 1999-2018
Layout: fixed | fluid