Algoritmo de generación de círculos

Dibujar un círculo en la pantalla es un poco complejo que dibujar una línea. Hay dos algoritmos populares para generar un círculo:Bresenham’s Algorithm y Midpoint Circle Algorithm. Estos algoritmos se basan en la idea de determinar los puntos posteriores necesarios para dibujar el círculo. Analicemos los algoritmos en detalle:

La ecuación del círculo es $ X ^ {2} + Y ^ {2} = r ^ {2}, $ donde r es el radio.

Algoritmo de Bresenham

No podemos mostrar un arco continuo en la pantalla ráster. En cambio, tenemos que elegir la posición de píxel más cercana para completar el arco.

En la siguiente ilustración, puede ver que hemos colocado el píxel en la ubicación (X, Y) y ahora debemos decidir dónde colocar el siguiente píxel: en N (X + 1, Y) o en S (X + 1, Y-1).

Esto puede decidirse mediante el parámetro de decisión d.

Si d <= 0, entonces N (X + 1, Y) debe elegirse como siguiente píxel.
Si d> 0, entonces S (X + 1, Y-1) debe elegirse como el siguiente píxel.

Algoritmo

Step 1- Obtenga las coordenadas del centro del círculo y el radio, y guárdelas en x, y y R respectivamente. Establezca P = 0 y Q = R.

Step 2 - Establecer el parámetro de decisión D = 3 - 2R.

Step 3 - Repita hasta el paso 8 mientras P ≤ Q.

Step 4 - Llamar a Draw Circle (X, Y, P, Q).

Step 5 - Incrementar el valor de P.

Step 6 - Si D <0 entonces D = D + 4P + 6.

Step 7 - De lo contrario, establezca R = R - 1, D = D + 4 (PQ) + 10.

Step 8 - Llamar a Draw Circle (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 de punto medio

Step 1 - Radio de entrada r y el centro del círculo $ (x_ {c,} y_ {c}) $ y obtenga el primer punto en la circunferencia del círculo centrado en el origen como

(x₀, y₀) = (0, r)

Step 2 - Calcular el valor inicial del parámetro de decisión como

$ P_ {0} $ = 5/4 - r (Consulte la siguiente descripción para simplificar esta ecuación).

f(x, y) = x² + y² - r² = 0

f(x_i - 1/2 + e, y_i + 1)
        = (x_i - 1/2 + e)² + (y_i + 1)² - r² 
        = (x_i- 1/2)² + (y_i + 1)² - r² + 2(x_i - 1/2)e + e²
        = f(x_i - 1/2, y_i + 1) + 2(x_i - 1/2)e + e² = 0

Let d_i = f(x_i - 1/2, y_i + 1) = -2(x_i - 1/2)e - e²
Thus,

If e < 0 then di > 0 so choose point S = (x_i - 1, y_i + 1).
d_i+1    = f(x_i - 1 - 1/2, y_i + 1 + 1) = ((x_i - 1/2) - 1)² + ((y_i + 1) + 1)² - r²
        = d_i - 2(x_i - 1) + 2(y_i + 1) + 1
        = d_i + 2(y_{i + 1} - x_{i + 1}) + 1
		  
If e >= 0 then di <= 0 so choose point T = (x_i, y_i + 1)
   d_i+1 = f(x_i - 1/2, y_i + 1 + 1)
       = d_i + 2y_i+1 + 1
		  
The initial value of di is
   d₀ = f(r - 1/2, 0 + 1) = (r - 1/2)² + 1² - r²
      = 5/4 - r {1-r can be used if r is an integer}
		
When point S = (x_i - 1, y_i + 1) is chosen then
   d_i+1 = d_i + -2x_i+1 + 2y_i+1 + 1
	
When point T = (x_i, y_i + 1) is chosen then
   d_i+1 = d_i + 2y_i+1 + 1

Step 3 - En cada posición $ X_ {K} $ a partir de K = 0, realice la siguiente prueba -

If P_K < 0 then next point on circle (0,0) is (X_K+1,Y_K) and
   P_K+1 = P_K + 2X_K+1 + 1
Else
   P_K+1 = P_K + 2X_K+1 + 1 – 2Y_K+1
	
Where, 2X_K+1 = 2X_K+2 and 2Y_K+1 = 2Y_K-2.

Step 4 - Determinar los puntos de simetría en otros siete octantes.

Step 5 - Mueva cada posición de píxel de cálculo (X, Y) a la ruta circular centrada en $ (X_ {C,} Y_ {C}) $ y trace los valores de coordenadas.

X = X + X_C,   Y = Y + Y_C

Step 6 - Repita del paso 3 al 5 hasta que X> = Y.

↰ Previous page Next page ↱