Algoritmo de Bresenham
Por aquella época era común compartir libremente los programas, y en la empresa era normal que otros compañeros dispusieran de copias.
No fue el propio Bresenham quien publicó su algoritmo, sino otros que le pidieron permiso para presentarlo en su nombre en la convención nacional de ACM, en Denver (Colorado) en 1963.
El algoritmo, finalmente ha encontrado un uso masivo en los gráficos de ordenador, debido a su velocidad y sencillez.
En cambio cuando se opera sobre un sistema mapeado (como es la propia representación pixelada) en filas y columnas (cuadriculado), una línea siempre seguirá un trazado imperfecto, ya que la propia línea imaginaria trazada entre dos puntos, (excepto para las líneas horizontales y verticales), siempre cortará los cuadrados por donde pase, dividiendo al punto mínimo en dos áreas de diferente tamaño.
La aproximación del dibujado de los puntos que describen la línea presenta dos claros problemas:
Dados dos puntos que describen el punto inicial y final de la recta, se conoce las medidas básicas de la línea, ancho y alto que abarca la línea.
Aunque 1'5 sea una medida cómoda, trabajar con decimales cuando operamos sobre unidades enteras, es parte del problema.
Al caso conviene considerar un círculo e imaginar el centro como el punto inicial.
Una vez considerado el círculo, se observa que básicamente puede ser subdividido en octantes (8 partes iguales).
Es probable que no alcance la explicación para terminar de entender por completo el algoritmo, pero con el pseudocódigo y un ejemplo paso a paso, viéndolo operar, se acaba de comprender.
El trazado se realiza sobre un bucle, elegido para el eje de mayor medida hallado en el paso previo.
A tales efectos, observando la imagen previa (del círculo con los octantes), se advierte que en función del ángulo que tenga la línea, los valores de incremento (avance) caerán en positivo o negativo tanto para el eje 'x' como al eje 'y'.
La solución de Bresenham, trata sobre cuando aplicar el avance unitario o cero, para el eje de menor distancia, y es la parte que se describe ahora (la explicación viene dada por comodidad y por simplicidad) para un solo octante donde ambas medidas son positivas, es decir para el octante marcado en la figura como n.º 1 (la numeración de los octantes es arbitraria, puede elegirse indistintamente, según convenga al código si se quieren usar numerados)): Sean dX y dY la distancias que separan los puntos extremos de la línea sobre cada eje, y 'e' la relación entre el mayor y el menor (e = dX/dY).
Matemáticamente una circunferencia será definida como el conjunto de puntos localizados a una distancia r en una posición central representada en el plano x,y.
Para los puntos más alejados del centro, estos pueden ser unidos con segmentos de línea recta, para los puntos más cercanos se puede aplicar el tamaño del paso para θ con la expresión 1/r, aprovechando las simetrías, el segundo cuadrante se genera a partir del primero, y el tercer y cuarto de los dos primeros juntos.
Dado que estas condiciones son aplicables a dos píxeles cercanos, tenemos:
