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);
}
}
