I am trying to draw a circle in discrete space (actual image pixel space). I have the center (x,y) and radius r of a circle that I am supposed to draw. The manner in which I draw this circle is the following:
Starting from the center position (x,y), I have a for loop over angles $\theta \in \{0,2\pi\}$. Lets say the angle is incremented by $\Delta\theta$ in every iteration. In each iteration, I calculate an x-deviation and a y-deviation based on,
$$\Delta x = r cos(\theta)\\ \Delta y = r sin(\theta).$$
The point on the circumference of the circle is then calculated as
$$x' = \text{round}(x + \Delta x)\\ y'= \text{round}(y + \Delta y).$$
This gives a location $(x', y')$ in discrete space at which I can color a pixel. How do I determine for a given radius, what is the minimum number of discrete "pixels" I will have along the circumference.
In other words, lets say if I have a radius of 10, then how many unique discrete points would I have along the boundary of the circle? Is this problem well defined? I know there is a pitfall here of what consists of a discrete circumference. I consider every connected pixel to be a circumference point.
Best Answer
You should probably be using Bresenham's Circle Algorithm?
The "distance" between adjacent pixels is either 1 or $\sqrt{2}$, i.e., two adjacent pixels either share a row or column or they are diagonal. This limits how much of the circumference consecutive pixels can consume. So the number of pixels needed, $x$, to complete the circumference of a circles with a radius of $r$ pixels is bounded $\sqrt{2} \pi r \leq x \leq 2 \pi r$, or roughly $4.443 \times r \leq x \leq 6.283\times r$. This gives a first approximation, by which to check the later estimate.
To get more accuracy we see that, by symmetry, only the pixels drawn in the first octant (i.e., $\pi/4$) need to be computed; the remaining can be found by using the same offsets but in different directions. With each consecutive pixel in the first octant progressing upward, there are at least $\lfloor r \sin(\pi/4)\rfloor$ pixels. Multiply this by 8, and you get roughly $5.657\times r$, which is within the earlier bounds.