BSc / MSc / BTech / BE / MCA - C / C++ Computer Graphics Lab Programs Source Code: Curve fitting algorithm

Bézier curves can be defined for any degree n. A recursive definition for the Bézier curve of degree n expresses it as a point-to-point linear combination (linear interpolation) of a pair of corresponding points in two Bézier curves of degree n − 1.

Let $\mathbf{B}_{\mathbf{P}_0\mathbf{P}_1\ldots\mathbf{P}_n}$ denote the Bézier curve determined by any selection of points P₀, P₁, ..., P_n. Then to start,

$\mathbf{B}_{\mathbf{P}_0}(t) = \mathbf{P}_0 \text{, and}$

$\mathbf{B}(t) = \mathbf{B}_{\mathbf{P}_0\mathbf{P}_1\ldots\mathbf{P}_n}(t) = (1-t)\mathbf{B}_{\mathbf{P}_0\mathbf{P}_1\ldots\mathbf{P}_{n-1}}(t) + t\mathbf{B}_{\mathbf{P}_1\mathbf{P}_2\ldots\mathbf{P}_n}(t)$

The formula can be expressed explicitly as follows:

$\begin{align} \mathbf{B}(t) = {} &\sum_{i=0}^n {n\choose i}(1 - t)^{n - i}t^i\mathbf{P}_i \\ = {} &(1 - t)^n\mathbf{P}_0 + {n\choose 1}(1 - t)^{n - 1}t\mathbf{P}_1 + \cdots \\ {} &\cdots + {n\choose n - 1}(1 - t)t^{n - 1}\mathbf{P}_{n - 1} + t^n\mathbf{P}_n,\quad t \in [0,1]\end{align}$

where $\scriptstyle {n \choose i}$ are the binomial coefficients.
For example, for n = 5:

$\begin{align} \mathbf{B}_{\mathbf{P}_0\mathbf{P}_1\mathbf{P}_2\mathbf{P}_3\mathbf{P}_4\mathbf{P}_5}(t) = \mathbf{B}(t) = {} & (1 - t)^5\mathbf{P}_0 + 5t(1 - t)^4\mathbf{P}_1 + 10t^2(1 - t)^3 \mathbf{P}_2 \\ {} & + 10t^3 (1-t)^2 \mathbf{P}_3 + 5t^4(1-t) \mathbf{P}_4 + t^5 \mathbf{P}_5,\quad t \in [0,1] \end{align}$

Program to Create Bezier curve

This program use only simple array operations to compute polynomial coefficients.
Can be done using factorial too .

#include <stdio.h>
#include <graphics.h>
#include <math.h>
void bezier (int x1[], int y1[], int no_ctrlpt)
{
   int i,j,row,col;
   double t,xt=0,yt=0; // xt , yt - points to plot curve
   int pcoeff[20][20]; // used to save the coefficents of the polynomial
                                 // created using pascal triangle
// code to find the coefficient of the polynomial
   for(i=0;i<no_ctrlpt;i++)   // no_ctrlpt - number of control points .
                                         // one point is a set of x, y coordinate
   {
       for(j=0;j<=i;j++)
       {
       if(j==0||i==j)
       {
       pcoeff[i][j]=1;
       }
       else
       {
       pcoeff[i][j]=pcoeff[i-1][j-1]+pcoeff[i-1][j];
       }
       }

   }
// code to compute the blend and to fit the curve
        for (t = 0.0; t < 1.0; t += 0.005)

          {
          int k, n= no_ctrlpt-1;
          double blend, term1,term2;

          xt=0.0;
          yt=0.0;
          for(k=0;k<no_ctrlpt;k++)
          {
          if(k==0)   // check needed since if k=0 then pow (t,k) will return domain error
          term1=1; //since anything raise to zero is 1
          else
          term1=pow(t,k);
          term2=pow( 1-t, n-k);
          blend = (double)pcoeff[no_ctrlpt-1][k]*term1*term2; // no_ctrlpt - 1 need since
                                              //only last row of the generated pascal triangle is needed

          xt=xt+x1[k]*blend;
          yt=yt+y1[k]*blend;
          }

   putpixel ((int)xt,(int)yt, RED);
}
   for (i=0; i<no_ctrlpt; i++)
   putpixel (x1[i], y1[i], YELLOW);
   }

