algorithmraster

Predict number of points returned mid-point circle algorithm


The well-known mid-point circle algorithm (wikipedia) gives us the x,y coordinates of the pixel coordinates of a circle of given radius.

The computation it uses is iterative, and uses a condition at each iteration to exit the loop: while (y > x) etc...

The question I have is how to predict in advance, given the radius, what will be the total number of point returned by the algorithm?

My mathematical background is limited, and I could not derive it. I googled for it, and the only thing I have found is the following: http://www.gdunge.com/2011/03/23/a-different-kind-of-pi. Doug, the author of the page, mentions that he found by experimenting that round(sqrt(2) * radius) works for a quarter of a circle. I experimented it trying to get the whole circle, and it misses a few points.

What is the substantial law behind this number?


Solution

  • I took your formula as a basis and got this:

    floor((sqrt(2)*(radius-1)+4)/2)*8
    

    And it's working just fine.