Graphic Algorithms

Line Generating Algorithms

//Line Generating Algorithm
//Digital Differential Analyzer

void line(int x1, int y1, int x2, int y2)
{
const double dx = x1 - x2;
const double dy = y1 - y2;
   if (dy == 0)
      for (int x=MIN(x1,x2); x<=MAX(x1,x2); ++x)
         putpixel(x, y1, getcolor());
   else if (dx == 0)
      for (int y=MIN(y1,y2); y<=MAX(y1,y2); ++y)
         putpixel(x1, y, getcolor());
   else
   {
   const double m = dy / dx;
   const double b = y1 - m * x1;
      if (fabs(dy) <= fabs(dx))
         for (int x=MIN(x1,x2); x<=MAX(x1,x2); ++x)
            putpixel(x, ROUND(m*x+b), getcolor());
      else
         for (int y=MIN(y1,y2); y<=MAX(y1,y2); ++y)
            putpixel(ROUND((y-b)/m), y, getcolor());
   }
}

//Line Generating Algorithm
//Bresenham's

void line(int x1, int y1, int x2, int y2)
{
const int dx = abs(x1 - x2);
const int dy = abs(y1 - y2);
int const1, const2, p, x, y, step;
   if (dx >= dy)
   {
   const1 = 2 * dy;
   const2 = 2 * (dy - dx);
      p = 2 * dy - dx;
      x = MIN(x1,x2);
      y = (x1 < x2) ? (y1) : (y2);
      step = (y1 > y2) ? (1) : (-1);
      putpixel(x, y, getcolor());
      while (x < MAX(x1,x2))
      {
         if (p < 0)
            p += const1;
         else
         {
            y += step;
            p += const2;
         }
         putpixel(++x, y, getcolor());
      }
   }
   else
   {
   const1 = 2 * dx;
   const2 = 2 * (dx - dy);
      p = 2 * dx - dy;
      y = MIN(y1,y2);
      x = (y1 < y2) ? (x1) : (x2);
      step = (x1 > x2) ? (1) : (-1);
      putpixel(x, y, getcolor());
      while (y < MAX(y1,y2))
      {
         if (p < 0)
            p += const1;
         else
         {
            x += step;
            p += const2;
         }
         putpixel(x, ++y, getcolor());
      }
   }
}

Circle Generating Algorithms

//Circle Generating Algorithm
//Simple Cartesian-Coordinate

void circle(int xc, int yc, int r)
{
double SQRT;
   for (int x=0; x<=(SQRT=sqrt(SQR(r)-SQR(x))); ++x)
   {
      putpixel(ROUND(xc + SQRT), yc + x, getcolor());
      putpixel(ROUND(xc + SQRT), yc - x, getcolor());
      putpixel(ROUND(xc - SQRT), yc + x, getcolor());
      putpixel(ROUND(xc - SQRT), yc - x, getcolor());
      putpixel(xc + x, ROUND(yc + SQRT), getcolor());
      putpixel(xc - x, ROUND(yc + SQRT), getcolor());
      putpixel(xc + x, ROUND(yc - SQRT), getcolor());
      putpixel(xc - x, ROUND(yc - SQRT), getcolor());
   }
}

//Circle Generating Algorithm
//Simple Polar-Coordinate

void circle(int xc, int yc, int r)
{
const double arc_size = PI / 4;
const int iterations = int(arc_size * r);
double RxCOS, RxSIN;
   for (int i=0; i<=iterations; ++i)
   {
      RxCOS = r * cos(arc_size*i/iterations);
      RxSIN = r * sin(arc_size*i/iterations);
      putpixel(ROUND(xc + RxCOS), ROUND(yc + RxSIN), getcolor());
      putpixel(ROUND(xc + RxCOS), ROUND(yc - RxSIN), getcolor());
      putpixel(ROUND(xc - RxCOS), ROUND(yc + RxSIN), getcolor());
      putpixel(ROUND(xc - RxCOS), ROUND(yc - RxSIN), getcolor());
      putpixel(ROUND(xc + RxSIN), ROUND(yc + RxCOS), getcolor());
      putpixel(ROUND(xc - RxSIN), ROUND(yc + RxCOS), getcolor());
      putpixel(ROUND(xc + RxSIN), ROUND(yc - RxCOS), getcolor());
      putpixel(ROUND(xc - RxSIN), ROUND(yc - RxCOS), getcolor());
   }
}

