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

(x0, y0) = (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) = 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 - En cada posición $ X_ {K} $ a partir de K = 0, realice la siguiente prueba -

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 - 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 + XC,   Y = Y + YC

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