2

https://www.geeksforgeeks.org/bresenhams-circle-drawing-algorithm/

I was looking at Bresenham's algorithm which I'm trying to use to make a MS paint style application. I've implemented it into python and it works. However, I was not sure HOW this worked. I understood all of the algorithm except for the decision parameter. Specifically why it has to be d = 3 – (2 * r) , d = d + (4*x) + 6 or d = d + 4 * (x – y) + 10. Is anyone familiar with the algorithm or understands the math behind how these were derived? I understood the theory behind the algorithm for lines, but I'm having a hard time understanding the circle drawing.

Tino Tom
  • 31
  • 4

1 Answers1

3

If you just drew pixel (x,y), then the next pixel to be drawn is either (x+1,y) or (x+1,y-1)

The actual condition used determine which one to choose is appoximately which one is closest to the ideal circle. Specifically (x+1,y-1) is chosen if (x+1)² + y² - r² > r² - (x+1)² - (y-1)²

Collecting like terms, simplifies to 2(x+1)² + y² + (y-1)² - 2r² > 0

Expanding gives 2x² + 2y² - 2r² + 4x - 2y + 3 > 0

That expression on the left is d. Initially, x=0 and y=r, so most of those terms are zero or cancel out and we have d = 3 - 2y = 3 - 2r

The other expressions you ask about indicate how d changes after you pick the next pixel.

http://www.wolframalpha.com/input/?i=simplify+(2(x%2B2)%C2%B2+%2B+(y-1)%C2%B2+%2B+(y-2)%C2%B2+-+2r%C2%B2)+-+(2(x%2B1)%C2%B2+%2B+y%C2%B2+%2B+(y-1)%C2%B2+-+2r%C2%B2)

http://www.wolframalpha.com/input/?i=simplify+(2(x%2B2)%C2%B2+%2B+y%C2%B2+%2B+(y-1)%C2%B2+-+2r%C2%B2)+-+(2(x%2B1)%C2%B2+%2B+y%C2%B2+%2B+(y-1)%C2%B2+-+2r%C2%B2)

Matt Timmermans
  • 53,709
  • 3
  • 46
  • 87