Pixels in a circle of radius (r)

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

User avatar
MisterH
Posts: 30
Joined: Thu Jul 21, 2011 11:02 am UTC

Pixels in a circle of radius (r)

Postby MisterH » Fri Oct 14, 2011 5:00 pm UTC

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!

User avatar
jaap
Posts: 2084
Joined: Fri Jul 06, 2007 7:06 am UTC
Contact:

Re: Pixels in a circle of radius (r)

Postby jaap » Fri Oct 14, 2011 6:18 pm UTC

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)

Postby Waterice man » Sat Oct 15, 2011 10:49 am UTC

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: 947
Joined: Thu Jan 08, 2009 7:48 pm UTC

Re: Pixels in a circle of radius (r)

Postby mfb » Sat Oct 15, 2011 11:37 am UTC

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.

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

Re: Pixels in a circle of radius (r)

Postby NathanielJ » Sat Oct 15, 2011 3:01 pm UTC

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

User avatar
jaap
Posts: 2084
Joined: Fri Jul 06, 2007 7:06 am UTC
Contact:

Re: Pixels in a circle of radius (r)

Postby jaap » Sat Oct 15, 2011 3:16 pm UTC

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.

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

Re: Pixels in a circle of radius (r)

Postby eta oin shrdlu » Sat Oct 15, 2011 5:43 pm UTC

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)

Postby Waterice man » Sat Oct 15, 2011 10:01 pm UTC

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

User avatar
jaap
Posts: 2084
Joined: Fri Jul 06, 2007 7:06 am UTC
Contact:

Re: Pixels in a circle of radius (r)

Postby jaap » Sat Oct 15, 2011 10:08 pm UTC

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)

Postby Waterice man » Sat Oct 15, 2011 10:11 pm UTC

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: 947
Joined: Thu Jan 08, 2009 7:48 pm UTC

Re: Pixels in a circle of radius (r)

Postby mfb » Tue Oct 18, 2011 8:34 am UTC

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.


Return to “Mathematics”

Who is online

Users browsing this forum: No registered users and 9 guests