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:

  1. If $A$ doesn't pertain to the circle, then neither does $B$ (I assume because of the symmetries given by the circle)
  2. 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 :)!

  • $\begingroup$ I assume it arises from expanding the conditions $(x+1)^2+y^2<(r+\frac12)^2$ for A and $(r-\frac12)^2\le x^2+(y-1)^2$ for B, then looking for common terms. $\endgroup$ – user856 Dec 2 '16 at 14:36
  • $\begingroup$ @Rahul Yeah, it seems so. By expanding the conditions, we get the hypothesis $d \geq 2x$ for $A$ and $d < 2(r - y)$ for $B$. So basically this $d$ was just a notation to simplify the explanation afterwards, but not something priorly deduced from something. Is that it? $\endgroup$ – Sonia Seddiki Dec 2 '16 at 15:08
  • $\begingroup$ Yup, the first one is $r^2+r-x^2-y^2-2x>\frac34$, and the second one is $r^2-r-x^2-y^2+2y\le\frac34$. Since the left-hand side is always an integer, we can replace the right-hand sides by $\ge1$ and $<1$ respectively, and then we quickly get to the desired conditions. $\endgroup$ – user856 Dec 2 '16 at 15:15

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.

  • $\begingroup$ Absolutely not, but I'll start digging from there after work :). Thanks! $\endgroup$ – Sonia Seddiki Dec 2 '16 at 14:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.