Algoritmo de línea de Bresenham

La forma pendiente-ordenada al origen de una recta se escribe como

${\displaystyle y=f(x)=mx+b}$

dónde${\displaystyle m}$es la pendiente y${\displaystyle b}$es la intersección con el eje y . Porque esta es una función de solo${\displaystyle x}$, no puede representar una línea vertical. Por lo tanto, sería útil hacer que esta ecuación se escriba como una función de ambos.${\displaystyle x}$y${\displaystyle y}$, poder dibujar líneas en cualquier ángulo. El ángulo (o pendiente) de una línea se puede expresar como "elevación sobre desplazamiento horizontal", o${\displaystyle \Delta y/\Delta x}$. Luego, utilizando manipulación algebraica,

${\displaystyle {\begin{aligned}y&=mx+b\\y&={\frac {\Delta y}{\Delta x}}x+b\\(\Delta x)y&=(\Delta y)x+(\Delta x)b\\0&=(\Delta y)x-(\Delta x)y+(\Delta x)b\end{aligned}}}$

Si esta última ecuación es una función de${\displaystyle x}$y${\displaystyle y}$, se puede escribir como

${\displaystyle f(x,y):=Ax+By+C=0}$

donde las constantes son

• ${\displaystyle A=\Delta y=y_{1}-y_{0}}$
• ${\displaystyle B=-\Delta x=-(x_{1}-x_{0})}$
• ${\displaystyle C=(\Delta x)b=(x_{1}-x_{0})b}$

La línea se define entonces para algunas constantes.${\displaystyle A}$,${\displaystyle B}$, y${\displaystyle C}$en cualquier lugar${\displaystyle f(x,y)=0}$. Es decir, para cualquier${\displaystyle (x,y)}$no en la línea,${\displaystyle f(x,y)\neq 0}$. Esta forma involucra solo números enteros si${\displaystyle x}$y${\displaystyle y}$son números enteros, ya que las constantes${\displaystyle A}$,${\displaystyle B}$, y${\displaystyle C}$se definen como números enteros.

Como ejemplo, la línea${\textstyle y={\frac {1}{2}}x+1}$entonces esto podría escribirse como${\displaystyle f(x,y)=x-2y+2}$El punto (2,2) está en la línea

${\displaystyle f(2,2)=x-2y+2=(2)-2(2)+2=2-4+2=0}$

y el punto (2,3) no está en la línea

${\displaystyle f(2,3)=(2)-2(3)+2=2-6+2=-2}$

y tampoco lo es el punto (2,1)

${\displaystyle f(2,1)=(2)-2(1)+2=2-2+2=2}$

Observe que los puntos (2,1) y (2,3) están en lados opuestos de la línea y${\displaystyle f(x,y)}$se evalúa como positivo o negativo. Una línea divide un plano en dos mitades y el semiplano que tiene un valor negativo${\displaystyle f(x,y)}$Se puede decir que una mitad es el semiplano negativo, y la otra mitad, el semiplano positivo. Esta observación es muy importante para el resto de la deducción.

El punto de partida está en la línea

${\displaystyle f(x_{0},y_{0})=0}$

únicamente porque la línea está definida para comenzar y terminar en coordenadas enteras (aunque es totalmente razonable querer dibujar una línea con puntos finales no enteros).

Teniendo en cuenta que la pendiente es como máximo${\displaystyle 1}$, ahora se plantea el problema de si el siguiente punto debería estar en${\displaystyle (x_{0}+1,y_{0})}$o${\displaystyle (x_{0}+1,y_{0}+1)}$. Quizás intuitivamente, el punto debería elegirse en función de cuál esté más cerca de la línea en${\displaystyle x_{0}+1}$Si está más cerca del primero, entonces incluya el primer punto en la línea; si está más cerca del segundo, entonces incluya el segundo. Para responder a esto, evalúe la función de línea en el punto medio entre estos dos puntos:

${\displaystyle f(x_{0}+1,y_{0}+{\tfrac {1}{2}})}$

Si el valor de esto es positivo, entonces la línea ideal está por debajo del punto medio y más cerca del punto candidato.${\displaystyle (x_{0}+1,y_{0}+1)}$; es decir, la coordenada y debería aumentar. De lo contrario, la línea ideal pasa por o por encima del punto medio, y la coordenada y debería permanecer igual; en cuyo caso el punto${\displaystyle (x_{0}+1,y_{0})}$se elige. El valor de la función de línea en este punto medio es el único determinante de qué punto debe elegirse.

La imagen adjunta muestra el punto azul (2,2), elegido para estar sobre la línea junto con dos puntos candidatos en verde: (3,2) y (3,3). El punto negro (3, 2,5) es el punto medio entre los dos puntos candidatos.

Alternativamente, se puede usar la diferencia entre puntos en lugar de evaluar f(x,y) en los puntos medios. Este método alternativo permite realizar operaciones aritméticas solo con números enteros, lo cual generalmente es más rápido que usar aritmética de punto flotante . Para derivar el otro método, defina la diferencia de la siguiente manera:

${\displaystyle D_{i}=f(x_{i}+1,y_{i}+{\tfrac {1}{2}})-f(x_{0},y_{0})}$

Para la primera decisión, esta formulación es equivalente al método del punto medio ya que${\displaystyle f(x_{0},y_{0})=0}$en el punto de partida. Simplificando esta expresión se obtiene:

${\displaystyle {\begin{array}{rclcl}D_{0}&=&\left[A(x_{0}+1)+B\left(y_{0}+{\frac {1}{2}}\right)+C\right]&-&\left[Ax_{0}+By_{0}+C\right]\\&=&\left[Ax_{0}+By_{0}+C+A+{\frac {1}{2}}B\right]&-&\left[Ax_{0}+By_{0}+C\right]\\&=&A+{\frac {1}{2}}B=\Delta y-{\frac {1}{2}}\Delta x\end{array}}}$

Al igual que con el método del punto medio, si${\displaystyle D_{0}}$es positivo, entonces elige${\displaystyle (x_{0}+1,y_{0}+1)}$, de lo contrario, elige${\displaystyle (x_{0}+1,y_{0})}$.

Si${\displaystyle (x_{0}+1,y_{0})}$se elige, el cambio en${\displaystyle D_{i}}$será:

${\displaystyle {\begin{array}{lclcl}\Delta D&=&f(x_{0}+2,y_{0}+{\tfrac {1}{2}})-f(x_{0}+1,y_{0}+{\tfrac {1}{2}})&=&A&=&\Delta y\\\end{array}}}$

Si${\displaystyle (x_{0}+1,y_{0}+1)}$se elige el cambio en${\displaystyle D_{i}}$será:

${\displaystyle {\begin{array}{lclcl}\Delta D&=&f(x_{0}+2,y_{0}+{\tfrac {3}{2}})-f(x_{0}+1,y_{0}+{\tfrac {1}{2}})&=&A+B&=&\Delta y-\Delta x\end{array}}}$

Si el nuevo D es positivo entonces${\displaystyle (x_{0}+2,y_{0}+1)}$se elige, de lo contrario${\displaystyle (x_{0}+2,y_{0})}$Esta decisión puede generalizarse acumulando el error en cada punto subsiguiente.

Ya se ha realizado toda la derivación del algoritmo. Un problema de rendimiento radica en el factor 1/2 del valor inicial de D. Dado que todo esto se refiere al signo de la diferencia acumulada, se puede multiplicar todo por 2 sin consecuencias.

Esto da como resultado un algoritmo que utiliza únicamente aritmética de enteros.

trazarLínea(x0, y0, x1, y1) dx = x1 - x0 dy = y1 - y0 D = 2*dy - dx y = y0 para x desde x0 hasta x1 trazar(x, y) si D > 0 y = y + 1 D = D + (2 * (dy - dx)) demás D = D + 2*dy fin si