//Circle Generating Algorithm
//Bresenham's

void circle(int xc, int yc, int r)
{
int x = 0;
int y = r;
int p = 3 - 2 * r;
   while (x <= y)
   {
      putpixel(xc + x, yc + y, getcolor());
      putpixel(xc - x, yc + y, getcolor());
      putpixel(xc + x, yc - y, getcolor());
      putpixel(xc - x, yc - y, getcolor());
      putpixel(xc + y, yc + x, getcolor());
      putpixel(xc - y, yc + x, getcolor());
      putpixel(xc + y, yc - x, getcolor());
      putpixel(xc - y, yc - x, getcolor());
      if (p < 0)
         p += 4 * x++ + 6;
      else
         p += 4 * (x++ - y--) + 10;
   }
}

Ellipse Generating Algorithms

//Ellipse Generating Algorithm
//Simple Cartesian-Coordinate

void ellipse(int xc, int yc, int xr, int yr)
{
int len;
   if (xr > yr)
   {
   int y12, y22;
   int y11 = yc, y21 = yc;
      for (int x=xc-xr+1; x<=xc+xr; ++x)
      {
         len = yr * sqrt(1 - SQR((x - xc) / double(xr)));
         y12 = yc + len;
         y22 = yc - len;
         line(x-1, y11, x, y12);
         line(x-1, y21, x, y22);
         y11 = y12;
         y21 = y22;
      }
   }
   else
   {
   int x12, x22;
   int x11 = xc, x21 = xc;
      for (int y=yc-yr+1; y<=yc+yr; ++y)
      {
         len = xr * sqrt(1 - SQR((y - yc) / double(yr)));
         x12 = xc + len;
         x22 = xc - len;
         line(x11, y-1, x12, y);
         line(x21, y-1, x22, y);
         x11 = x12;
         x21 = x22;
      }
   }
}

//Ellipse Generating Algorithm
//Simple Polar-Coordinate

void ellipse(int xc, int yc, int xr, int yr)
{
const int ITERATIONS = 1000;
double theta;
   moveto(xc + xr, yc);
   for (int i=1; i<=ITERATIONS; ++i)
   {
      theta = 2 * PI * i / ITERATIONS;
      lineto(ROUND(xc+xr*cos(theta)), ROUND(yc+yr*sin(theta)));
   }
}

Fill Algorithms

//Boundary Fill Algorithm
void boundaryFill(int x, int y, int border)
{
#define IS_IN_X_RANGE(x) (((x) >= 0) && ((x) <= getmaxx()))
#define IS_IN_Y_RANGE(y) (((y) >= 0) && ((y) <= getmaxy()))
   if (IS_IN_X_RANGE(x) && IS_IN_Y_RANGE(y) &&
      (getpixel(x,y) != border) && (getpixel(x,y) != getcolor()))
   {
      putpixel(x, y, getcolor());
      boundaryFill(x+1, y, border);
      boundaryFill(x-1, y, border);
      boundaryFill(x, y+1, border);
      boundaryFill(x, y-1, border);
   }
#undef IS_IN_X_RANGE
#undef IS_IN_Y_RANGE
}

//Note: the 4-connected approach is implemented rather
//than the 8-connected approach.

