mirror of
https://github.com/LCTT/TranslateProject.git
synced 2024-12-23 21:20:42 +08:00
212 lines
8.7 KiB
Markdown
212 lines
8.7 KiB
Markdown
[#]: subject: "Calculate pi by counting pixels"
|
||
[#]: via: "https://opensource.com/article/23/3/calculate-pi-counting-pixels"
|
||
[#]: author: "Jim Hall https://opensource.com/users/jim-hall"
|
||
[#]: collector: "lkxed"
|
||
[#]: translator: " "
|
||
[#]: reviewer: " "
|
||
[#]: publisher: " "
|
||
[#]: url: " "
|
||
|
||
Calculate pi by counting pixels
|
||
======
|
||
|
||
For Pi Day this year, I wanted to write a program to calculate pi by drawing a circle in [FreeDOS][1] graphics mode, then counting pixels to estimate the circumference. I naively assumed that this would give me an approximation of pi. I didn't expect to get 3.14, but I thought the value would be somewhat close to 3.0.
|
||
|
||
I was wrong. Estimating the circumference of a circle by counting the pixels required to draw it will give you the wrong result. No matter what resolution I tried, the final pi calculation of _circumference divided by diameter_ was always around 2.8.
|
||
|
||
### You can't count pixels to calculate pi
|
||
|
||
I wrote a FreeDOS program using OpenWatcom C that draws a circle to the screen, then counts the pixels that make up that circle. I wrote it in FreeDOS because DOS programs can easily enter graphics mode by using the OpenWatcom `_setvideomode` function. The `_VRES16COLOR` video mode puts the display into 640×680 resolution at 16 colors, a common "classic VGA" screen resolution. In the [standard 16 color DOS palette][2], color 0 is black, color 1 is blue, color 7 is a low intensity white, and color 15 is a high intensity white.
|
||
|
||
In graphics mode, you can use the `_ellipse` function to draw an ellipse to the screen, from some starting x,y coordinate in the upper left to a final x,y coordinate in the lower right. If the height and width are the same, the ellipse is a circle. Note that in graphics mode, x and y count from zero, so the upper left corner is always 0,0.
|
||
|
||
![Drawing a white circle in VGA mode][3]
|
||
|
||
You can use the `_getpixel` function to get the color of a pixel at a specified x,y coordinate on the screen. To show the progress in my program, I also used the `_setpixel` function to paint a single pixel at any x,y on the screen. When the program found a pixel that defined the circle, I changed that pixel to bright white. For other pixels, I set the color to blue.
|
||
|
||
![After evaluating the pixels, the background is blue and the circle is bright white.][4]
|
||
|
||
With these graphics functions, you can write a program that draws a circle to the screen, then iterates over all the x,y coordinates of the circle to count the pixels. For any pixel that is color 7 (the color of the circle), add one to the pixel count. At the end, you can use the total pixel count as an estimate of the circumference:
|
||
|
||
```
|
||
#include <stdio.h>
|
||
#include <graph.h>
|
||
|
||
int
|
||
main()
|
||
{
|
||
unsigned long count;
|
||
int x, y;
|
||
|
||
/* draw a circle */
|
||
|
||
_setvideomode(_VRES16COLOR); /* 640x480 */
|
||
_setcolor(7); /* white */
|
||
_ellipse(_GBORDER, 0, 0, 479, 479);
|
||
|
||
/* count pixels */
|
||
|
||
count = 0;
|
||
|
||
for (x = 0; x <= 479; x++) {
|
||
for (y = 0; y <= 479; y++) {
|
||
if (_getpixel(x, y) == 7) {
|
||
count++;
|
||
/* highlight the pixel */
|
||
_setcolor(15); /* br white */
|
||
_setpixel(x, y);
|
||
}
|
||
else {
|
||
/* highlight the pixel */
|
||
_setcolor(1); /* blue */
|
||
_setpixel(x, y);
|
||
}
|
||
}
|
||
}
|
||
|
||
/* done */
|
||
|
||
_setvideomode(_DEFAULTMODE);
|
||
|
||
printf("pixel count (circumference?) = %lu\n", count);
|
||
puts("diameter = 480");
|
||
printf("pi = c/d = %f\n", (double) count / 480.0);
|
||
|
||
return 0;
|
||
}
|
||
```
|
||
|
||
But counting pixels to determine the circumference underestimates the actual circumference of the circle. Because pi is the ratio of the circumference of a circle to its diameter, my pi calculation was noticeably lower than 3.14. I tried several video resolutions, and I always got a final result of about 2.8:
|
||
|
||
```
|
||
pixel count (circumference?) = 1356
|
||
diameter = 480
|
||
pi = c/d = 2.825000
|
||
```
|
||
|
||
### You need to measure the distance between pixels to get pi
|
||
|
||
The problem with counting pixels to estimate the circumference is that the pixels are only a _sample_ of a circular drawing. Pixels are discrete points in a grid, while a circle is a continuous drawing. To provide a better estimate of the circumference, you must measure the _distance between pixels_ and use that total measurement for the circumference.
|
||
|
||
To update the program, you must write a function that calculates the distance between any two pixels: x0,y0 and x,y. You don't need a bunch of fancy math or algorithms here, just the knowledge that the OpenWatcom `_ellipse` function draws only solid pixels in the color you set for the circle. The function doesn't attempt to provide _antialiasing_ by drawing nearby pixels in some intermediate color. That allows you to simplify the math. In a circle, pixels are always directly adjacent to one another: vertically, horizontally, or diagonally.
|
||
|
||
For pixels that are vertically or horizontally adjacent, the pixel "distance" is simple. It's a distance of **1**.
|
||
|
||
For pixels that are diagonally adjacent, you can use the Pythagorean theorem of a²+b²=c² to calculate the distance between two diagonal pixels as the square root of **2**, or approximately **1.414**.
|
||
|
||
```
|
||
double
|
||
pixel_dist(int x0, int y0, int x, int y)
|
||
{
|
||
if (((x - x0) == 0) && ((y0 - y) == 1)) {
|
||
return 1.0;
|
||
}
|
||
|
||
if (((y0 - y) == 0) && ((x - x0) == 1)) {
|
||
return 1.0;
|
||
}
|
||
|
||
/* if ( ((y0-y)==1) && ((x-x0)==1) ) { */
|
||
return 1.414;
|
||
/* } */
|
||
}
|
||
```
|
||
|
||
I wrapped the last "if" statement in comments so you can see what the condition is supposed to represent.
|
||
|
||
To measure the circumference, we don't need to examine the entire circle. We can save a little time and effort by working on only the upper left quadrant. This also allows us to know the starting coordinate of the first pixel in the circle; we'll skip the first pixel at 0,239 and instead assume that as our first x0,y0 coordinate in measuring the quarter-circumference.
|
||
|
||
![The program only needs to evaluate the upper left quadrant of the circle.][5]
|
||
|
||
The final program is similar to our "count the pixels" program, but instead measures the tiny distances between pixels in the upper left quadrant of the circle. You may notice that the program counts _down_ the y coordinates, from 238 to 0. This accommodates the assumption that the known starting x0,y0 coordinate in the quarter-circle is 0,239. With that assumption, the program only needs to evaluate the y coordinates between 0 and 238. To estimate the total circumference of the circle, multiply the quarter-measurement by 4:
|
||
|
||
```
|
||
#include <stdio.h>
|
||
#include <graph.h>
|
||
|
||
double
|
||
pixel_dist(int x0, int y0, int x, int y)
|
||
{
|
||
...
|
||
}
|
||
|
||
int
|
||
main()
|
||
{
|
||
double circum;
|
||
int x, y;
|
||
int x0, y0;
|
||
|
||
/* draw a circle */
|
||
|
||
_setvideomode(_VRES16COLOR); /* 640x480 */
|
||
_setcolor(7); /* white */
|
||
_ellipse(_GBORDER, 0, 0, 479, 479);
|
||
|
||
/* calculate circumference, use upper left quadrant only */
|
||
|
||
circum = 0.0;
|
||
|
||
x0 = 0;
|
||
y0 = 479 / 2;
|
||
|
||
for (x = 0; x <= 479 / 2; x++) {
|
||
for (y = (479 / 2) - 1; y >= 0; y--) {
|
||
if (_getpixel(x, y) == 7) {
|
||
circum += pixel_dist(x0, y0, x, y);
|
||
|
||
x0 = x;
|
||
y0 = y;
|
||
|
||
/* highlight the pixel */
|
||
_setcolor(15); /* br white */
|
||
_setpixel(x, y);
|
||
}
|
||
else {
|
||
/* highlight the pixel */
|
||
_setcolor(1); /* blue */
|
||
_setpixel(x, y);
|
||
}
|
||
}
|
||
}
|
||
|
||
circum *= 4.0;
|
||
|
||
/* done */
|
||
|
||
_setvideomode(_DEFAULTMODE);
|
||
|
||
printf("circumference = %f\n", circum);
|
||
puts("diameter = 480");
|
||
printf("pi = c/d = %f\n", circum / 480.0);
|
||
|
||
return 0;
|
||
}
|
||
```
|
||
|
||
This provides a better estimate of the circumference. It's still off by a bit, because measuring a circle using pixels is still a pretty rough approximation, but the final pi calculation is much closer to the expected value of 3.14:
|
||
|
||
```
|
||
circumference = 1583.840000
|
||
diameter = 480
|
||
pi = c/d = 3.299667
|
||
```
|
||
|
||
--------------------------------------------------------------------------------
|
||
|
||
via: https://opensource.com/article/23/3/calculate-pi-counting-pixels
|
||
|
||
作者：[Jim Hall][a]
|
||
选题：[lkxed][b]
|
||
译者：[译者ID](https://github.com/译者ID)
|
||
校对：[校对者ID](https://github.com/校对者ID)
|
||
|
||
本文由 [LCTT](https://github.com/LCTT/TranslateProject) 原创编译，[Linux中国](https://linux.cn/) 荣誉推出
|
||
|
||
[a]: https://opensource.com/users/jim-hall
|
||
[b]: https://github.com/lkxed/
|
||
[1]: https://opensource.com/downloads/guide-using-freedos
|
||
[2]: https://opensource.com/article/21/6/freedos-sixteen-colors
|
||
[3]: https://opensource.com/sites/default/files/2023-03/1000000000000280000001E0F6AC941D0C3A4F04.webp
|
||
[4]: https://opensource.com/sites/default/files/2023-03/1000000000000280000001E01BA6891AE7373404.webp
|
||
[5]: https://opensource.com/sites/default/files/2023-03/1000000000000280000001E09B0AAA422BFA0296.webp |