• ### Popular Now

• 10
• 9
• 13
• 10
• 18

#### Archived

This topic is now archived and is closed to further replies.

# Michener's Circle Algorithm

This topic is 5562 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Hi all, Could someone tell me the derivation of this algorithm, because i can't find it. On many pages it says how to apply it, but there is no derivation at all. Like this: { int x = 0; int y = nRadius; // Error term int d = 3 - 2 * nRadius; while (x <= y) { DrawPixel(pSurface, xc + x, yc + y, color); DrawPixel(pSurface, xc - x, yc + y, color); DrawPixel(pSurface, xc + x, yc - y, color); DrawPixel(pSurface, xc - x, yc - y, color); DrawPixel(pSurface, xc + y, yc + x, color); DrawPixel(pSurface, xc - y, yc + x, color); DrawPixel(pSurface, xc + y, yc - x, color); DrawPixel(pSurface, xc - y, yc - x, color); // Error update term if (d < 0) { d += 4 * x + 6; } else { d += 4 * (x - y) + 10; --y; } ++x; } } I want to know the derivation. Can somebody help me out? The final result is like this: di+1 = di + 4x_{i-1} + 6 + 2(y_{i}^2 - (y_{i-1})^2) - 2(y_{i}-y_{i-1} BTW: '_{i}' means it is a lower index like in math '^x' means to the power of x Matthijs [edited by - rm82 on December 24, 2002 8:54:27 AM]

##### Share on other sites
That algorithm is mostly referred to as "Bresenham''s circle algorithm". Do a search on Google for that and you''ll find numerous of links to it (I hardly found anything on Michener :/ ).

Does anybody actually know which line, circle- and ellipse-routines are by Bresenham, and which "extensions" are by others? I''d really want to know, it seems that everybody''s using "Bresenham" for everything...

##### Share on other sites
i found out the algorithm. im making a tutor which covers all types of line, circle drawing algorithms and descendants of bresenhams''.

Matthijs

##### Share on other sites
Cool, I gotta see that to make sure I know which line (circle, ellipse, whatever) is made by who

##### Share on other sites
I found this. Note that the math is different because this example increments x and decrements y before d is updated, instead of after like in your algorithm.

Assume that the last point was (x-1,y). Find whether (x,y-½) is above or below the circle, and move SE to (x,y-1) or E to (x,y), respectively.

y=r;pixel(0,r);for(x=1;x < r/sqrt(2);x++){  d=x^2+(y-1/2)^2-r^2;   if (d>=0) y--;   pixel(x,y);}

Optimize: d=x^2+(y-1/2)^2-r^2 becomes d=x^2+y^2-y+1/4-r^2. How does the d for a given x differ from d for x-1? If y is unchanged, then d{x} = d{x-1}+2x-1. If y decreases, add -2y+2, where that is the old y. Also the only time that 1/4 affects the test d>0 is when d=1/4, so ignore it, but make the test d>=0.

y=r;d= -r;pixel(0,r);for(x=1;x < r/sqrt(2);x++){  d+= 2x-1;   if (d>=0)    {  y--;      d -= 2y; /* Must do this AFTER y-- */   }   pixel(x,y);}

This is Bresenham's circle algorithm. Note that you can store 2x-1 and -2y and update them by adding or subtracting 2.

[edited by - jediknight219 on December 27, 2002 11:48:48 AM]