## Pixels in a circle of radius (r)

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

MisterH
Posts: 31
Joined: Thu Jul 21, 2011 11:02 am UTC

### Pixels in a circle of radius (r)

If you use the Bresenham method to draw a circle on a bitmap, it has a finite number of pixel co-ordinates for a given radius

Radius Number of Pixels
1 4
2 12
3 16
4 24
5 28
6 32
7 40
8 44
9 52
10 56
Click spoiler for more...
Spoiler:
11 64
12 68
13 72
14 80
15 84
16 92
17 96
18 100
19 108
20 112
21 120
22 124
23 132
24 136
25 140
26 148
27 152
28 160
29 164
30 168
31 176
32 180
33 188
34 192
35 196
36 204
37 208
38 216
39 220
40 228
41 232
42 236
43 244
44 248
45 256
46 260
47 264
48 272
49 276
50 284

It goes up by 4 or 8 for each radius increment but I can't work out the pattern behind it.

2 times the radius, times the square root of 8 is the mean, but it is not precise enough.

I'm hoping someone has a better grasp of the maths involved and can provide a single formula that provides the exact number of pixels required for any given radius. Thanks!

jaap
Posts: 2091
Joined: Fri Jul 06, 2007 7:06 am UTC
Contact:

### Re: Pixels in a circle of radius (r)

For the range of numbers you gave, one formula for it would be 5.654 * radius, rounded to the nearest multiple of 4. In other words, it is 4*round(5.654/4 * radius).
For this range any number in the interval [5.6522 , 5.6571] works as the multiplier above. If you want it to be valid for a larger range of radius values that interval will be smaller and you might have to twerk that multiplier a bit.

Waterice man
Posts: 10
Joined: Wed Oct 12, 2011 2:50 pm UTC

### Re: Pixels in a circle of radius (r)

After graphing and analysing this it seems to be tending towards a limit of 1.111*the circumference (with all limits the integers bring). It seems for the data provided, this is completely correct to the nearest multiple of 4

mfb
Posts: 948
Joined: Thu Jan 08, 2009 7:48 pm UTC

### Re: Pixels in a circle of radius (r)

If the limit of the ratio pixels/radius is irrational (and I think it is), there is no repeating system telling you whether the algorithm adds 4 or 8 pixels.
Something like jaap's method may work, with an irrational factor 5.65...

@Waterice man: The circumference is larger than the number of pixels.

NathanielJ
Posts: 882
Joined: Sun Jan 13, 2008 9:04 pm UTC

### Re: Pixels in a circle of radius (r)

This sequence appears to be 4*A022846. In other words, the number in jaap's post appears to be [imath]4\sqrt{2} = 5.65685...[/imath]

As far as a proof goes though, I have no idea.
Homepage: http://www.njohnston.ca
Conway's Game of Life: http://www.conwaylife.com

jaap
Posts: 2091
Joined: Fri Jul 06, 2007 7:06 am UTC
Contact:

### Re: Pixels in a circle of radius (r)

NathanielJ wrote:This sequence appears to be 4*A022846. In other words, the number in jaap's post appears to be [imath]4\sqrt{2} = 5.65685...[/imath]

As far as a proof goes though, I have no idea.

Very nice.
In a way it's not surprising that sqrt(2) appears, but the more I look at it the more surprising it gets. I have no idea how to prove it either, but I get the feeling that either it's pretty hard to prove or there must be some kind of insight I'm missing that would make it nearly obvious.

eta oin shrdlu
Posts: 450
Joined: Sat Jan 19, 2008 4:25 am UTC

### Re: Pixels in a circle of radius (r)

jaap wrote:
NathanielJ wrote:This sequence appears to be 4*A022846. In other words, the number in jaap's post appears to be [imath]4\sqrt{2} = 5.65685...[/imath]

As far as a proof goes though, I have no idea.

Very nice.
In a way it's not surprising that sqrt(2) appears, but the more I look at it the more surprising it gets. I have no idea how to prove it either, but I get the feeling that either it's pretty hard to prove or there must be some kind of insight I'm missing that would make it nearly obvious.
It's easy to see why it's pretty close to 4*sqrt(2). The arc of a Bresenham circle has exactly one pixel per row from 0° to 45° (i.e., as you follow the circle pixels around from 0° to 45°, you always step either north one pixel or northwest one pixel), which means that this eighth of the circle has about r*sin(45°)=r/sqrt(2) pixels; multiplying by 8 gives r*4*sqrt(2).

I'd have to look at the algorithm more closely to see if this is exact though.

Waterice man
Posts: 10
Joined: Wed Oct 12, 2011 2:50 pm UTC

### Re: Pixels in a circle of radius (r)

I meant division. However, it seems to me that ALL of the datum provided fit the model I propose, to the nearest multiple of 4

jaap
Posts: 2091
Joined: Fri Jul 06, 2007 7:06 am UTC
Contact:

### Re: Pixels in a circle of radius (r)

Waterice man wrote:I meant division. However, it seems to me that ALL of the datum provided fit the model I propose, to the nearest multiple of 4

Yes, 2*pi / 1.111 = 5.655, which matches what I posted.

Waterice man
Posts: 10
Joined: Wed Oct 12, 2011 2:50 pm UTC

### Re: Pixels in a circle of radius (r)

I'd be interested to see why the 1.111 comes about, or perhaps this is better described as *0.900 rather than /1.111, which makes it even more interesting. I, however, don't know enough about this sort of thing yet.

mfb
Posts: 948
Joined: Thu Jan 08, 2009 7:48 pm UTC

### Re: Pixels in a circle of radius (r)

4*sqrt(2)/(2pi) = 0.900316
2pi/(4*sqrt(2))=1.11072
Just coincidence with the value 1.111.

>> The arc of a Bresenham circle has exactly one pixel per row from 0° to 45°
And that explains the formula.