Calculating pi by counting pixels (or not)
Вставка
- Опубліковано 31 бер 2023
- For Pi Day a few weeks ago (3/14) I wanted to write a program to calculate pi by drawing a circle in graphics mode and counting the pixels to estimate the circumference. I didn't think that would give me 3.14 for pi, but I thought it might be close. I was wrong.
Counting pixels is basically sampling the circle, it's not actually measuring the circumference. But I thought this would be a good April 1 video!
A better way to use pixels to calculate pi is to "measure" the "distance" between the pixels in the circle. I wrote an article about that, here: opensource.com/article/23/3/c...
Visit our website
www.freedos.org/
Join us on Facebook
/ freedosproject
Follow us on Mastodon
fosstodon.org/@freedosproject
Consider supporting me on Patreon
/ freedos
And don't forget to Like and Subscribe!
Standard comment rules apply. - Наука та технологія
If you drew a solid circle using Pythagoras and plotting lines you could use the same process but work pi out from the area.
Even better just draw a quarter circle and multiply the result by 4:
r = 240
for ( x = 0; x
I think you're describing the method I wrote about in this Pi Day article: opensource.com/article/23/3/calculate-pi-counting-pixels
Basically, calculate the "distance" between pixels to draw the outline of the circle. If you want to calculate pi by drawing an outline, this is better than just counting pixels.
Of course, the better method would be to use a filled circle, then count pixels in the area to use A=πr² or π=A/r² (this is a much better estimate of pi)
I enjoyed watching you write the code. What can I say, I'm a geek/nerd/techie.
Thanks! I just posted another programming video - but next week's video will be back to games and apps for a while. ☺
A good observation is: if you split the circle into 4 sectors in a cross (top/bottom/left/right), you can see top and bottom sectors each have 1 pixel for every x, left and right each have 1 pixel for every y. If you "move" those pixels into a square (like pushing dust), you actually get the inscribed square, whose perimeter is 1357.645 (the extra 1.645 is the extra precision in my android calc while calculating that square from diameter: 4 sides of 480/sqrt(2) ). The higher the resolution, the smaller this difference will get. That's where the sampling fails.
I think with anti-aliasing you can get closer if you do a sum instead of count (i.e.: aliased pixels get "smaller counts"). But of course, that fails if the aliasing has any gamma applied (assuming 16+ bit colors, not palette).
You can get away with the anti-aliasing if you count the background pixels, because we already know the total pixel count (480x480) and subtracting the unchanged pixels we know how many of the rest there are.
Thanks, you said it and I don't have to! I think it's neat that he tried to approximate one irrational and ended up approximating a different one :)
Good point. And as someone pointed out on Fosstodon, the method of counting pixels is basically the same as the "square" method: ua-cam.com/video/VYQVlVoWoPY/v-deo.html
Also: the OpenWatcom _ellipse function does not do antialiasing. Pixels are either set or not.
Using Archimedes method by calculating the circumference of a polygon using geometric laws is more accurate to calculate pi.
the method used in this code is equivalent to perimeter of inscribed sqaure/diameter = 2*sqrt(2) =~2.825
Yes, someone on Fosstodon also pointed me to this method, basically what you're describing. It explains why the value is about 2.8:
ua-cam.com/video/VYQVlVoWoPY/v-deo.html
Haven't finished the video yet, but I have a guess that your result from counting pixels may be around 15% off? Part of the pixels have centers 1 unit apart, but the ones that are adjacent diagonally have centers the square root of two units apart.
After finishing the video, I see it's actually only about 11% off. It wasn't as bad as I thought, but that still ain't a great approximation of pi.
Yes, it's a bad calculation! ☺ There are better ways to calculate pi with pixels on the screen. One way is to use a filled circle, and count those pixels:
A = π r² … thus π = A / r²
A quick C program gives 3.14444
Another way is to measure "pixel distance" around the perimeter of the circle. This is still off, but it's a little closer than the "count pixels for the circumference" method.
I described the second method here: opensource.com/article/23/3/calculate-pi-counting-pixels
I remember doing something like this in reverse as well as many other things when I was 10 years old trying to figure out how to draw a circle before I even heard of sine or cosine...
This was back in the 80s so there were no libraries....
I did the same on the Apple II! I was about the same age, and sin() and cos() were unknown to me. I developed a weird algebraic method to draw something *close* to a circle on the Apple II without trig functions, but it wasn't a very good circle. ☺
@@freedosproject was that apple II also the only and first computer for students in the whole district?
@@petevenuti7355 We had *two* Apple II+ computers in our elementary school until our 6th grade classroom got an Apple IIe. So I guess someone applied for funding. 😄
We also had an Apple II clone at home, called the Franklin ACE 1000. That's where I did most of my programming.
@@freedosproject yeah I was told the district was experimenting to see if kids could benefit from having a computer, I think I was in 5th grade at the time, ended up tutoring other kids by sixth grade. But Middle school's they got a whole room full.. and the large system with one of those canister drives, they let me take cobol as a language credit instead of Spanish or Latin.. never used it since...
Now there is no language requirement.
the circumference of a circle with a diameter of 480 units should approximately be 1507 units. This is where the aliasing (or lack thereof) comes into play - because you're only drawing (and checking!) whole pixels and not subpixels, not all of the circle is getting drawn/measured.
That was my initial assumption (and why I initially thought my calculation of pi would be "close") but "3 blue 1 brown" has a very well done video about why this isn't the right method. It's the second of the "false proofs" he goes through. ua-cam.com/video/VYQVlVoWoPY/v-deo.html
You basically have the basis of a program to calculate π by "shooting" pixels at (pseudo)random positions and counting how many are inside the circle. If i is the number of pixels inside the circle and t is the total number of random pixels then π=4*i/t.
In fact, it is the most well-known example of a simple Montecarlo method, and it will give a decent estimated value for π. Do not expect great accuracy though.
Yes, this is not a great method. It turns out calculating based on area gives a much better result (3.144). I just posted that video. ☺
Could you use a blank between your x and y coordinate numbers for future videos, when you write coordinates like 0,0 and 639,479?
This would making reading your code much easier.
Reason:
In some languages like German the comma separator is a separator for Floating-point numbers (or more precisely rational numbers ℚ ) .
This means, if you write 639,479 instead of 639, 479 with a blank between x and y then i will read 639.479.
This makes reading your code a little bit distracting.
I'll try to do that. Thanks for letting me know.
@@freedosproject Thanks!
A better solution would be to fill the circle and use the area instead of the perimeter.
That's the video after this one 😃
I got the same result on python
The follow-up video briefly mentions that the "outline" method will never work, and links to another video that explains why in more detail. But that follow-up video also provides a method that *does* work, using the area method: ua-cam.com/video/jHC1iLHtUP8/v-deo.html
Your explanation of why this estimate is inaccurate for pi, must really be a joke, because it's not inaccurate because "we are sampling the circle", but because it approximates another number. 😂 Would you not sample the perimeter only but the whole area instead, the estimate would be near 3.1409. Your method does not approximate pi, but cheer up, you've found a nice way to approximate sqrt(8). The mathematical intuition is that points are not equidistant on the perimeter and thus you are inadvertently approximating a weighted integral of the arc length, opposed to the actual one. The circle drawing algorithm works by calculating the circular arc in one octant only, then transforming the values into the other octants. It always steps one point to the side, and one or zero step orthogonally, until it reaches the diagonal line y=x. It's easy to see that this requires sqrt(2)/2 steps to finish...
You could’ve explained this by sounding a lot less like a pretentious redditor
Yes, the better way to do this *using circumference* is to calculate the "distance" between pixels. This isn't a perfect method either, because measuring a 480x480 circle this way is still a little blocky. But you get a slightly better result. See opensource.com/article/23/3/calculate-pi-counting-pixels
I think that the pixel count is not the circumference
Definitely not the circumference! :-) "3 blue 1 brown" (channel) on UA-cam explains why this doesn't work - this method is very similar to the second of the "false proofs" he goes through (limit of a sequence of curves).
The pixel from 30 to 60 degree don't have a distance of 1 rather 2 squared.
So half of the circle has the distance 1 the other half 2 squared.
Half of your 2.8 is 1.4. 1.4 times 1.4 is about 1.9. So would rather get 3.3.
Yes, that's the solution. I described a better way to calculate "pixel perimeter distance" in this article: opensource.com/article/23/3/calculate-pi-counting-pixels
Since the OpenWatcom _ellipse function doesn't do antialiasing, pixels are either colored in or not. And pixels end up either horizontally or vertically adjacent ("pixel distance" of 1) or diagonally adjacent (x and y "pixel distance" are each 1, for total "pixel distance" of 1.414). Add up the pixels this way, and you get 3.299667.
@@freedosproject But we are still some way off pi. Anyway it was though a rough estimate...
By the way: I am writing to the creator of FreeDOS! Nice to meet you! I'm very pleased!
Long story short, this method approximates 2√2, and not π.
For details see my earlier comment.