//Flood Fill Algorithm
void floodFill(int x, int y, int old_color)
{
#define IS_IN_X_RANGE(x) (((x) >= 0) && ((x) <= getmaxx()))
#define IS_IN_Y_RANGE(y) (((y) >= 0) && ((y) <= getmaxy()))
   if (IS_IN_X_RANGE(x) && IS_IN_Y_RANGE(y) &&
       getpixel(x,y) == old_color)
   {
      putpixel(x, y, getcolor());
      floodFill(x+1, y, old_color);
      floodFill(x-1, y, old_color);
      floodFill(x, y+1, old_color);
      floodFill(x, y-1, old_color);
   }
#undef IS_IN_X_RANGE
#undef IS_IN_Y_RANGE
}
//Note: the 4-connected approach is implemented rather
//than the 8-connected approach.

Scan-Line Fill Algorithms

//Scan-Line Rectangle Fill Algorithm
void rectangleFill(int x1, int y1, int x2, int y2)
{
   for (int y=MIN(y1,y2); y<=MAX(y1,y2); ++y)
      line(x1, y, x2, y);
}

//Scan-Line Circle Fill Algorithm
//Utilizing Cartesian-Coordinate

void circleFill(int xc, int yc, int r)
{
int x1, x2;
   for (int y=yc-r; y<=yc+r; ++y)
   {
      x1 = ROUND(xc + sqrt(SQR(r) - SQR(y - yc)));
      x2 = ROUND(xc - sqrt(SQR(r) - SQR(y - yc)));
      line(x1, y, x2, y);
   }
}

//Scan-Line Circle Fill Algorithm
//Utilizing Polar-Coordinate

void circleFill(int xc, int yc, int r)
{
const int ITERATIONS = 2 * PI * r;
double theta;
int x, y;
   for (int i=0; i<=ITERATIONS; ++i)
   {
      theta = 2 * PI * i / ITERATIONS;
      x = ROUND(xc + r * cos(theta));
      y = ROUND(yc + r * sin(theta));
      line(xc, yc, x, y);
   }
}

Line Clipping Algorithms

//Line Clipping Algorithm
//Sutherland-Cohen

int ABRL(int x, int y)
{
int code = 0;
   if (x < XS_MIN)
      code = 1;
   else if (x > XS_MAX)
      code = 2;
   if (y < YS_MIN)
      code |= 4;
   else if (y > YS_MAX)
      code |= 8;
   return code;
}

void intersection(int& x1, int& y1, int x2, int y2)
{
   if (y1 > YS_MAX)
   {
      x1 += (x2 - x1) * (YS_MAX - y1) / (y2 - y1);
      y1 = YS_MAX;
   }
   else if (y1 < YS_MIN)
   {
      x1 += (x2 - x1) * (YS_MIN - y1) / (y2 - y1);
      y1 = YS_MIN;
   }
   if (x1 > XS_MAX)
   {
      y1 += (y2 - y1) * (XS_MAX - x1) / (x2 - x1);
      x1 = XS_MAX;
   }
   else if (x1 < XS_MIN)
   {
      y1 += (y2 - y1) * (XS_MIN - x1) / (x2 - x1);
      x1 = XS_MIN;
   }
}

void clipping(int& x1, int& y1, int& x2, int& y2)
{
   intersection(x1, y1, x2, y2);
   intersection(x2, y2, x1, y1);
}

void drawClippedLine(int x1, int y1, int x2, int y2)
{
   if (ABRL(x1, y1) == 0 && ABRL(x2, y2) == 0)
      line(x1, y1, x2, y2);
   else if (ABRL(x1, y1) && ABRL(x2, y2) != 0)
      return;
   else
   {
      clipping(x1, y1, x2, y2);
      if (ABRL(x1, y1) == 0 && ABRL(x2, y2) == 0)
         line(x1, y1, x2, y2);
   }
}

//Line Clipping Algorithm
//Midpoint
int ABRL(int x, int y)
{
int code = 0;
   if (x < XS_MIN)
      code = 1;
   else if (x > XS_MAX)
      code = 2;
   if (y < YS_MIN)
      code |= 4;
   else if (y > YS_MAX)
      code |= 8;
   return code;
}

