<p>After a short research, I found <a href="https://www.javatpoint.com/computer-graphics-bresenhams-circle-algorithm" rel="nofollow noreferrer">this site</a>, which describes the algorithm. I didn't know it before. An important thing you didn't mention in your question is the calculation of the decision parameter <span class="math-container">$d$</span>, which is:</p>

<p><span class="math-container">$$d=f\left(N\right)+f\left(S\right)$$</span></p>

<p>It abuses the fact, that the bottom pixel will always lie on the circle or inside and the right pixel will always be on the circle or outside (for this particular segment). In conclusion, this means that <span class="math-container">$f\left(S\right) \le 0$</span> and <span class="math-container">$f\left(N\right) \ge 0$</span>. If <span class="math-container">$d&lt;=0$</span> you pick the right one and the left one otherwise.</p>

<blockquote>
  <p>Okay, we're using the circle equation to determine which is the closest point to the circle but why not simply using the euclidean distance?</p>
</blockquote>

<p>Most probably for performance reasons. Using the Euclidean distance requires you to calculate 2 square roots, which is quite expensive when compared to simple multiplication (<span class="math-container">$r\cdot r$</span>). On a Haswell CPU, you can perform 6 independent multiplications at the same time as calculating a single square root. </p>

<p>If you optimize the Bresenham algorithm you will probably get something like that:</p>

<p><span class="math-container">$$\begin{matrix}
d &amp;=&amp; x_{k+1}^2 + y_k^2 - r^2 +  x_{k+1}^2 + y_{k-1}^2 - r^2\\
 &amp;=&amp; 2x_{k+1}^2- 2r^2 + y_k^2   + y_{k-1}^2 \\
 &amp;=&amp; 2\left(x_{k+1}^2- r^2\right) + y_k^2   + y_{k-1}^2
\end{matrix}
$$</span></p>

<p>then compare</p>

<p><span class="math-container">$$d \le 0$$</span>
So in total, you end up with 9 multiplications, 2 additions, 1 subtraction and 1 comparison. </p>

<p><strong>EDIT</strong>
As mentioned in the comments to this answer, the Euclidean length and the Bresenham algorithm won't give you the same results. While the Euclidean length will always give you the Pixel with the closest distance of its center to the arc, the Bresenham algorithm will favor points inside the circle, even though they are a little bit farther away. However, this error gets smaller the closer you get to the circle and shouldn't be noticeable.  </p>

<hr>

<p><strong>Update</strong></p>

<p>After rereading some tutorials like the one above or <a href="https://www.getsetcg.com/2018/10/bresenhams-circle-drawing-derivation.html" rel="nofollow noreferrer">this one</a>, I am not totally sure if they are really stating that they take the closest point. The tutorial I linked says:</p>

<blockquote>
  <p>So if <span class="math-container">$Dk &lt; 0$</span> that means the negative <span class="math-container">$F(S)$</span> is bigger then the positive <span class="math-container">$F(N)$</span>, that implies Point <span class="math-container">$N$</span> is closer to the circle than point <span class="math-container">$S$</span>.</p>
</blockquote>

<p>Language details are not my strong suit, but I think "implies" is meant more in the way of "indicating" something. In this case, it does not mean it is the exact result.</p>

<p>Anyways, after some elongated calculations, you are right, that <span class="math-container">$d=f\left(N\right)+f\left(S\right)$</span> will give wrong results in favor of the inner point if both distances to the circle are quite close. I did some error estimation.
With:</p>

<p><span class="math-container">$$
\begin{matrix}
a &amp;=&amp; \sqrt{x_{k+1}^2 + y_k^2} \\
b &amp;=&amp; \sqrt{x_{k+1}^2 + y_{k-1}^2} \\
\end{matrix}
$$</span>
being the distances to the points from the center, you can calculate the error <span class="math-container">$\epsilon$</span> as follows:</p>

<p><span class="math-container">$$\begin{matrix}
a^2 - r^2 + b^2 - r^2 + \epsilon &amp;=&amp; ((a-r) - (r-b))^2\\
&amp;=&amp; (2r -a - b)^2
\end{matrix}$$</span></p>

<p>If you solve that for <span class="math-container">$\epsilon$</span> you will get:</p>

<p><span class="math-container">$$\epsilon = 6r + 2ab - 4ra - 4 rb$$</span></p>

<p>You can get 2 interesting pieces of information from that. First, as you already claimed, the Bresenham algorithm does not take the exact distance to the circle when deciding which point is the next one, otherwise <span class="math-container">$\epsilon$</span> must have been 0. However, the second information is: If <span class="math-container">$a$</span> and <span class="math-container">$b$</span> are both on the circle, the error vanishes.</p>

