Algoritmo De Punto Medio

Algoritmo del Punto Medio

El Algoritmo del Punto Medio fue ideado por Breshenhan en 1965. Su principal ventaja con respecto a otros métodos utilizados para el dibujo de líneas es su rapidez a la hora de calcular los pixels que debemos pintar cuando estamos dibujando una línea.

Esta rapidez de la que hablamos se debe a que es un algoritmo incremental en el que además solo trabajamos con enteros por lo que no tenemos que hacer ningún tipo de redondeo.

Lo que hace este algoritmo es utilizar una variable de decisión que le indicará cual es el siguiente pixel que tiene que pintar. Esta variable la llamaremos "d" y cada vez que pintemos un pixel se verá incrementada en un valor fijo que denominaremos incremento. Veamos esto con un pequeño ejemplo. Supongamos la siguiente situación:

En la figura que tenemos arriba estamos intentando pintar la línea L y el último pixel que hemos pintado es P0. A la hora de elegir el siguiente pixel a pintar tenemos 2 posibilidades: P1 y P2. Pues bien, según elijamos P1 o P2, a la variable de decisión "d" le sumaremos un valor u otro. Pero, ¿de dónde sale ese valor que le tenemos que sumar a "d"? y ¿cómo utilizamos la variable de decisión "d" a la hora de elegir entre P1 y P2?. Eso es lo que vamos a ver ahora.

Usaremos la ecuación implícita de la recta F(x, y) = ax + by +c, teniendo en cuenta lo siguiente:

- Si F(x, y) = 0, entonces el punto (x, y) pertenece a la recta.

- Si F(x, y) < 0, entonces el punto (x, y) está por encima de la recta.

- Si F(x, y) > 0, entonces el punto (x, y) está por debajo de la recta.

¿Cuál será nuestra variable de decisión?

Nuestra variable de decisión "d" será F(M), siendo M el punto medio entre P1 y P2.

¿Cómo utilizamos la variable de decisión "d" para elegir entre P1 y P2?

- Si d > 0, entonces M está por debajo de la recta L. Esto implica que el punto P1 está más cerca de la recta que P2, lo que nos lleva a elegirlo como próximo punto a pintar.

- Si d < 0, estaremos en el caso contrario al anterior, lo que nos lleva a elegir P2 como siguiente punto a pintar.

- Si d = 0, da igual el punto que elijamos, si bien debemos mantener la elección cada vez que se nos plantee el mismo caso.

En este ejemplo hemos considerado el octante E - NE, con lo cual P1 se refiere al píxel que esta al NE y P2 al que se encuentra al E.

El cálculo de los incrementos y las d iniciales se muestran en:

INTRODUCCIÓN

El algoritmo del Punto Medio es un método recursivo que fue aplicado al movimiento browniano normal en 1920 por N.Wiener. Es una extensión del método de Von Koch y aparece en la mayoría de los ejemplos de fractales descritos por Mandelbrot. Esta forma de computar gráficos ha sido ampliamente divulgada por Fournier, Fussel,y Carpenter.

Se considera la estimación aproximada a un simple mfB VH(t), Si por ejemplo VH(0)=0, entonces los puntos para t=1 y t=-1 son elegidos como muestras de una variable gaussiana aleatoria con varianza ² que satisfacer, se puede definir el algoritmo del Punto Medio como:

VH(±½) = 0.5 [ VH(0) + VH(±1) ] + 1

Donde 1 es una variable gaussiana aleatoria con media cero y varianza 1² que es determinada por la condición de que los incrementos desde 0 a ±1/2 debe satisfacer la siguiente relación:

12 = 2/22H – 1/4 var [ VH(1) ] = (2/22H) [1 – 22H-2]

ALGORITMO

Este algoritmo genera nuevos puntos entre dos puntos iniciales, estos nuevos puntos los generará utilizando una variable aleatoria Gaussiana la cual la sumara al punto medio de los puntos iniciales, en cada etapa del algoritmo se obtendrán nuevos puntos, a partir de los cuales se puede aplicar de nuevo el algoritmo.

Si el proceso es realizado en tiempos t, entre 0 y 1, entonces se deben inicializar VH(0) = 0 y seleccionar VH(1) como una muestra de variable aletoria de Gauss con media cero y varianza 2.

VH(½) va a ser la media de VH(0) y VH(1) más una variable aleatoria Gaussiana D1 con media cero y varianza 12. Entonces

VH(½) – VH(0) = ½ ((VH(1) – VH(0)) + D1

En la segunda etapa

VH(±¼) = ½ [ VH(0) + VH(±½)] + 2

Donde 2 tiene como varianza

22 = 2/42H – 1/4 var [ VH(½) ] = (2/42H) [1 – 22H-2]

En la etapa n-ésima la medida de la distancia ha decrecido a 1/2n y la variable aleatoria gaussiana n es sumada a los puntos medios de la etapa n-1 con varianza

n2 =(2/(2n)2H )[1 – 22H-2]

Una vez que un punto ti ha sido

...