Here is the Bresenham Circle Algorithm, generally accepted as the most optimized circle algorithm.
كود:
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;
}
}
Another algorithm is called the midpoint algorithm. This algorithm can't explicitly draw the 4 cardinal points so we draw them before the algorithm then take the 1st and 2nd derivative to incrementalize.
كود:
void CircleMidpoint(int xc, int yc, int r, int color)
{
int x= 0, y= r;
int d= 1-r;
int dE= 3;
int dSE= 5 - 2*r;
if (!r) return;
drawpixel(xc-r, yc, color);
drawpixel(xc+r, yc, color);
drawpixel(xc, yc-r, color);
drawpixel(xc, yc+r, color);
while (y > x) //only formulate 1/8 of circle
{
if (d < 0)
{
d+= dE;
dE+=2, dSE+=2;
} else {
d+=dSE;
dE+=2, dSE+=4;
y--;
}
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
}
}
At first glance, it looks like we've taken a step back because midpoint circle is actually more code than bresenham but if we inverse the logic for the midpoint algorithm to do spans instead of a check every iteration (just like we did for The Bresenham Line then we can get something much more optimized than either midpoint or bresenham.
كود:
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
}
}
مواقع النشر (المفضلة)