# Mid Point Circle Algorithm

Views:

Category: Education

## Presentation Description

No description available.

## Presentation Transcript

### Circle Midpoint Algorithm :

Circle Midpoint Algorithm draw pixels in this octant (draw others using symmetry) (0,R) (0,-R) (R,0) (-R,0) Implicit function for circle on circle inside outside x+ y+

### Choosing the Next Pixel :

Choosing the Next Pixel choose E choose SE decision variable d

### Change of d when E is chosen :

Change of d when E is chosen

### Change of d when SE is chosen :

Change of d when SE is chosen Mold (x, y) (x+1, y) E SE (x+1, y+2) (x+2, y+2) Mnew

### Initial value of d :

Initial value of d (0,-R) M0 (1,-R) (1,-R+1)

### Midpoint Circle Algo :

Midpoint Circle Algo x = 0; y = -R; d = 5/4 – R; /* real */ setPixel(x,y); while (y > x) { if (d > 0) { /* E chosen */ d += 2*x + 3; x++; } else { /* SE chosen */ d += 2*(x+y) + 5; x++; y++; } setPixel(x,y); }

### New Decision Variable :

New Decision Variable Our circle algorithm requires arithmetic with real numbers. Let’s create a new decision variable h h=d-1/4 Substitute h+1/4 for d in the code. Note h > -1/4 can be replaced with h > 0 since h will always have an integer value.

### New Circle Algorithm :

New Circle Algorithm x = 0; y = -R; h = 1 – R; setPixel(x,y); while (y > x) { if (h > 0) { /* E chosen */ h += 2*x + 3; x++; } else { /* SE chosen */ h += 2*(x+y) + 5; x++; y++; } setPixel(x,y); }

### Second-Order Differences :

Second-Order Differences Note that d is incremented by a linear expression each time through the loop. We can speed things up a bit by tracking how these linear expressions change. Not a huge improvement since multiplication by 2 is just a left-shift by 1 (e.g. 2*x = x<<1).

### 2nd Order Difference when E chosen :

2nd Order Difference when E chosen When E chosen, we move from pixel (x,y) to (x+1,y).

### Slide 11:

2nd Order Difference when SE chosen When SE chosen, we move from pixel (x,y) to (x+1,y+1).

### New and Improved Circle Algorithm :

New and Improved Circle Algorithm x = 0; y = -R; h = 1 – R; dE = 3; dSE = -2*R + 5; setPixel(x,y); while (y > x) { if (h > 0) { /* E chosen */ h += dE; dE += 2; dSE += 2; x++; } else { /* SE chosen */ h += dSE; dE += 2; dSE += 4; X++; y++; } setPixel(x,y); }