Algoritmo di generazione del cerchio

Disegnare un cerchio sullo schermo è un po 'complesso che disegnare una linea. Esistono due algoritmi popolari per generare un cerchio:Bresenham’s Algorithm e Midpoint Circle Algorithm. Questi algoritmi si basano sull'idea di determinare i successivi punti necessari per disegnare il cerchio. Parliamo in dettaglio degli algoritmi -

L'equazione del cerchio è $ X ^ {2} + Y ^ {2} = r ^ {2}, $ dove r è il raggio.

Algoritmo di Bresenham

Non è possibile visualizzare un arco continuo sulla visualizzazione raster. Invece, dobbiamo scegliere la posizione del pixel più vicina per completare l'arco.

Dalla seguente illustrazione, puoi vedere che abbiamo messo il pixel nella posizione (X, Y) e ora dobbiamo decidere dove mettere il pixel successivo - in N (X + 1, Y) o in S (X + 1, Y-1).

Questo può essere deciso dal parametro di decisione d.

• Se d <= 0, allora N (X + 1, Y) deve essere scelto come pixel successivo.
• Se d> 0, allora S (X + 1, Y-1) deve essere scelto come pixel successivo.

Algoritmo

Step 1- Ottieni le coordinate del centro del cerchio e del raggio e memorizzale rispettivamente in x, y e R. Porre P = 0 e Q = R.

Step 2 - Impostare il parametro di decisione D = 3 - 2R.

Step 3 - Ripetere il passaggio 8 mentre P ≤ Q.

Step 4 - Chiama Disegna cerchio (X, Y, P, Q).

Step 5 - Incrementa il valore di P.

Step 6 - Se D <0 allora D = D + 4P + 6.

Step 7 - Else Set R = R - 1, D = D + 4 (PQ) + 10.

Step 8 - Chiama Disegna cerchio (X, Y, P, Q).

Draw Circle Method(X, Y, P, Q).

Call Putpixel (X + P, Y + Q).
Call Putpixel (X - P, Y + Q).
Call Putpixel (X + P, Y - Q).
Call Putpixel (X - P, Y - Q).
Call Putpixel (X + Q, Y + P).
Call Putpixel (X - Q, Y + P).
Call Putpixel (X + Q, Y - P).
Call Putpixel (X - Q, Y - P).

Algoritmo del punto medio

Step 1 - Raggio di input r e cerchio centro $ (x_ {c,} y_ {c}) $ e ottenere il primo punto sulla circonferenza del cerchio centrato sull'origine come

(x0, y0) = (0, r)

Step 2 - Calcola il valore iniziale del parametro decisionale come

$ P_ {0} $ = 5/4 - r (Vedere la seguente descrizione per la semplificazione di questa equazione.)

f(x, y) = x2 + y2 - r2 = 0

f(xi - 1/2 + e, yi + 1)
        = (xi - 1/2 + e)2 + (yi + 1)2 - r2 
        = (xi- 1/2)2 + (yi + 1)2 - r2 + 2(xi - 1/2)e + e2
        = f(xi - 1/2, yi + 1) + 2(xi - 1/2)e + e2 = 0

Let di = f(xi - 1/2, yi + 1) = -2(xi - 1/2)e - e2
Thus,

If e < 0 then di > 0 so choose point S = (xi - 1, yi + 1).
di+1    = f(xi - 1 - 1/2, yi + 1 + 1) = ((xi - 1/2) - 1)2 + ((yi + 1) + 1)2 - r2
        = di - 2(xi - 1) + 2(yi + 1) + 1
        = di + 2(yi + 1 - xi + 1) + 1
		  
If e >= 0 then di <= 0 so choose point T = (xi, yi + 1)
   di+1 = f(xi - 1/2, yi + 1 + 1)
       = di + 2yi+1 + 1
		  
The initial value of di is
   d0 = f(r - 1/2, 0 + 1) = (r - 1/2)2 + 12 - r2
      = 5/4 - r {1-r can be used if r is an integer}
		
When point S = (xi - 1, yi + 1) is chosen then
   di+1 = di + -2xi+1 + 2yi+1 + 1
	
When point T = (xi, yi + 1) is chosen then
   di+1 = di + 2yi+1 + 1

Step 3 - Ad ogni $ X_ {K} $ posizione che inizia da K = 0, esegui il seguente test -

If PK < 0 then next point on circle (0,0) is (XK+1,YK) and
   PK+1 = PK + 2XK+1 + 1
Else
   PK+1 = PK + 2XK+1 + 1 – 2YK+1
	
Where, 2XK+1 = 2XK+2 and 2YK+1 = 2YK-2.

Step 4 - Determina i punti di simmetria in altri sette ottanti.

Step 5 - Sposta ogni posizione calcolata dei pixel (X, Y) sul percorso circolare centrato su $ (X_ {C,} Y_ {C}) $ e traccia i valori delle coordinate.

X = X + XC,   Y = Y + YC

Step 6 - Ripetere i passaggi da 3 a 5 fino a quando X> = Y.