void main()
{
   int gd = DETECT, gm;
   int x[20], y[20]; // used to store x, y coordinate system
   int i,n;
   initgraph (&gd, &gm, "..\\bgi");
   setbkcolor(BLUE);
   printf("Enter the number of control points");
   scanf("%d",&n);
   printf ("Enter the x- and y-coordinates of the control points.\n");
   for (i=0; i<n; i++)
   scanf ("%d%d", &x[i], &y[i]);
   bezier (x, y,n);    // calling function to fit the curve
   getch();
   closegraph();
}

The above program modified to draw the x and y axis and to draw the Bézier curve is listed below :

#include <stdio.h>
#include <graphics.h>
#include <math.h>
void bezier (int x1[], int y1[], int no_ctrlpt)
{
   int i,j,row,col;
   double t,xt=0,yt=0;
   int pcoeff[20][20];

    for(i=0;i<no_ctrlpt;i++)
    {
        for(j=0;j<=i;j++)
        {
        if(j==0||i==j)
        {
        pcoeff[i][j]=1;
        }
        else
        {
        pcoeff[i][j]=pcoeff[i-1][j-1]+pcoeff[i-1][j];
        }
        }

    }

        for (t = 0.0; t < 1.0; t += 0.005)

          {
          int k, n= no_ctrlpt-1;
          double blend, term1,term2;

          xt=0.0;
          yt=0.0;
          for(k=0;k<no_ctrlpt;k++)
          {
          if(k==0)
          term1=1; //since anything raise to zero is 1
          else
          term1=pow(t,k);
          term2=pow( 1-t, n-k);
          blend = (double)pcoeff[no_ctrlpt-1][k]*term1*term2;
          xt=xt+x1[k]*blend;
          yt=yt+y1[k]*blend;
          }

    putpixel ((int)xt,(int)yt, RED);
}
    for (i=0; i<no_ctrlpt; i++)
    putpixel (x1[i], y1[i], YELLOW);
   }

void main()
{
   int gd = DETECT, gm;
   int x[20], y[20],gap=50;
   char str[5];
   int i,n;
   initgraph (&gd, &gm, "..\\bgi");
   setbkcolor(BLUE);
   line(5,getmaxy()-10,getmaxx()-5,getmaxy()-10);
   line(3,8,3,getmaxy()-8);

   for( i= gap;i<getmaxx();i=i+gap)    // gap required for spacing of co-ordinate values
   {
   outtextxy(i,getmaxy()-14,"|");
   itoa(i,str,10);
   outtextxy(i,getmaxy()-8,str);
   }
   for( i=gap;i<getmaxy();i=i+gap)
   {
   outtextxy(1,getmaxy()-i,"-");
   itoa(i,str,10);
   outtextxy(8,getmaxy()-i,str);
   }

   printf("Enter the number of control points");
   scanf("%d",&n);
   printf ("Enter the x- and y-coordinates of the four control points.\n");
   printf(" eg: if 3 control point then enter 50 50 100 100 150 50 \n");
   for (i=0; i<n; i++)
   {
   scanf ("%d%d", &x[i], &y[i]);
   y[i]= getmaxy()-y[i]; // this step required for shifting (0,0) position from top left to bottom left
   }
   bezier (x, y,n);
   getch();
   closegraph();
}

Sample Input :
           if 3 control points : 200 200 250 150 300 200
         if 4 control points : 200 200 250 150 300 200 350 250

BSc / MSc / BTech / BE / MCA - C / C++ Computer Graphics Lab Programs Source Code

Saturday, December 14, 2013

Bézier curve fitting program