Ricerca nel sito web

Calcola pi greco contando i pixel


Buon giorno Pi! Contando i pixel si ottiene la circonferenza di un cerchio?

Per il Pi Day di quest'anno, volevo scrivere un programma per calcolare il pi greco disegnando un cerchio in modalità grafica FreeDOS, quindi contando i pixel per stimare la circonferenza. Ho ingenuamente pensato che questo mi avrebbe dato un'approssimazione di pi greco. Non mi aspettavo di ottenere 3,14, ma pensavo che il valore sarebbe stato un po' vicino a 3,0.

Mi sbagliavo. Stimare la circonferenza di un cerchio contando i pixel necessari per disegnarlo ti darà un risultato sbagliato. Non importa quale risoluzione ho provato, il calcolo finale del pi greco della circonferenza divisa per il diametro era sempre intorno a 2,8.

Non puoi contare i pixel per calcolare il pi greco

Ho scritto un programma FreeDOS utilizzando OpenWatcom C che disegna un cerchio sullo schermo, quindi conta i pixel che compongono quel cerchio. L'ho scritto in FreeDOS perché i programmi DOS possono facilmente entrare in modalità grafica utilizzando la funzione _setvideomode di OpenWatcom. La modalità video _VRES16COLOR mette il display nella risoluzione 640×480 a 16 colori, una comune risoluzione dello schermo "VGA classico". Nella tavolozza DOS standard a 16 colori, il colore 0 è il nero, il colore 1 è il blu, il colore 7 è un bianco a bassa intensità e il colore 15 è un bianco ad alta intensità.

In modalità grafica, puoi utilizzare la funzione _ellipse per disegnare un'ellisse sullo schermo, dalle coordinate x,y iniziali in alto a sinistra alle coordinate x,y finali in basso a destra. Se l'altezza e la larghezza sono uguali, l'ellisse è un cerchio. Tieni presente che in modalità grafica, xey contano da zero, quindi l'angolo in alto a sinistra è sempre 0,0.

(Jim Hall, CC BY-SA 4.0)

Puoi utilizzare la funzione _getpixel per ottenere il colore di un pixel in una coordinata x,y specificata sullo schermo. Per mostrare l'avanzamento del mio programma, ho utilizzato anche la funzione _setpixel per disegnare un singolo pixel in corrispondenza di qualsiasi x,y sullo schermo. Quando il programma ha trovato un pixel che definiva il cerchio, ho cambiato quel pixel in bianco brillante. Per gli altri pixel, ho impostato il colore sul blu.

(Jim Hall, CC BY-SA 4.0)

Con queste funzioni grafiche è possibile scrivere un programma che disegna un cerchio sullo schermo, quindi esegue un'iterazione su tutte le coordinate x,y del cerchio per contare i pixel. Per ogni pixel di colore 7 (il colore del cerchio), aggiungi uno al conteggio dei pixel. Alla fine, puoi utilizzare il conteggio totale dei pixel come stima della circonferenza:

#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;
}

Ma contare i pixel per determinare la circonferenza sottostima la circonferenza effettiva del cerchio. Poiché pi greco è il rapporto tra la circonferenza di un cerchio e il suo diametro, il mio calcolo pi greco era notevolmente inferiore a 3,14. Ho provato diverse risoluzioni video e ho sempre ottenuto un risultato finale di circa 2,8:

pixel count (circumference?) = 1356
diameter = 480
pi = c/d = 2.825000

È necessario misurare la distanza tra i pixel per ottenere pi greco

Il problema con il conteggio dei pixel per stimare la circonferenza è che i pixel sono solo un esempio di un disegno circolare. I pixel sono punti discreti in una griglia, mentre un cerchio è un disegno continuo. Per fornire una stima migliore della circonferenza, devi misurare la distanza tra i pixel e utilizzare la misurazione totale per la circonferenza.

Per aggiornare il programma, è necessario scrivere una funzione che calcoli la distanza tra due pixel qualsiasi: x0,y0 e x,y. Non hai bisogno di un sacco di calcoli o algoritmi fantasiosi qui, solo la consapevolezza che la funzione _ellipse di OpenWatcom disegna solo pixel solidi nel colore impostato per il cerchio. La funzione non tenta di fornire antialiasing disegnando i pixel vicini con un colore intermedio. Ciò ti consente di semplificare i calcoli. In un cerchio, i pixel sono sempre direttamente adiacenti l'uno all'altro: verticalmente, orizzontalmente o diagonalmente.

Per i pixel adiacenti verticalmente o orizzontalmente, la "distanza" dei pixel è semplice. È una distanza di 1.

Per i pixel diagonalmente adiacenti, puoi utilizzare il teorema di Pitagora a²+b²=c² per calcolare la distanza tra due pixel diagonali come radice quadrata di 2, o circa 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;
  /* } */
}

Ho racchiuso l'ultima istruzione "if" nei commenti in modo che tu possa vedere cosa dovrebbe rappresentare la condizione.

Per misurare la circonferenza non è necessario esaminare l'intero cerchio. Possiamo risparmiare un po' di tempo e fatica lavorando solo sul quadrante in alto a sinistra. Questo ci permette anche di conoscere la coordinata iniziale del primo pixel del cerchio; salteremo il primo pixel a 0,239 e lo assumeremo invece come prima coordinata x0,y0 nella misurazione del quarto di circonferenza.

(Jim Hall, CC BY-SA 4.0)

Il programma finale è simile al nostro programma "conta i pixel", ma misura invece le minuscole distanze tra i pixel nel quadrante in alto a sinistra del cerchio. Potresti notare che il programma conta alla rovescia le coordinate y, da 238 a 0. Ciò presuppone che la coordinata x0,y0 iniziale nota nel quarto di cerchio sia 0,239. Con questo presupposto, il programma deve solo valutare le coordinate y comprese tra 0 e 238. Per stimare la circonferenza totale del cerchio, moltiplicare la misura del quarto per 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;
}

Ciò fornisce una stima migliore della circonferenza. È ancora un po' sbagliato, perché misurare un cerchio usando i pixel è ancora un'approssimazione piuttosto approssimativa, ma il calcolo finale del pi greco è molto più vicino al valore atteso di 3,14:

circumference = 1583.840000
diameter = 480
pi = c/d = 3.299667

Articoli correlati: