IV. ALGORITMO PUNTO MEDIO DE LA CIRCUNFERENCIA

Este algoritmo consiste en determinar el píxel más cercano a la circunferencia
• Consideremos el centro del círculo en (0,0)
• Comenzaremos en el punto (0,R) e iremos desde
x=0 hasta x=y, donde la pendiente va de 0 a -1
• Sólo pintaremos el primer octante
• Sea la función:
f(x,y) = x2 + y2 – R2
• Este test lo ejecutaremos en los puntos medios
entre los pixels que hay que decidir
<> (x,y) está dentro
= 0 -> (x,y) está sobre la circunferencia> 0 -> (x,y) está fuera


Supongamos ya dibujado el pixel (xk, yk)
pk = f (xk + 1, yk – ½) = (xk + 1)2 + (yk – ½)2 – R2
pk+1 = f (xk+1 + 1, yk+1 – ½) = (xk+1 + 1)2 + (yk+1 – ½)2 – R2
pk+1 = pk + 2xk+1 + 1 + (y2k+1–y2k) – (yk+1–yk)
0 ó 1 dependiendo del signo de pk
• Por lo tanto:
• Si pk <> pk+1 = pk + 2xk+1 + 1 -> hay que pintar el pixel (xk+1, yk)
• Si pk > 0 -> pk+1 = pk + 2xk+1 - 2yk+1 + 1 -> hay que pintar el pixel (xk+1, yk-1)
• Empezamos en el punto (0, R). ¿Cuánto vale p0?
p0 = f (1, R-1/2) =… = 5/4 – R -> no es entero!
Sin embargo, da igual. Podemos redondearlo, porque todos los incrementos son enteros,
y sólo queremos utilizar el signo de pk, y no su valor