# Can someone help me grasp the circle algorithm?

7 posts

 1312 posts Hey! I’m making my own display framework for pixel games. Currently implementing the circle. Reading about the algorithm on wikipedia, I don’t understand much ._. I might be slow but I’m really interested in understanding stuff I do. Found some copypasta code here So can any of you explain the thought behind the algorithm? Thanks a ton! 521 posts I think, the circle algorithm is similar to Bresenham’s line algorithm which draws a straight line by only knowing the start and end points of the line. From there it gets the gradient and plots the line in a way especially for computer screens. Basically, it moves across one pixel on the x every time, then sees where that pixel needs to be on the y based on the gradient. The circle algorithm seems to be doing a similar thing, but in reverse. (example in 1st quadrant, 1st octant) It is moving up 1 pixel in the y every time, and then seeing if it needs to move left 1 in the x. This works until it gets to 45 degrees, until it has to change. ```void CircleBresenham(int xc, int yc, int r, int color) { int x = 0; int y = r; int p = 3 - 2 * r; if (!r) return; while (y >= x) // only formulate 1/8 of circle { drawpixel(xc-x, yc-y, color);//upper left left drawpixel(xc-y, yc-x, color);//upper upper left drawpixel(xc+y, yc-x, color);//upper upper right drawpixel(xc+x, yc-y, color);//upper right right drawpixel(xc-x, yc+y, color);//lower left left drawpixel(xc-y, yc+x, color);//lower lower left drawpixel(xc+y, yc+x, color);//lower lower right drawpixel(xc+x, yc+y, color);//lower right right if (p < 0) p += 4*x++ + 6; else p += 4*(x++ - y--) + 10; } } ``` Excuse the bad drawing, but that is the order in which the pixels are being drawn. Ignore p for the moment, and just look at x and y. x starts at 0, and increases by 1 every run through of the loop. If y needs to, it decreases. 1312 posts Thanks for the effort man :D I understand it more now, will just wait for the full revelation to drop by :) It draws one pixel per octant every iteration if I’ve understood it correctly. 1312 posts Btw I’ll use the last and most optimized code: ```void CircleOptimized(int xc, int yc, int r, int color) { unsigned int x= r, y= 0;//local coords int cd2= 0; //current distance squared - radius squared if (!r) return; drawpixel(xc-r, yc, color); drawpixel(xc+r, yc, color); drawpixel(xc, yc-r, color); drawpixel(xc, yc+r, color); while (x > y) //only formulate 1/8 of circle { cd2-= (--x) - (++y); if (cd2 < 0) cd2+=x++; drawpixel(xc-x, yc-y, color);//upper left left drawpixel(xc-y, yc-x, color);//upper upper left drawpixel(xc+y, yc-x, color);//upper upper right drawpixel(xc+x, yc-y, color);//upper right right drawpixel(xc-x, yc+y, color);//lower left left drawpixel(xc-y, yc+x, color);//lower lower left drawpixel(xc+y, yc+x, color);//lower lower right drawpixel(xc+x, yc+y, color);//lower right right } } ``` How would I alter it if I wanted to take width and height instead of radius? 113 posts http://www.kirupa.com/forum/showthread.php?200214-8-bitmapData-Circle There’s some explaination if you look a bit further down. 521 posts If you wanted to take width and height istead of radius, I assume you’re talking about an ellipse (squashed circle). There is a pdf on the bottom of the wikipedia page explaining it here With the circle, you could plot 8 points from 1 calculation, but with the ellipse, you can only plot 4. So you need to do a 90 calculation, instead of the 45 with the circle. 113 posts You should not use 8-way symmetry with this since it doesn’t work with small radiusses, and it’s more difficult to code in.