Algoritmo dell'arco di cerchio di Bresenham

L' arco di trama dell'algoritmo di Bresenham , o punto medio dell'algoritmo di tracciamento dell'arco ( punto medio inglese) consente una complessità algoritmica notevolmente ridotta, disegnare cerchi nell'immagine raster .

Storico

Questo algoritmo, pubblicato da Bresenham in Febbraio 1977, si ispira al suo precedente lavoro sul tracciato di segmenti e al più generale algoritmo di Pitteway sul tracciato di coniche , di cui i cerchi sono un caso speciale.

Spiegazione dell'algoritmo di base nel primo ottante

Un ottavo è sufficiente

Innanzitutto possiamo notare che su una griglia di pixel sono presenti quattro assi di simmetria rispetto al cerchio , due lungo gli assi della matrice e due che rappresentano le bisettrici della cornice centrata sul cerchio. Quindi, avendo calcolato un arco di un settore del segno di riferimento delimitato dagli assi di simmetria, è sufficiente sfruttare la simmetria per posizionare i pixel negli altri sette ottanti.

L'algoritmo di base

Per ragioni di simmetria spiegate in precedenza, l'algoritmo spiegato sarà limitato al secondo ottante (con angolo compreso tra e ) e quindi generalizzato. L'algoritmo partirà quindi dal punto più alto del cerchio e scenderà fino alla prima bisettrice. π2{\ displaystyle {\ frac {\ pi} {2}}}π4{\ displaystyle {\ frac {\ pi} {4}}}

Questa trama procede per iterazione , ogni iterazione attiva un pixel. Immagina di essere in un pixel P e di dover posizionare il pixel successivo. Dato che siamo nel secondo ottante, questo pixel sarà il punto E o il punto F. Il metodo di Bresenham consiste nel valutare se il cerchio di equazione "ideale" passa sopra o sotto il punto M, punto medio del segmento EF per attivare il pixel E o il pixel F. X2+y2-R2=0{\ displaystyle x ^ {2} + y ^ {2} -R ^ {2} = 0}

È quindi necessario calcolare ad ogni iterazione una variabile m tale che . Allora : m=XM2+yM2-R2{\ displaystyle m = {x_ {M}} ^ {2} + {y_ {M}} ^ {2} -R ^ {2}}

• m> 0 ⇒ M sopra il cerchio ideale ⇒ scelta di F ⇒ incremento x, decremento y
• m <0 ⇒ M sotto il cerchio ideale ⇒ scelta di E ⇒ incremento x

Ottimizzazione dell'algoritmo

Per ottimizzare l'algoritmo, calcoliamo ricorsivamente la variabile m. Dimostriamo che (1) 4m=4Xio2+4yio2+8Xio-4yio+5-4R2{\ displaystyle 4m = 4 {x_ {i}} ^ {2} +4 {y_ {i}} ^ {2} + 8x_ {i} -4y_ {i} + 5-4R ^ {2}}

dimostrazione

Passiamo al punto di contatto sulla griglia di pixel e calcoliamo la variabile m. Pio{\ displaystyle P_ {i}}(Xio;yio){\ displaystyle (x_ {i}; y_ {i})}

Allora sappiamo che M ha per coordinate . (Xm=Xio+1;ym=yio-0,5){\ displaystyle (x_ {m} = x_ {i} +1; y_ {m} = y_ {i} -0,5)}

Quindi . m=XM2+yM2-R2=(Xio+1)2+(yio-0,5)2-R2=Xio2+yio2+2Xio-yio+1,25-R2{\ displaystyle m = {x_ {M}} ^ {2} + {y_ {M}} ^ {2} -R ^ {2} = {(x_ {i} +1)} ^ {2} + {( y_ {i} -0.5)} ^ {2} -R ^ {2} = {x_ {i}} ^ {2} + {y_ {i}} ^ {2} + 2x_ {i} -y_ {i} + 1,25-R ^ {2}}

