Here is the Bresenham Circle Algorithm, generally accepted as the most optimized circle algorithm.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 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; } }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 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 } }}كود: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 }
مواقع النشر (المفضلة)