void intersection(int& x1, int& y1, int x2, int y2)
{
int xm, ym;
   if (y1 > YS_MAX)
   {
      while (y1 != YS_MAX)
      {
         xm = (x1 + x2) >> 1;
         ym = (y1 + y2) >> 1;
         if (ym >= YS_MAX)
            x1 = xm, y1 = ym;
         else
            x2 = xm, y2 = ym;
      }
   }
   else if (y1 < YS_MIN)
   {
      while (y1 != YS_MIN)
      {
         xm = (x1 + x2) >> 1;
         ym = (y1 + y2) >> 1;
         if (ym <= YS_MIN)
            x1 = xm, y1 = ym;
         else
            x2 = xm, y2 = ym;
      }
   }
   if (x1 > XS_MAX)
   {
      while (x1 != XS_MAX)
      {
         xm = (x1 + x2) >> 1;
         ym = (y1 + y2) >> 1;
         if (xm >= XS_MAX)
            x1 = xm, y1 = ym;
         else
         x2 = xm, y2 = ym;
      }
   }
   else if (x1 < XS_MIN)
   {
      while (x1 != XS_MIN)
      {
         xm = (x1 + x2) >> 1;
         ym = (y1 + y2) >> 1;
         if (xm <= XS_MIN)
            x1 = xm, y1 = ym;
         else
            x2 = xm, y2 = ym;
      }
   }
}

void clipping(int& x1, int& y1, int& x2, int& y2)
{
   intersection(x1, y1, x2, y2);
   intersection(x2, y2, x1, y1);
}

void drawClippedLine(int x1, int y1, int x2, int y2)
{
   if (ABRL(x1, y1) == 0 && ABRL(x2, y2) == 0)
      line(x1, y1, x2, y2);
   else if (ABRL(x1, y1) && ABRL(x2, y2) != 0)
      return;
   else
   {
      clipping(x1, y1, x2, y2);
      if (ABRL(x1, y1) == 0 && ABRL(x2, y2) == 0)
         line(x1, y1, x2, y2);
   }
}

//Line Clipping Algorithm
//Liang-Barsky

int clipTest(int p, int q, double& u1, double& u2)
{
double r;
   if (p < 0)
   {
      r = q / p;
      if (r > u2)
         return 0;
      else if (r > u1)
         u1 = r;
   }
   else if (p > 0)
   {
      r = q / p;
      if (r < u1)
         return 0;
      else if (r < u2)
         u2 = r;
   }
   else if (q < 0)
      return 0;
   return 1;
}

void clipping(int& x1, int& y1, int& x2, int& y2)
{
const int dx = x2 - x1;
const int dy = y2 - y1;
double u1 = 0;
double u2 = 1;
   if ((clipTest(-dx, x1-XS_MIN, u1, u2)) &&
       (clipTest( dx, XS_MAX-x1, u1, u2)) &&
       (clipTest(-dy, y1-YS_MIN, u1, u2)) &&
       (clipTest( dy, YS_MAX-y1, u1, u2)))
   {
      if (u2 < 1)
         x2 = x1 + ROUND(u2 * dx),
         y2 = y1 + ROUND(u2 * dy);
      if (u1 > 0)
         x1 += ROUND(u1 * dx),
         y1 += ROUND(u1 * dy);
   }
}

Curve Generating Algorithm

//Curve Generating Algorithm
//Bezier-Spline

long C(int n, int k)
{
   return k != 0 && n != k ? C(n-1, k-1) + C(n-1, k) : 1;
}

double power(double x, double y)
{
   return x == 0 && y == 0 ? 1 : pow(x, y);
}

double BEZ(int k, int n, double u)
{
   return C(n, k) * power(u, k) * power(1-u, n-k);
}

void bezierCurve(int n, pointType* point)
{
double u, x, y;
   for (int i=0; i<=ITERATIONS; ++i)
   {
      u = double(i) / ITERATIONS;
      x = y = 0;
      for (int k=0; k<=n; ++k)
      {
      double BEZvalue = BEZ(k, n, u);
         x += point[k].x * BEZvalue;
         y += point[k].y * BEZvalue;
      }
      if (i == 0)
         moveto(x, y);
      lineto(x, y);
   }
}