4
$\begingroup$

I'm trying to figure out how to calculate the number of whole pixels in a pixel circle using the diameter of the circle.

I understand how to find the area of a circle using diameter. But I'm wondering what else I have to do to round this number correctly. I was looking into the Midpoint circle algorithm, but I don't think that fully answers how to figure this out.

The circle I am making is 17px in diameter, which makes the area 226.865px. When I go to a pixel circle generator and make it 17x17, I have an outcome of 225 pixels. What else do I need to do to find the area in pixels?

$\endgroup$
  • 1
    $\begingroup$ Somewhat related: en.wikipedia.org/wiki/Gauss_circle_problem $\endgroup$ – angryavian Aug 5 '14 at 22:14
  • 1
    $\begingroup$ @ChrisVolkoff Correct, but I don't see why the 225px is irrelevant? 225px is the answer to the equation. I just don't know how to get there. Yes, I am looking for the number of pixels in a pixelated circle. It so happens that there are 225px in a 17x17 pixelated circle. Why? $\endgroup$ – ntgCleaner Aug 5 '14 at 22:17
  • $\begingroup$ I'm sorry. I misunderstood your question. You would have to check each coordinate (each pixel) to see if it they are entirely part of the circle: x^2 + y^2 = 1. This is similar to the midpoint circle algorithm. $\endgroup$ – christophebedard Aug 5 '14 at 22:20
5
$\begingroup$

Please consider this as an supplement to Ross's answer.

I figured out how the pixel generator count the number of unit squares inside the inscribed circle for a $d \times d$ square. It basically count the number of unit squares whose centers lie in the interior or on the boundary of the inscribed circle.

Geometrically, this falls into two cases.

Case I - $d = 2\ell + 1$ is odd.

When $d$ is odd, the center of the inscribed circle coincides with the center of one of the unit squares. The centers of the unit squares lie on an integer lattice and the number we want is

$$\mathcal{N}_{odd}(d) = \left| \left\{\; (x,y) \in \mathbb{Z}^2 : \sqrt{ x^2 + y^2 } \le \frac{d}{2} \;\right\}\right|$$ Notice the lattice points inside the inscribed circle has a $4$-fold rotational symmetry with respect to the center of $d\times d$ square. This give us $$\begin{align} \mathcal{N}_{odd}(d) &= 1 + 4 \left|\left\{ (x,y) \in \mathbb{Z}^2 : \sqrt{ x^2 + y^2 } \le \frac{d}{2}, x \ge 0, y > 0 \;\right\}\right|\\ &= 1 + 4 \sum_{y=1}^\ell \left|\left\{ x \in \mathbb{Z} : \sqrt{ x^2 + y^2 } \le \frac{d}{2}, x \ge 0 \;\right\}\right|\\ &= 1 + 4 \sum_{y=1}^\ell \left\lfloor 1 + \sqrt{\left(\frac{d}{2}\right)^2 - y^2} \right\rfloor \end{align} $$ What Gauss has shown is we can get rid of the square root inside the floor and

$$\mathcal{N}_{odd}(d) = 1 + 4 \sum_{i=0}^\infty\left[\left\lfloor \frac{r^2}{4i+1}\right\rfloor-\left\lfloor \frac{r^2}{4i+3}\right\rfloor\right]$$

as given in Ross' answer.

Case II - $d = 2\ell$ is even.

When $d$ is even, the center of the inscribed circle coincides with the common corner of 4 unit squares. If we choose a coordinate system such that this center is the origin, the centers of the unit squares nows lies on an "half-integer" lattice. The numbers we want becomes

$$\mathcal{N}_{even}(d) = \left|\left\{\; (x,y) \in \mathbb{Z}_h^2 : \sqrt{x^2+y^2} \le \frac{d}{2}\;\right\}\right| \quad\text{ where }\quad \mathbb{Z}_h = \left\{\; x + \frac12 : x \in \mathbb{Z} \;\right\} $$ One again, the lattice points inside the inscribed circle has a 4-fold rotation symmetry. This leads to $$\begin{align} \mathcal{N}_{even}(d) &= 4\left|\left\{\; (x,y) \in \mathbb{Z}_h^2 : \sqrt{x^2+y^2} \le \frac{d}{2}, x > 0, y > 0\;\right\}\right|\\ &= 4\sum_{y=1}^\ell \left|\left\{\; x \in \mathbb{Z} : \sqrt{(x-\frac12)^2+(y-\frac12)^2} \le \frac{d}{2}, x > 0\;\right\}\right|\\ &= 4\sum_{y=1}^\ell \left\lfloor\frac12 + \sqrt{\left(\frac{d}{2}\right)^2 - \left(y-\frac12\right)^2}\right\rfloor \end{align} $$ Combine this, we obtain a formula for the number of unit squares:

$$\mathcal{N}(d) = \begin{cases} 1 + 4 \sum\limits_{y=1}^\ell \left\lfloor 1 + \frac12\sqrt{d^2 - 4y^2}\right\rfloor, & d = 2\ell+1\\ \\ 4\sum\limits_{y=1}^\ell \left\lfloor\frac12 + \frac12\sqrt{d^2 - (2y-1)^2}\right\rfloor, & d = 2\ell\\ \end{cases} $$ For small $d \le 50$, $\mathcal{N}(d)$ is given by

$$\begin{array}{|r:l|} \hline d & \mathcal{N}(d)\\ \hline \verb/ 1-10/& 1,4,9,12,21,32,37,52,69,80,\\ \verb/11-20/& 97,112,137,156,177,208,225,256,293,316,\\ \verb/21-30/& 349,384,421,448,489,540,577,616,665,716\\ \verb/31-40/& 749,812,861,912,973,1020,1085,1124,1201,1264\\ \verb/41-50/& 1313,1396,1457,1528,1597,1664,1741,1804,1885,1976\\ \hline \end{array}$$

Matching the corresponding numbers from pixel generators and that on OEIS A124623.

$\endgroup$
  • $\begingroup$ This is certainly a supplement to Ross' answer, though this explains perfectly what I was asking for. This is the accepted answer for me, seeing as how Gauss' formula is not exactly what I was looking for. Thank you! $\endgroup$ – ntgCleaner Aug 6 '14 at 18:46
6
$\begingroup$

This is known as Gauss' circle problem. For a radius $r$, the number of lattice points inside a circle is $$N(r)=1+4\sum_{i=0}^\infty\left(\left\lfloor \frac{r^2}{4i+1}\right\rfloor-\left\lfloor \frac{r^2}{4i+3}\right\rfloor\right)$$

$\endgroup$
  • $\begingroup$ Thank you Ross! I am... terrible at math. I'm actually trying to figure this out to program it for a website. If it's not too much trouble, would you mind explaining this formula? I'm reading through the wiki right now $\endgroup$ – ntgCleaner Aug 5 '14 at 22:22
  • $\begingroup$ Edited to correct the equation. $\endgroup$ – Deepak Aug 5 '14 at 22:30
  • 1
    $\begingroup$ Are you sure the number of lattice points is equivalent to the number of pixels? The exact number of pixels is going to be down to how the software chooses to approximate curved lines using pixels, which might not be based on lattice points. $\endgroup$ – Jack M Aug 5 '14 at 22:33
  • $\begingroup$ In particular, counting lattice points and pixels in the application the OP linked to seems to give different numbers. $\endgroup$ – Jack M Aug 5 '14 at 22:36
  • $\begingroup$ @JackM: I was taking it to be the number of pixels that are wholly contained inside the circle. This will not be the best fit to the circle. You may be correct in what OP wants. $\endgroup$ – Ross Millikan Aug 5 '14 at 22:48

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.