2.2 Representacion y trazo de poligonos

La ecuación de un círculo centrado en el origen es:

x2 + y2 = R2

por lo cual, una primera aproximación para discretizar un círculo es resolver la ecuación

y = ±(R2 - x2)½; ∀ x∈Z, x entre 0 y R1

También se pueden usar las ecuaciones (R cos φ, R sen φ ) con φ creciendo desde 0° a 90°, con esto se reduce el espaciado, pero tampoco es tan eficiente, ya que usa aritmética de punto flotante y llamadas a funciones.

Se puede aprovechar la simetría del círculo para sólo calcular uno de los 8 segmentos de 45º y luego con éste determinar los demás octantes. La siguiente figura y procedimiento resumen el proceso: 

procedure puntos_circulo (x, y:real; valor:integer); 
begin
escribir_pixel(x, y, valor);
escribir_pixel(y, x, valor);
escribir_pixel(y, -x, valor);
escribir_pixel(x, -y, valor);
escribir_pixel(-x, -y, valor);
escribir_pixel(-y, -x, valor);
escribir_pixel(-y, x, valor);
escribir_pixel(-x, y, valor); 
end;

 

Algoritmo de Círculo de Punto Medio 

Se considerará la discretización del segmento de círculo de 45º correspondiente a x = 0 hasta x = y = R/2½, los demás puntos se pueden dibujar con la función puntos_circulo.

Sean  P,  el  pixel  elegido  previamente  en  (xp,  yp);  E  y  SE  los píxeles candidatos (ver figura).

La ecuación de una circunferencia es

F(x, y) = x2 + y2 - R2

y F(x, y) = 0, si el punto (x, y) se encuentra en el círculo; F(x, y) < 0, si (x, y)

está dentro del círculo; y, F(x, y) > 0, si (x, y) está fuera del círculo.

Se define la variable de decisión d en el punto medio entre E y SE.

d = F(xp + 1, yp - ½) = (xp + 1)2 + (yp - ½)2 - R2

Si d < 0 se escoge E y la variable de decisión dnueva será:

dnueva = F(xp + 2, yp - ½) = (xp + 2)2 + (yp - ½)2 - R2

lo cual da que la diferencia incremental es

dnuevo = d + 2 * xp +3

Por lo tanto, se define el incremento por :

∆E = 2 * xp + 3

Si d > 0 se elige SE y la variable de decisión dnuevo será:

dnuevo = F(xp + 2, yp - 3/2) = (xp + 2)2 + (yp - 3/2)2 - R2

como

dnuevo = d + 2 * xp - 2 * yp + 5

Por lo tanto, el incremento está dado por:

∆SE = 2 * xp - 2 * yp + 5

Es decir, en este caso los valores de ∆E y ∆SE son variables, dependen de los puntos seleccionados  (xp, yp) en la iteración previa.

El cálculo de la condición inicial debe considerar que el punto de partida del círculo está en (0, R), por lo tanto, el siguiente punto medio estará en (1, R - ½) y

F(1, R - ½) = 1 + R2 - R + ¼ - R2 = 5/4 - R

Por lo tanto, el programa quedará

               

procedure circulo_punto_medio(radio, valor : integer);

var

x, y : integer;

d : real;

begin

x := 0; y:= radio;

d := 5.0 / 4 - radio;

puntos_circulo (x, y, valor);

while ( y > x) do begin

if ( d < 0) then begin

d := d + x * 2.0 + 3;

x := x +1;

end else begin

d := d + (x - y) * 2.0 + 5;

x := x + 1;

y := y -

end;

end;

end;

puntos_circulo (x, y, valor);

Para que este algoritmo trabaje sólo con enteros se definirá una nueva variable de decisión

h = d - ¼

con lo que se reemplazará la línea 7 del programa a

h := 1 - radio;

En cuanto a la comparación d < 0 se puede reemplazar sin problemas por h < 0, ya que h se inicia y se incrementa en valores enteros.