<p>I was wondering how much closer <span class="math-container">$a$</span> must be than <span class="math-container">$b$</span> until it is selected. So I did the following:</p>

<p><span class="math-container">$$\begin{matrix}
a &amp;=&amp; r+\delta + \tau\\
b &amp;=&amp; r-\delta 
\end{matrix}$$</span></p>

<p>The reasoning here is as follows: If <span class="math-container">$\tau = 0$</span>, then both points have the same distance <span class="math-container">$\delta$</span> to the circle. So the right-hand side of</p>

<p><span class="math-container">$$\begin{matrix} a^2 - r^2 + b^2 - r^2 + \epsilon &amp;=&amp; (2r -a - b)^2 \end{matrix}$$</span></p>

<p>, the Euclidean distance, will be 0. Now I want to find an offset <span class="math-container">$\tau$</span>, which causes the left-hand side to be 0, which is the condition where the Bresenham algorithm "assumes" both points to be equally distant to the circle. So if you say  <span class="math-container">$$a^2 - r^2 + b^2 - r^2 = 0$$</span>, replace the <span class="math-container">$a$</span> and <span class="math-container">$b$</span> with the shown formulas and solve for <span class="math-container">$\tau$</span> you get:</p>

<p><span class="math-container">$$\tau =   \sqrt{r^2 + 2\delta - \delta^2}- (r + \delta)$$</span></p>

<p>You can rewrite this a little bit so that it looks like this</p>

<p><span class="math-container">$$\tau =   \sqrt{(r + \delta)^2 - 2\delta^2}- \sqrt{(r + \delta)^2}$$</span></p>

<p>From this, you can see again that both approaches give the same result in the special case that both points lie on the circle since <span class="math-container">$\tau$</span> gets 0. Putting in some real numbers will also show, that <span class="math-container">$\tau$</span> does not get too big. I am no mathematician, but I think you can show, that the "error" and <span class="math-container">$\tau$</span> get relatively small with a growing ratio of <span class="math-container">$r:\delta$</span>. So if you are not drawing circles with a radius of just 2-3 pixels, the differences in the visual output should be negligible. </p>

<p>Apart from that, taking the Euclidean distance might also not be the best way in the first place. 
In the end, a rasterized circle is just an approximation and not a true circle. So there is no "correct" rasterization method for that. With enough distance, you won't notice that it contains of pixels. But in this case, you won't also notice anymore which pixels center is closer to the "true circle". </p>

<p><strong>Conclusion</strong></p>

<p>The Euclidean distance and Bresenham algorithm result in slightly different rasterizations (probably not noticeable most of the times).
The Euclidean distance is much more expensive to calculate due to the square roots. Additionally, as one can read in the linked sources, the Bresenham algorithm can be optimized even further than written in this answer, which makes it really fast. If I got it right, one just needs 1-2 multiplications and 2-3 additions/subtractions per pixel.</p>

CC BY-SA 4.0
2020-04-17T17:08:36.513Z
This explanation would have been so convincing and I had really hoped it was that simple, but if we take the square of the distance, we don't get this beautiful $x_{k+1}^2 + y_k^2 - r^2$ but instead a weird $x_{k+1}^2+y_k^2 - 2r\sqrt{x_{k+1}^2+y_k^2}+r^2$, and so I still can't see the link between this weird thing and the actual $f(N)$ that we use in the algorithm.
Voko
CC BY-SA 4.0
2020-04-17T19:42:57.983Z
You are right. I have adjusted my answer for now and will further enhance it tomorrow. Running out of time today. However, even though the algorithm is not always taking the closer pixel, it only picks the wrong one if both distances are really close to each other. So you probably can't tell by just looking at the circle, that the wrong one was choosen.
wychmaster
CC BY-SA 4.0
2020-04-18T14:21:54.780Z
So, I updated my answer, after I did some lengthy, insightful calculations.
wychmaster
CC BY-SA 4.0
2020-04-18T15:41:33.417Z
Thank you so much for your detailed answer, now it's clear to me
Voko
CC BY-SA 4.0
2020-04-17T10:44:38.640Z
2020-04-18T14:21:11.480Z
2020-04-18T14:21:11.480Z
wychmaster
<p>In the Bresenham circle drawing algorithm, we have to choose between the top and bottom pixel, but what we always do is using the circle's equation (<span class="math-container">$f(x, y) = x^2 + y^2 = r^2$</span>) to determine which of the two pixels is closer to the circle (r is the radius).</p>

<p>For the top pixel (N), we thus have <span class="math-container">$f(N) = x_{k+1}^2 + y_k^2 - r^2$</span></p>

<p>And for the bottom pixel (S), we have <span class="math-container">$f(S) = x_{k+1}^2 + y_{k-1}^2 - r^2$</span></p>

<p>Okay, we're using the circle equation to determine which is the closest point to the circle but why not simply using the euclidean distance? What is the point to use f instead of the actual distance? It would be easier to understand (this f function seems to come out of nowhere).</p>

<p>The actual distance between the top pixel and the circle is <span class="math-container">$\sqrt{x_{k+1}^2 + y_k^2} - r$</span> and with the bottom pixel it's <span class="math-container">$r - \sqrt{x_{k+1}^2 + y_{k-1}^2}$</span>.</p>

<p><a href="https://i.sstatic.net/3UQIZ.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/3UQIZ.png" alt="enter image description here"></a></p>

CC BY-SA 4.0
2020-04-17T10:14:46.950Z
You like square roots?
lightxbulb
<algorithm><drawing><midpoint>
Bresenham circle drawing algorithm, compute the distance?
Voko
# Bresenham circle drawing algorithm, compute the distance?

(Asked by: username_0 on 2020-04-17)

In the Bresenham circle drawing algorithm, we have to choose between the top and bottom pixel, but what we always do is using the circle's equation ($f(x, y) = x^2 + y^2 = r^2$) to determine which of the two pixels is closer to the circle (r is the radius).

For the top pixel (N), we thus have $f(N) = x\_{k+1}^2 + y\_k^2 - r^2$

And for the bottom pixel (S), we have $f(S) = x\_{k+1}^2 + y\_{k-1}^2 - r^2$

Okay, we're using the circle equation to determine which is the closest point to the circle but why not simply using the euclidean distance? What is the point to use f instead of the actual distance? It would be easier to understand (this f function seems to come out of nowhere).

The actual distance between the top pixel and the circle is $\sqrt{x\_{k+1}^2 + y\_k^2} - r$ and with the bottom pixel it's $r - \sqrt{x\_{k+1}^2 + y\_{k-1}^2}$.