Ejecutando este algoritmo para${\displaystyle f(x,y)=x-2y+2}$Desde (0,1) hasta (6,4) se obtienen las siguientes diferencias con dx=6 y dy=3:

D=2*3-6=0 Recorrer en bucle desde 0 hasta 6 * x=0: plot(0, 1) , D≤0: D=0+6=6 * x=1: plot(1, 1) , D>0: D=6-12=-6, y=1+1=2, D=-6+6=0 * x=2: plot(2, 2) , D≤0: D=0+6=6 * x=3: plot(3, 2) , D>0: D=6-12=-6, y=2+1=3, D=-6+6=0 * x=4: plot(4, 3) , D≤0: D=0+6=6 * x=5: plot(5, 3) , D>0: D=6-12=-6, y=3+1=4, D=-6+6=0 * x=6: plot(6, 4) , D≤0: D=0+6=6

El resultado de esta gráfica se muestra a la derecha. La gráfica se puede visualizar trazando líneas en la intersección (círculos azules) o rellenando cuadrados de píxeles (cuadrados amarillos). En ambos casos, la gráfica es la misma.

Sin embargo, como se mencionó anteriormente, esto solo funciona para el octante cero, es decir, líneas que comienzan en el origen con una pendiente entre 0 y 1 donde x aumenta exactamente en 1 por iteración e y aumenta en 0 o 1.

El algoritmo se puede extender para cubrir pendientes entre 0 y -1 comprobando si y necesita aumentar o disminuir (es decir, dy < 0).

plotLineLow(x0, y0, x1, y1) dx = x1 - x0 dy = y1 - y0 yi = 1 si dy < 0 yi = -1 dy = -dy fin si D = (2 * dy) - dx y = y0 para x desde x0 hasta x1 trazar(x, y) si D > 0 y = y + yi D = D + (2 * (dy - dx)) demás D = D + 2*dy fin si

Al intercambiar los ejes x e y, se puede escribir una implementación para pendientes pronunciadas positivas o negativas como:

plotLineHigh(x0, y0, x1, y1) dx = x1 - x0 dy = y1 - y0 xi = 1 si dx < 0 xi = -1 dx = -dx fin si D = (2 * dx) - dy x = x0 para y desde y0 hasta y1 trazar(x, y) si D > 0 x = x + xi D = D + (2 * (dx - dy)) demás D = D + 2*dx fin si

Una solución completa necesitaría detectar si x1 > x0 o y1 > y0 e invertir las coordenadas de entrada antes de dibujar, por lo tanto

trazarLínea(x0, y0, x1, y1) si abs(y1 - y0) < abs(x1 - x0) si x0 > x1 plotLineLow(x1, y1, x0, y0) demás plotLineLow(x0, y0, x1, y1) fin si si no si y0 > y1 plotLineHigh(x1, y1, x0, y0) demás plotLineHigh(x0, y0, x1, y1) fin si fin si

En las implementaciones de bajo nivel que acceden directamente a la memoria de vídeo, lo habitual es que los casos especiales de líneas verticales y horizontales se traten por separado, ya que pueden optimizarse en gran medida.

Algunas versiones utilizan los principios de Bresenham de error incremental entero para realizar todos los trazados de líneas octantes, equilibrando el error positivo y negativo entre las coordenadas x e y. ^{[ 3 ]}

trazarLínea(x0, y0, x1, y1) dx = abs(x1 - x0) sx = x0 < x1 ? 1 : -1 dy = -abs(y1 - y0) sy = y0 < y1 ? 1 : -1 error = dx + dy mientras que es cierto trazar(x0, y0) e2 = 2 * error si e2 >= dy si x0 == x1 salir error = error + dy x0 = x0 + sx fin si si e2 <= dx si y0 == y1 salir error = error + dx y0 = y0 + sy fin si fin mientras