Poiché vogliamo lavorare solo con numeri interi e poiché siamo interessati solo al segno di m, moltiplichiamo l'equazione per 4 e otteniamo .4m=4Xio2+4yio2+8Xio-4yio+5-4R2{\ displaystyle 4m = 4 {x_ {i}} ^ {2} +4 {y_ {i}} ^ {2} + 8x_ {i} -4y_ {i} + 5-4R ^ {2}}  

Modificheremo la variabile m secondo la scelta del pixel E o del pixel F. Denomineremo il vecchio valore di m, e il nuovo valore di m. mio{\ displaystyle m_ {i}}mio+1{\ displaystyle m_ {i + 1}}

• Esso dimostra che se scegliamo E .4mio+1=4mio+8Xio+12=4mio+8Xio+1+4{\ displaystyle 4 m_ {i + 1} = 4 m_ {i} + 8x_ {i} + 12 = 4 m_ {i} + 8x_ {i + 1} +4}

È quindi necessario incrementare di . 4mio{\ displaystyle 4m_ {i}}8Xio+1+4{\ displaystyle 8x_ {i + 1} +4}

dimostrazione

Se scegliamo E, allora . (Xio+1=Xio+1,yio+1=yio){\ displaystyle (x_ {i + 1} = x_ {i} + 1, y_ {i + 1} = y_ {i})}

Tuttavia, secondo l'equazione (1),

4mio+1=4Xio+12+4yio+12+8Xio+1-4yio+1+5-4R2{\ displaystyle 4m_ {i + 1} = 4 {x_ {i + 1}} ^ {2} +4 {y_ {i + 1}} ^ {2} + 8x_ {i + 1} -4y_ {i + 1 } + 5-4R ^ {2}},

pertanto 4mio+1=4(Xio2+2Xio+12)+4yio2+8(Xio+1)-4yio+5-4R2{\ displaystyle 4m_ {i + 1} = 4 ({x_ {i}} ^ {2} + 2x_ {i} + 1 ^ {2}) + 4 {y_ {i}} ^ {2} +8 (x_ {i} +1) -4y_ {i} + 5-4R ^ {2}}

da dove . 4mio+1=4Xio2+4yio2+8Xio-4yio+5-4R2+8Xio+12{\ displaystyle 4m_ {i + 1} = 4 {x_ {i}} ^ {2} +4 {y_ {i}} ^ {2} + 8x_ {i} -4y_ {i} + 5-4R ^ {2 } + 8x_ {i} +12}

Utilizzando il fatto che , 4mio=4Xio2+4yio2+8Xio-4yio+5-4R2{\ displaystyle 4m_ {i} = 4 {x_ {i}} ^ {2} +4 {y_ {i}} ^ {2} + 8x_ {i} -4y_ {i} + 5-4R ^ {2}}

otteniamo .4mio+1=4mio+8Xio+12=4mio+8Xio+1+4{\ displaystyle 4 m_ {i + 1} = 4 m_ {i} + 8x_ {i} + 12 = 4 m_ {i} + 8x_ {i + 1} +4}  

• Esso dimostra che se scegliamo F .(Xio+1=Xio+1,yio+1=yio-1){\ displaystyle (x_ {i + 1} = x_ {i} + 1, y_ {i + 1} = y_ {i} -1)}

È quindi necessario incrementare di . 4mio{\ displaystyle 4m_ {i}}8Xio+1+4-8yio+1{\ displaystyle 8x_ {i + 1} + 4-8y_ {i + 1}}

dimostrazione Ragionamento analogo a quello in cui scegliamo E  

Si deduce quindi il calcolo iterativo di m: con d che è uguale a 0 se scegliamo E, e se scegliamo F. 4mio+1=4mio+8Xio+1+4-d{\ displaystyle 4 m_ {i + 1} = 4 m_ {i} + 8x_ {i + 1} + 4-d}8yio+1{\ displaystyle 8y_ {i + 1}}

Per avviare il calcolo iterativo, lo notiamo quindi . m0=(1)2+(R-0,5)2-R2{\ displaystyle m_ {0} = {(1)} ^ {2} + {(R-0,5)} ^ {2} -R ^ {2}}4m0=5-4R{\ displaystyle 4m_ {0} = 5-4R}

