# Determining the minimum number of pixels on the boundary of a circle drawn in discrete space

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.

• A possibly better way to draw accurate circles in a discrete space is to iterate over the entire square (x-r,y+r),(x+r,y-r) [that's (upper left, bottom right)-format] and for each pixel(px, py) determine if (px-x)^2+(py-y)^2 <= r^2 (which is also a different shape than yours). Your method requires you to calculate a "good" theta and then you will either recalculate some pixels multiple times or skip some, and introduces rounding artifacts. Then your boundary should be all colored pixels with an uncolored pixel in at least one of (up, down, left, right) neighbor. – ex0du5 Jul 6 '12 at 1:09
• – ex0du5 Jul 6 '12 at 1:09
• For a simpler algorithm, see Bresenham's circle algorithm. – lhf Jul 6 '12 at 1:57
• @exodu5 - Thanks, you're right, I do generate pixels multiple times especially if I use a small sweeping $\Delta \theta$. However, if I am only looking for the boundary and not a solid circle, I'd have to either use $(p_x - x)^2 + (p_y - y)^2 = r^2$ or $(r-1)^2 < (p_x - x)^2 + (p_y - y)^2 \leq r^2$ right ? – Mustafa Jul 6 '12 at 5:07
• I second lhf's comment. Bresenham's is the standard algorithm for drawing circles. Please use it. – Rahul Jul 6 '12 at 6:21

## 1 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.

• Thanks Justin. That makes a lot of sense. – Mustafa Jul 6 '12 at 5:14