Dibujo de Círculos
Juan José Cortés Orozco.
Antonio Muñoz Torres.
Indice
•
•
•
•
Introducción.
Desarrollo Teórico del Dibujo de Círculos.
Algoritmo de Bresenham.
Conclusiones y Otras Técnicas.
Introducción.
El trabajo que se nos encomendó se basa en dibujar un
círculo, conociendo el punto origen y el radio(R). Para ello,
por simplicidad, en todo el desarrollo se considerará una
circunferencia centrada en el origen de coordenadas.
Utilizaremos y veremos en las siguientes diapositivas,
métodos que nos van a ayudar a obtener el resultado deseado,
como la Simetría y el Algoritmo de Bresenham.
Desarrollo Teórico
•
Para obtener todos los puntos de una
circunferencia tenemos la siguiente fórmula:
y R x
2
2
•
Partiendo de aquí, para dibujar ¼ de
circunferencia, se incrementa el valor de X en
pasos de uno en uno desde 0 hasta R y
resolvemos la fórmula sólo para los valores
positivos.
•
Los Otros ¾ de circunferencia se pueden dibujar
por simetría. Lo veremos a continuación
Desarrollo Teórico
(Simetría de la Octava Parte)
•
Si un punto de coordenadas (x,y) pertenece al circulo, podemos obtener de
forma trivial otros siete Puntos que se Obtienen por Simetría.
•
Para Hacer esto utilizamos el mismo método anterior, pero solo para valores
de X comprendidos entre 0 hasta R/ 2 . Este es el punto donde x=y, el seno y
el coseno son iguales y el eje x forma un ángulo de 45 º con el radio dibujado
desde el centro hasta el punto (x,y).
Para Dibujar el punto obtenido y los siete simétricos se utiliza el siguiente
Procedimiento:
•
Circle_Points
Algoritmo de Bresenham
•
•
Bresenham desarrolló un generador incremental de circunferencias. Este algoritmo
genera todos los puntos de un círculo centrado en el origen.
En cada paso el algoritmo selecciona el punto Pi(xi,yi), el cuál es el más cercano a la
verdadera circunferencia y al mismo tiempo hace que el término de error D(Pi) sea mas
cercano a cero.
D(Pi)=(xi2+yi2)-R2
•
La estrategia a seguir es seleccionar el punto más cercano para usar variables de decisión
cuyos valores puedan ser incrementalmente calculados sólo con algunas operaciones
básicas como sumas, restas o cambios de signo.
NOTA:
Debemos tener en cuenta que trabajamos con una matriz de puntos que no es continua, y por ello tenemos que
aproximar lo más posible los puntos a dibujar, con los puntos de la circunferencia real, obtenidos en la aplicación de la
formula.
Algoritmo de Bresenham
•
•
•
Asumimos que Pi ha sido seleccionado en
el paso anterior como el punto más cercano
a la circunferencia real.
En el paso actual, debemos determinar si el
punto mas cercano es Si o Ti.
El término de error para estos puntos será la
diferencia de los cuadrados de las distancias
al origen del punto y de la circunferencia
real.
D(Si)=((Xi-1 + 1)2 + Yi-1) - R2
D(Ti)=((Xi-1 + 1)2 + (Yi-1 – 1)2) - R2
•
•
Si |D(Si)| >= |D(Ti)| , entonces Ti es más
cercano al círculo real que Si y lo tomamos
como un punto de la circunferencia.
Podemos definir di como un término de
error di = |D(Si)| - |D(Ti)|
Algoritmo de Bresenham
•
•
•
•
Vamos a considerar otro termino de error
como di = D(Si) + D(Ti)
Con este nuevo termino de error y observando
la imagen podemos ver que en los casos A y B
tanto Si como Ti quedan dentro de la
circunferencia real, con lo que el término di es
negativo y seleccionaremos el punto Si.
En los casos D y E ocurre al contrario. di
siempre será positivo con lo que tomaremos el
punto Ti
El caso más complejo es el caso C. Aquí Si
queda fuera del círculo, con lo que su término
de error es positivo, mientras Ti queda dentro
del círculo y por tanto con un término de error
negativo. El punto más cercano al círculo será
Ti, si el término de error di es positivo y Si en
caso contrario.
Algoritmo de Bresenham
•
•
Podemos comprobar que la variable de decisión di tal y como la hemos
expresado, requiere el cálculo de varias multiplicaciones y cuadrados, y por el
contrario dijimos anteriormente que el algoritmo sólo calcula unas algunas
operaciones básicas como sumas o restas. A partir de aquí vamos a desarrollar
el algoritmo de Bresenham.
Mediante una serie de manipulaciones algebraicas llegamos a que en el
paso 1, el termino de error es d1=3 – 2 R
Demostración.P0 = (x0,y0) = (0,R)
así S1=(1,R) y T1=(1,(R-1))
D(S1)=(12+R2)-R2=1
D(T1)=(12+(R-1) 2)-R2=1+R2-2R+1-R2=2-2R
d1=D(S1)+D(T1)=1+ 2 + 2R = 3 - 2 R
Algoritmo de Bresenham
•
Como hemos visto, si di es menor que cero elegimos Si como punto a dibujar, y el
siguiente término de error será di+1=di + 4 * Xi-1 + 6
di = ((xi-1 + 1) 2 + y i-12) - R2 +((x i-1 + 1) 2 + (y i-1 - 1) 2) - R2
d i+1 = ((x i-1 + 2) 2 + y i-12) - R2 + ((x i-1 + 2) 2 + (y i-1 - 1) 2) - R2 =
= (x i-12 + 4 x i-1 + 4 + y i-12 - R2) + (x i-12 + 4 x i-1 + 4 + (y i-1 - 1) 2 - R2)
Como
x i-12 + 4 x i-1 + 4 = x i-12 + 2 x i-1 + 1 – 2 x i-1 + 3 = (x i-1 + 1) 2 + 2 x i-1 + 3
Entonces
d i+1 = ((x i-1 + 1) 2 + y i-12 - R2) + 2 x i-1 + 3 + ((x i-1 + 1) 2 + (y i-1-1) 2 - R2)+2x i-1 + 3 =
= D(Si) + 2 x i-1 + 3 + D(Ti) + 2 x i-1 + 3 =
= di + 4 x i-1 + 6
Algoritmo de Bresenham
•
Si por el contrario di es mayor que cero y elegimos Ti, nos quedará que el término de
error es:
di+1 = di + 4 * (Xi+1 – Yi-1) + 10
d i+1 = (x i-1 + 2)2 + (y i-1 - 1) 2 - R2 + (x i-1 + 2) 2 + (y i-1 - 2) 2 - R2 =
= x i-12 + 4x i-1 + 4 + y i-12 – 2 y i-1 + 1 - R2 + x i-12 + 4 x i-1 + 4 + y i-12 – 4 y i-1 +4 - R2=
= (x i-1 + 1) 2 + 2 x i-1 + 3 + y i-12 – 2 y i-1 + 1 - R2 + (x i-1 + 1) 2 + 2 x i-1 + 3 + (y i-1-1) 2 - 2y i-1 + 3 – R2 =
= D(S i) + 2 x i-1 + 3 – 2 y i-1 + 1 + D(T i) + 2 x i-1 + 3 – 2 y i-1 + 3 =
= d i+ 4 x i-1 – 4 y i-1 + 10=
= d i + 4 (x i-1 - yi-1) + 10
Algoritmo de Bresenham
• Este resultado algebraico y el consiguiente algoritmo fueron derivados por
J. Michener por aplicación de la metodología de Bresenham. La expresión para di
es expandida usando las fórmulas de D(Si) y D(Ti). Sustituyendo i-1 por i,
encontramos una expresión para di.1. Entonces la diferencia di – di-1 es formada y
evaluada para cada uno de los posibles movimientos. El siguiente procedimiento
esta basado en este resultado.
Algoritmo de Bresenham
Procedure MICH_CIRCLE (radius,value:integer);
{Se supone el centro del círculo en el origen}
Var x,y,d:integer;
Begin
x:=0;
y:=radius;
d:= d- 3 * radius;
while x<y do begin
Circle_Points (x,y,value);
if d<0
then d:= d + 4 * x + 6
{ Selecciono S}
else begin
d := d + 4 * (x – y) + 10;
{ Selecciono T – decremento de y}
y := y – 1
end
x:=x+1
end {While}
if x = y then Circle_points (x,y,value);
End {Mich_Circle}
Conclusiones y Otras Técnicas.
•
Se han desarrollado otras técnicas para dibujar círculos y demás curvas.
Jordan, Lenon y Holm desarrollaron un eficiente método para curvas en
general, el cual puede ser expresado como f(x,y)=0 y tener continuas
derivadas. Aunque más tarde se demostró que este método tenia ciertas
limitaciones. En concreto casos especiales de algunas curvas que incluyen
secciones cónicas y líneas rectas. Aunque el algoritmo pueda ser simplificado
en esos casos, aún así, genera más carga por iteración que el algoritmo de
Bresenham
Descargar

Dibujo de Circulos