For my first post here I'll come with a question about Andres circle algorithm. If you've never heard about it, its aim is to get, for a given circle (centre C, radius r), a representation of this circle with pixels on an image. Pretty much the same as Bresenham's algorithm, except that a set of concentric circles can cover the whole image without missing any pixel, but anyway, that's not the point here.
I am curious about the math behind this algorithm, and since it is hard to find the original paper or an explanation somewhere (there is a French article on Wikipedia that sums up the whole idea), I was hoping some of you here would help me.
Beginning of the algorithm
Let's take a circle $\Gamma (C, r)$. Basically the idea is to start at the top of the circle, say $P(x_C, y_C + r)$ and turn clockwise to find the next point. We work on the first octant $[\frac{\pi}{2}; \frac{\pi}{4}]$ and complete the others with symmetry.
We consider that the point pertaining to the circle are:
(E) $\{(x,y)\} \;/\; (r - \frac{1}{2})^2 \:\leq\: (x - x_C)^2 + (y - y_C)^2 \:<\: (r + \frac{1}{2})^2$
If $P$ verifies this property, then the next point on the circle can only be $A(x_P + 1, y_P)$, $B(x_P, y_P - 1)$ or $C(x_P + 1, y_P - 1)$. The best choice being the one with a distance from the centre closest to $r$.
Picture to describe the position of the next point
Furthermore, we can deduce other things:
- If $A$ doesn't pertain to the circle, then neither does $B$ (I assume because of the symmetries given by the circle)
- If neither $A$ nor $B$ pertain to the circle, then $C$ does.
Now is the complicated part for me. To simplify the demonstration, the writer takes a circle centred in the origin. Out of the blue, he says:
"Let $d = r^2 + r - x^2 - y^2 - 1$. We prove that we have to choose $A$ if $d \geq 2x$ and $B$ if $d < 2(r - y)$".
He then gives the proof of everything, but never mentions the process to get $d$.
Do you have any idea where this expression of $d$ could come from?
My thoughts so far: starting from the expression of $d$, I could come up with something like that just by rearranging the terms a little bit
$x^2 + y^2 = r^2 + [r - (d + 1)]$
Since we need to be as close as possible from the original circle, I thought the point was to minimize the $[r - (d + 1)]$, but I didn't come to any conclusive result.
It might be obvious, but I'm completely missing it here. So thank you in advance for your answers and feel free to ask for more details :)!
Not a comment and not a full answer:
Have you tried using $(a r^2 + b r + c) - (x^2 + y^2)$ in the proof as given to produce a set of constraints on $a$, $b$, and $c$ so that the given claim actually holds? (I have to rush off to class, otherwise I would try this myself and report the consequences...)
Why $(a r^2 + b r + c)$? I presume because the constraints deduced from the simpler $(b r + c)$ are inconsistent.