Instantly share code, notes, and snippets.

Created July 15, 2011 21:01
Show Gist options
• Save bert/1085538 to your computer and use it in GitHub Desktop.
Bresenham Algorithms in C
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 Some possible implementations of the Bresenham Algorithms in C. The Bresenham line algorithm is an algorithm which determines which points in an n-dimensional raster should be plotted in order to form a close approximation to a straight line between two given points. It is commonly used to draw lines on a computer screen, as it uses only integer addition, subtraction and bit shifting, all of which are very cheap operations in standard computer architectures. It is one of the earliest algorithms developed in the field of computer graphics. A minor extension to the original algorithm also deals with drawing circles. While algorithms such as Wu's algorithm are also frequently used in modern computer graphics because they can support antialiasing, the speed and simplicity of Bresenham's line algorithm mean that it is still important. The algorithm is used in hardware such as plotters and in the graphics chips of modern graphics cards. It can also be found in many software graphics libraries. Because the algorithm is very simple, it is often implemented in either the firmware or the hardware of modern graphics cards. The label "Bresenham" is used today for a whole family of algorithms extending or modifying Bresenham's original algorithm. # EOF #
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 // 'cx' and 'cy' denote the offset of the circle centre from the origin. void circle (int cx, int cy, int radius) { int error = -radius; int x = radius; int y = 0; // The following while loop may altered to 'while (x > y)' for a // performance benefit, as long as a call to 'plot4points' follows // the body of the loop. This allows for the elimination of the // '(x != y') test in 'plot8points', providing a further benefit. // // For the sake of clarity, this is not shown here. while (x >= y) { plot8points (cx, cy, x, y); error += y; ++y; error += y; // The following test may be implemented in assembly language in // most machines by testing the carry flag after adding 'y' to // the value of 'error' in the previous step, since 'error' // nominally has a negative value. if (error >= 0) { --x; error -= x; error -= x; } } } void plot8points (int cx, int cy, int x, int y) { plot4points (cx, cy, x, y); if (x != y) plot4points (cx, cy, y, x); } // The '(x != 0 && y != 0)' test in the last line of this function // may be omitted for a performance benefit if the radius of the // circle is known to be non-zero. void plot4points (int cx, int cy, int x, int y) { setPixel (cx + x, cy + y); if (x != 0) setPixel (cx - x, cy + y); if (y != 0) setPixel (cx + x, cy - y); if (x != 0 && y != 0) setPixel (cx - x, cy - y); } /* EOF */
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 void plot_basic_bezier (int x0, int y0, int x1, int y1, int x2, int y2) { int sx = x0 < x2 ? 1 : -1; int sy = y0 < y2 ? 1 : -1; /* step direction */ int cur = sx * sy *((x0 - x1) * (y2 - y1) - (x2 - x1) * (y0 - y1)); /* curvature */ int x = x0 - 2 * x1 + x2, y = y0 - 2 * y1 +y2, xy = 2 * x * y * sx * sy; /* compute error increments of P0 */ long dx = (1 - 2 * abs (x0 - x1)) * y * y + abs (y0 - y1) * xy - 2 * cur * abs (y0 - y2); long dy = (1 - 2 * abs (y0 - y1)) * x * x + abs (x0 - x1) * xy + 2 * cur * abs (x0 - x2); /* compute error increments of P2 */ long ex = (1 - 2 * abs (x2 - x1)) * y * y + abs (y2 - y1) * xy + 2 * cur * abs (y0 - y2); long ey = (1 - 2 * abs (y2 - y1)) * x * x + abs (x2 - x1) * xy - 2 * cur * abs (x0 - x2); /* sign of gradient must not change */ assert ((x0 - x1) * (x2 - x1) <= 0 && (y0 - y1) * (y2 - y1) <= 0); if (cur == 0) { /* straight line */ plotLine (x0, y0, x2, y2); return; } x *= 2 * x; y *= 2 * y; if (cur < 0) { /* negated curvature */ x = -x; dx = -dx; ex = -ex; xy = -xy; y = -y; dy = -dy; ey = -ey; } /* algorithm fails for almost straight line, check error values */ if (dx >= -y || dy <= -x || ex <= -y || ey >= -x) { plotLine (x0, y0, x1, y1); /* simple approximation */ plotLine (x1, y1, x2, y2); return; } dx -= xy; ex = dx + dy; dy -= xy; /* error of 1.step */ for (;;) { /* plot curve */ setPixel (x0, y0); ey = 2 * ex - dy; /* save value for test of y step */ if (2 * ex >= dx) { /* x step */ if (x0 == x2) break; x0 += sx; dy -= xy; ex += dx += y; } if (ey <= 0) { /* y step */ if (y0 == y2) break; y0 += sy; dx -= xy; ex += dy += x; } } } /* EOF */
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 void plot_circle (int xm, int ym, int r) { int x = -r, y = 0, err = 2-2*r; /* II. Quadrant */ do { setPixel (xm-x, ym+y); /* I. Quadrant */ setPixel (xm-y, ym-x); /* II. Quadrant */ setPixel (xm+x, ym-y); /* III. Quadrant */ setPixel (xm+y, ym+x); /* IV. Quadrant */ r = err; if (r > x) err += ++x*2+1; /* e_xy+e_x > 0 */ if (r <= y) err += ++y*2+1; /* e_xy+e_y < 0 */ } while (x < 0); } /* EOF */
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 void plot_ellipse_rect (int x0, int y0, int x1, int y1) { int a = abs (x1 - x0), b = abs (y1 - y0), b1 = b & 1; /* values of diameter */ long dx = 4 * (1 - a) * b * b, dy = 4 * (b1 + 1) * a * a; /* error increment */ long err = dx + dy + b1 * a * a, e2; /* error of 1.step */ if (x0 > x1) { x0 = x1; x1 += a; } /* if called with swapped points */ if (y0 > y1) y0 = y1; /* .. exchange them */ y0 += (b + 1) / 2; y1 = y0-b1; /* starting pixel */ a *= 8 * a; b1 = 8 * b * b; do { setPixel (x1, y0); /* I. Quadrant */ setPixel (x0, y0); /* II. Quadrant */ setPixel (x0, y1); /* III. Quadrant */ setPixel (x1, y1); /* IV. Quadrant */ e2 = 2 * err; if (e2 >= dx) { x0++; x1--; err += dx += b1; } /* x step */ if (e2 <= dy) { y0++; y1--; err += dy += a; } /* y step */ } while (x0 <= x1); while (y0-y1 < b) { /* too early stop of flat ellipses a=1 */ setPixel (x0-1, y0); /* -> finish tip of ellipse */ setPixel (x1+1, y0++); setPixel (x0-1, y1); setPixel (x1+1, y1--); } } /* EOF */
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 void plot_line (int x0, int y0, int x1, int y1) { int dx = abs (x1 - x0), sx = x0 < x1 ? 1 : -1; int dy = -abs (y1 - y0), sy = y0 < y1 ? 1 : -1; int err = dx + dy, e2; /* error value e_xy */ for (;;){ /* loop */ setPixel (x0,y0); if (x0 == x1 && y0 == y1) break; e2 = 2 * err; if (e2 >= dy) { err += dy; x0 += sx; } /* e_xy+e_x > 0 */ if (e2 <= dx) { err += dx; y0 += sy; } /* e_xy+e_y < 0 */ } } /* EOF */
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 void raster_circle (int x0, int y0, int radius) { int f = 1 - radius; int ddF_x = 1; int ddF_y = -2 * radius; int x = 0; int y = radius; setPixel (x0, y0 + radius); setPixel (x0, y0 - radius); setPixel (x0 + radius, y0); setPixel (x0 - radius, y0); while (x < y) { // ddF_x == 2 * x + 1; // ddF_y == -2 * y; // f == x*x + y*y - radius*radius + 2*x - y + 1; if (f >= 0) { y--; ddF_y += 2; f += ddF_y; } x++; ddF_x += 2; f += ddF_x; setPixel (x0 + x, y0 + y); setPixel (x0 - x, y0 + y); setPixel (x0 + x, y0 - y); setPixel (x0 - x, y0 - y); setPixel (x0 + y, y0 + x); setPixel (x0 - y, y0 + x); setPixel (x0 + y, y0 - x); setPixel (x0 - y, y0 - x); } } /* EOF */
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 So. When we compare sum of N odd numbers to this algorithm we have. ddF_y = -2 * radius is connected to last member of sum of N odd numbers. This member has index equal to value of radius (integral). Since odd number is 2*n + 1 there is 1 handled elsewhere or it should be -2*radius - 1 ddF_x = 0 should be 1. Because difference between two consecutive odd numbers is 2. If so f += ddF_y + 1 is f+= ddF_y. Saving one operation. f = - radius + 1 Initial error equal to half of "bigger" step. In case of saving one addition it should be either -radius or -radius + 2. In any case there should be addition of 1 driven out of outer loop. So. f += ddF_y Adding odd numbers from Nth to 1st. f += ddF_x Adding odd numbers from 1st to Nth. 1 is missing because it can be moved outside of loop. # EOF #

### larrywal-express commented Jun 12, 2020

Hello
Thanks for your work. I want to ask about how to transform rectangle box to circle box in darknet Yolo. image.c

void draw_box(image a, int x1, int y1, int x2, int y2, float r, float g, float b) {
//normalize_image(a);
int i;
if (x1 < 0) x1 = 0;
if (x1 >= a.w) x1 = a.w - 1;
if (x2 < 0) x2 = 0;
if (x2 >= a.w) x2 = a.w - 1;

``````if (y1 < 0) y1 = 0;
if (y1 >= a.h) y1 = a.h - 1;
if (y2 < 0) y2 = 0;
if (y2 >= a.h) y2 = a.h - 1;

for (i = x1; i <= x2; ++i) {
a.data[i + y1*a.w + 0*a.w*a.h] = r;
a.data[i + y2*a.w + 0*a.w*a.h] = r;

a.data[i + y1*a.w + 1*a.w*a.h] = g;
a.data[i + y2*a.w + 1*a.w*a.h] = g;

a.data[i + y1*a.w + 2*a.w*a.h] = b;
a.data[i + y2*a.w + 2*a.w*a.h] = b;
}
for(i = y1; i <= y2; ++i) {
a.data[x1 + i*a.w + 0*a.w*a.h] = r;
a.data[x2 + i*a.w + 0*a.w*a.h] = r;

a.data[x1 + i*a.w + 1*a.w*a.h] = g;
a.data[x2 + i*a.w + 1*a.w*a.h] = g;

a.data[x1 + i*a.w + 2*a.w*a.h] = b;
a.data[x2 + i*a.w + 2*a.w*a.h] = b;
}
``````

}

void draw_box_width(image a, int x1, int y1, int x2, int y2, int w, float r, float g, float b) {
int i;
for (i = 0; i < w; ++i) {
draw_box(a, x1+i, y1+i, x2-i, y2-i, r, g, b);
}
}