[![enter image description here](https://i.sstatic.net/3UQIZ.png)](https://i.sstatic.net/3UQIZ.png)

**Tags:** algorithm, drawing, midpoint

> **Comments:**
> **username_1**: You like square roots?  

---

## 1 answers

### Answer by username_2 on 2020-04-17. Score: 2 | Accepted answer

After a short research, I found [this site](https://www.javatpoint.com/computer-graphics-bresenhams-circle-algorithm), which describes the algorithm. I didn't know it before. An important thing you didn't mention in your question is the calculation of the decision parameter $d$, which is:

$$d=f\left(N\right)+f\left(S\right)$$

It abuses the fact, that the bottom pixel will always lie on the circle or inside and the right pixel will always be on the circle or outside (for this particular segment). In conclusion, this means that $f\left(S\right) \le 0$ and $f\left(N\right) \ge 0$. If $d<=0$ you pick the right one and the left one otherwise.

> Okay, we're using the circle equation to determine which is the closest point to the circle but why not simply using the euclidean distance?

Most probably for performance reasons. Using the Euclidean distance requires you to calculate 2 square roots, which is quite expensive when compared to simple multiplication ($r\cdot r$). On a Haswell CPU, you can perform 6 independent multiplications at the same time as calculating a single square root.

If you optimize the Bresenham algorithm you will probably get something like that:

$$\begin{matrix}
d &=& x\_{k+1}^2 + y\_k^2 - r^2 + x\_{k+1}^2 + y\_{k-1}^2 - r^2\\
&=& 2x\_{k+1}^2- 2r^2 + y\_k^2 + y\_{k-1}^2 \\
&=& 2\left(x\_{k+1}^2- r^2\right) + y\_k^2 + y\_{k-1}^2
\end{matrix}
$$

then compare

$$d \le 0$$
So in total, you end up with 9 multiplications, 2 additions, 1 subtraction and 1 comparison.

**EDIT**
As mentioned in the comments to this answer, the Euclidean length and the Bresenham algorithm won't give you the same results. While the Euclidean length will always give you the Pixel with the closest distance of its center to the arc, the Bresenham algorithm will favor points inside the circle, even though they are a little bit farther away. However, this error gets smaller the closer you get to the circle and shouldn't be noticeable.

---

**Update**

After rereading some tutorials like the one above or [this one](https://www.getsetcg.com/2018/10/bresenhams-circle-drawing-derivation.html), I am not totally sure if they are really stating that they take the closest point. The tutorial I linked says:

> So if $Dk < 0$ that means the negative $F(S)$ is bigger then the positive $F(N)$, that implies Point $N$ is closer to the circle than point $S$.

Language details are not my strong suit, but I think "implies" is meant more in the way of "indicating" something. In this case, it does not mean it is the exact result.

Anyways, after some elongated calculations, you are right, that $d=f\left(N\right)+f\left(S\right)$ will give wrong results in favor of the inner point if both distances to the circle are quite close. I did some error estimation.
With:

$$
\begin{matrix}
a &=& \sqrt{x\_{k+1}^2 + y\_k^2} \\
b &=& \sqrt{x\_{k+1}^2 + y\_{k-1}^2} \\
\end{matrix}
$$
being the distances to the points from the center, you can calculate the error $\epsilon$ as follows:

$$\begin{matrix}
a^2 - r^2 + b^2 - r^2 + \epsilon &=& ((a-r) - (r-b))^2\\
&=& (2r -a - b)^2
\end{matrix}$$

If you solve that for $\epsilon$ you will get:

$$\epsilon = 6r + 2ab - 4ra - 4 rb$$

You can get 2 interesting pieces of information from that. First, as you already claimed, the Bresenham algorithm does not take the exact distance to the circle when deciding which point is the next one, otherwise $\epsilon$ must have been 0. However, the second information is: If $a$ and $b$ are both on the circle, the error vanishes.

I was wondering how much closer $a$ must be than $b$ until it is selected. So I did the following:

$$\begin{matrix}
a &=& r+\delta + \tau\\
b &=& r-\delta
\end{matrix}$$

The reasoning here is as follows: If $\tau = 0$, then both points have the same distance $\delta$ to the circle. So the right-hand side of

$$\begin{matrix} a^2 - r^2 + b^2 - r^2 + \epsilon &=& (2r -a - b)^2 \end{matrix}$$

, the Euclidean distance, will be 0. Now I want to find an offset $\tau$, which causes the left-hand side to be 0, which is the condition where the Bresenham algorithm "assumes" both points to be equally distant to the circle. So if you say $$a^2 - r^2 + b^2 - r^2 = 0$$, replace the $a$ and $b$ with the shown formulas and solve for $\tau$ you get:

$$\tau = \sqrt{r^2 + 2\delta - \delta^2}- (r + \delta)$$

You can rewrite this a little bit so that it looks like this

$$\tau = \sqrt{(r + \delta)^2 - 2\delta^2}- \sqrt{(r + \delta)^2}$$

From this, you can see again that both approaches give the same result in the special case that both points lie on the circle since $\tau$ gets 0. Putting in some real numbers will also show, that $\tau$ does not get too big. I am no mathematician, but I think you can show, that the "error" and $\tau$ get relatively small with a growing ratio of $r:\delta$. So if you are not drawing circles with a radius of just 2-3 pixels, the differences in the visual output should be negligible.

Apart from that, taking the Euclidean distance might also not be the best way in the first place.
In the end, a rasterized circle is just an approximation and not a true circle. So there is no "correct" rasterization method for that. With enough distance, you won't notice that it contains of pixels. But in this case, you won't also notice anymore which pixels center is closer to the "true circle".

**Conclusion**

The Euclidean distance and Bresenham algorithm result in slightly different rasterizations (probably not noticeable most of the times).
The Euclidean distance is much more expensive to calculate due to the square roots. Additionally, as one can read in the linked sources, the Bresenham algorithm can be optimized even further than written in this answer, which makes it really fast. If I got it right, one just needs 1-2 multiplications and 2-3 additions/subtractions per pixel.

> **Comments:**
> **username_0**: This explanation would have been so convincing and I had really hoped it was that simple, but if we take the square of the distance, we don't get this beautiful $x_{k+1}^2 + y_k^2 - r^2$ but instead a weird $x_{k+1}^2+y_k^2 - 2r\sqrt{x_{k+1}^2+y_k^2}+r^2$, and so I still can't see the link between this weird thing and the actual $f(N)$ that we use in the algorithm.  
> **username_2**: You are right. I have adjusted my answer for now and will further enhance it tomorrow. Running out of time today. However, even though the algorithm is not always taking the closer pixel, it only picks the wrong one if both distances are really close to each other. So you probably can't tell by just looking at the circle, that the wrong one was choosen.  
> **username_2**: So, I updated my answer, after I did some lengthy, insightful calculations.  
> **username_0**: Thank you so much for your detailed answer, now it's clear to me  

---