Algoritmo ottimizzato

Algoritmo di trama ottante

procédure tracerOctant (entier rayon, entier x_centre, entier y_centre) déclarer entier x, y, m ; x ← 0 ; y ← rayon ; // on se place en haut du cercle m ← 5 - 4*rayon ; // initialisation Tant que x <= y // tant qu'on est dans le second octant tracerPixel( x+x_centre, y+y_centre ) ; si m > 0 alors // choix du point F y ← y - 1 ; m ← m-8*y ; // correspond au "d" des explications fin si ; x ← x+1 ; m ← m + 8*x+4 ; fin tant que ; fin de procédure ;

La variabile m rappresenta i “4m” del paragrafo precedente, poiché ci interessa solo il segno di 4m ed è uguale a quello di m.

Algoritmo per disegnare l'intero cerchio

procédure tracerCercle (entier rayon, entier x_centre, entier y_centre) déclarer entier x, y, m ; x ← 0 ; y ← rayon ; // on se place en haut du cercle m ← 5 - 4*rayon ; // initialisation Tant que x <= y // tant qu'on est dans le second octant tracerPixel( x+x_centre, y+y_centre ) ; tracerPixel( y+x_centre, x+y_centre ) ; tracerPixel( -x+x_centre, y+y_centre ) ; tracerPixel( -y+x_centre, x+y_centre ) ; tracerPixel( x+x_centre, -y+y_centre ) ; tracerPixel( y+x_centre, -x+y_centre ) ; tracerPixel( -x+x_centre, -y+y_centre ) ; tracerPixel( -y+x_centre, -x+y_centre ) ; si m > 0 alors //choix du point F y ← y - 1 ; m ← m - 8*y ; fin si ; x ← x + 1 ; m ← m + 8*x + 4 ; fin tant que ; fin de procédure ;

Procediamo semplicemente per simmetria nei diversi ottanti.

Note sul metodo Bresenham

Bassa complessità

Abbiamo visto in precedenza che per ogni pixel posizionato la complessità computazionale è stata ridotta a X addizioni, moltiplicazioni Y e confronti Z. L'uso delle usuali funzioni trigonometriche o di una radice quadrata avrebbe richiesto un notevole costo algoritmico in confronto.

Estensioni

Possiamo anche usare il principio di questo algoritmo per disegnare corone ed ellissi .

Limitazioni del metodo

Se disegniamo cerchi concentrici di raggio sempre maggiore, notiamo che non possiamo riempire tutto il piano: ci sono dei "buchi". Questo difetto porta all'uso di altri metodi, come l' algoritmo di disegno del cerchio di Andres .

Esempio di implementazione

In C #

public static List<Point> BresenhamCircle(int xc,int yc,int r) { List<Point> ret = new List<Point>(); int x,y,p; x=0; y=r; ret.Add(new Point(xc+x,yc-y)); p=3-(2*r); for(x=0;x<=y;x++) { if (p<0) { p=(p+(4*x)+6); } else { y-=1; p+=((4*(x-y)+10)); } ret.Add(new Point(xc+x,yc-y)); ret.Add(new Point(xc-x,yc-y)); ret.Add(new Point(xc+x,yc+y)); ret.Add(new Point(xc-x,yc+y)); ret.Add(new Point(xc+y,yc-x)); ret.Add(new Point(xc-y,yc-x)); ret.Add(new Point(xc+y,yc+x)); ret.Add(new Point(xc-y,yc+x)); } return ret; }

Appunti

1. (in) Jack Bresenham, "  Un algoritmo lineare per la visualizzazione digitale incrementale di archi circolari  " , Communications of the ACM , vol.  20, n o  2Febbraio 1977, p.  100-106 ( DOI  10.1145 / 359423.359432 )
2. (in) Michael LV Pitteway, "  Algorithm for Drawing Ellipses gold Hyperbolee with a Digital Plotter  " , The Computer Journal , vol.  10, n o  3,Novembre 1967, p.  282-289 ( ISSN  0010-4620 , OCLC  4653069003 , DOI  10.1093 / comjnl / 10.3.282 ) [PDF]