Algoritmo de la linea del punto medio de breseham

ALGORITMO DE LA LINEA DEL PUNTO MEDIO DE BRESEHAM
Una extension al algoritmo de Bresenham es la técnica del punto medio (midpoint technique).
Para líneas y círculos de enteros, la formulación de punto medio, como la muestra Van Aken (1985), se reduce a laformulación de Bresenham y por lo tanto se generan los mismos pixeles.
Bresenham (1977) mostró que este algoritmo de línea y circulo deenteros proveen la mejor aproximación a líneasy círculos verdaderos al minimizar el error (distancia) a las primitivas reales.
Se asume que la pendiente de la línea es entre 0 y 1.
Otras pendientes se pueden manejar como reflexiones sobre ejes principales.
Se define a (x0,y0) como el extremo inferior izquierdo y (x1,y1) como el extremo superior derecho.

Consideremos la siguiente figura.

PIXELSIGUIENTE
M
E
NE
P


yP+1

yP

xP+1
xP

Asumimos que se ha seleccionado el pixel P en (xp,yp) y ahora se debe escoger entre el pixel de un incremento a la
derecha (pixel del este, E) o el pixel unincremento para la derecha y otro para arriba (pixel del noreste, NE).
Si Q es el punto de intersección de la línea real con la columna x = xp + 1.
En la formulación de Bresenham, la diferencia entre las distancias verticales de E y NE a Q se computan, y el signo de la diferencia, p, se usa para seleccionar el pixel cuya distancia de Q sea menor como la mejor aproximación a la línea real.
En laformulación del punto medio, se observa de que lado de la línea el punto medio M esta.
Es fácil ver, si el punto medio esta sobre la línea real, el pixel E esta mas cercano a la línea; si el punto medio esta debajo de la línea real, el pixel NE es mas cercano a la línea.
La línea puede pasar entre E y NE o ambos pixeles están de un lado de la línea, pero en cualquiera de los casos, la prueba delpunto medio selecciona el pixel mas cercano.
También, el error, o sea, la distancia vertical entre el pixel escogido y la línea real, siempre es £1/2.
La línea se representa con una función implícita (esta representación se extiende muy bien para la formulación decírculos) con coeficientes A, B, y C:
f(x,y) = Ax + By + C = 0
Si Dy = y1 - y0, y Dx = x1 - x0, la ecuación de la línea tiene la formade
y = (Dy / Dx) x + b
Por lo tanto
f(x,y) = Dy x - Dx y + b Dx = 0
donde A = Dy, B = - Dx, y C = b Dx
(Es importante para este algoritmo que A > 0, lo cual se logra ya que se escogió Dy > 0.)
Es fácil de verificar que:
1. Un punto en la línea está representado por: f(x,y) = 0.
2. Un punto debajo de la línea está representado por valores positivos, o sea: f(x,y) > 0.
3. Un puntoencima de la línea está representado por valores negativos, o sea: f(x,y) < 0.
Esto se puede demostrar de la siguiente forma, para D y > 0 y Dx > 0:
Si tomamos cualquier punto (x,y) sobre la línea, tenemos:
f(x,y) = Dy x - Dx y + b Dx = 0
Si tomamos un punto cualquiera ys y la misma coordenada anterior de x, tenemos:
f(x, ys) = Dy x - Dx ys + b Dx = k
donde k es alguna valorresultante de aplicar la nueva coordenada a la ecuación de la línea. (k = 0 solo si el punto está sobre la línea.)
Si restamos estas dos ecuaciones, tenemos:
f(x, ys) - f(x,y) = (Dy x - Dx ys + b Dx) - (Dy x - Dx y + b Dx) = k
lo cual es equivalente a:
- Dx ys+ Dx y = k
- ys+ y = k/Dx
Esto indica que pueden existir dos casos:
1. Si - ys+ y > 0 entonces k/Dx > 0, o sea,si y > ys entonces k/Dx > 0, y un punto debajo de la línea corresponde a un valor positivo de k.
2. Si - ys+ y < 0 entonces k/Dx < 0, o sea, si y < ys entonces k/Dx < 0, y un punto encima de la línea corresponde a un valor negativo de k.
Para aplicar el criterio del punto medio, solo se necesita computar f(M) = f(xp+1,yp+1/2) y probar su signo.
Como la decision se basa en el...