Líneas y Polígonos
Semestre 02, 2026
El reto de dibujar una línea
No podemos dibujar la recta ideal; debemos elegir el conjunto de píxeles que mejor la aproxime.
Rasterizar
Rasterizar es convertir una figura geométrica (recta, polígono, círculo) en el conjunto de píxeles que la representa en la pantalla.
- Un buen algoritmo debe ser preciso: los píxeles no se separan de la recta real.
- Y eficiente: pocas operaciones por píxel, porque se ejecuta millones de veces.
Tres enfoques, cada uno mejor
Iremos de lo simple y caro a lo rápido y exacto.
Enfoque 1: ecuación de la recta
def linea_ecuacion(x0, y0, x1, y1):
m = (y1 - y0) / (x1 - x0) # pendiente
b = y0 - m * x0 # intercepto
for x in range(x0, x1 + 1):
y = m * x + b # 1 mult + 1 suma por pixel
plot(x, round(y)) # redondeo al pixel mas cercano
Recorremos cada x y calculamos su y con y = m·x + b.
def linea_ecuacion(x0, y0, x1, y1):
m = (y1 - y0) / (x1 - x0) # pendiente
b = y0 - m * x0 # intercepto
for x in range(x0, x1 + 1):
y = m * x + b # 1 mult + 1 suma por pixel
plot(x, round(y)) # redondeo al pixel mas cercano
Recibe los dos extremos de la recta y prepara el cálculo.
def linea_ecuacion(x0, y0, x1, y1):
m = (y1 - y0) / (x1 - x0) # pendiente
b = y0 - m * x0 # intercepto
for x in range(x0, x1 + 1):
y = m * x + b # 1 mult + 1 suma por pixel
plot(x, round(y)) # redondeo al pixel mas cercano
La pendiente mide cuánto sube la línea por cada unidad que avanza en horizontal.
def linea_ecuacion(x0, y0, x1, y1):
m = (y1 - y0) / (x1 - x0) # pendiente
b = y0 - m * x0 # intercepto
for x in range(x0, x1 + 1):
y = m * x + b # 1 mult + 1 suma por pixel
plot(x, round(y)) # redondeo al pixel mas cercano
El intercepto es el valor de la altura cuando la horizontal vale cero. Con la pendiente y el intercepto, la recta queda definida.
def linea_ecuacion(x0, y0, x1, y1):
m = (y1 - y0) / (x1 - x0) # pendiente
b = y0 - m * x0 # intercepto
for x in range(x0, x1 + 1):
y = m * x + b # 1 mult + 1 suma por pixel
plot(x, round(y)) # redondeo al pixel mas cercano
Recorremos la recta avanzando de uno en uno en horizontal, desde el inicio hasta el final.
def linea_ecuacion(x0, y0, x1, y1):
m = (y1 - y0) / (x1 - x0) # pendiente
b = y0 - m * x0 # intercepto
for x in range(x0, x1 + 1):
y = m * x + b # 1 mult + 1 suma por pixel
plot(x, round(y)) # redondeo al pixel mas cercano
Para cada horizontal calculamos su altura. Aquí está la multiplicación de punto flotante que se repite en cada píxel.
def linea_ecuacion(x0, y0, x1, y1):
m = (y1 - y0) / (x1 - x0) # pendiente
b = y0 - m * x0 # intercepto
for x in range(x0, x1 + 1):
y = m * x + b # 1 mult + 1 suma por pixel
plot(x, round(y)) # redondeo al pixel mas cercano
Redondeamos la altura al entero más cercano y encendemos ese píxel. Ese redondeo por píxel es lo que encarece este enfoque.
Enfoque 2: DDA
Algoritmo incremental de rasterización: en lugar de recalcular y = m·x + b desde cero en cada píxel, trabaja con las diferencias (incrementos) entre píxeles consecutivos.
- Al avanzar 1 en
x, layaumenta exactamentem. Entonces basta sumarm, no multiplicar. - Elige como eje dominante el de mayor variación, para no dejar huecos en líneas empinadas.
DDA: el algoritmo
def dda(x0, y0, x1, y1):
dx = x1 - x0
dy = y1 - y0
pasos = max(abs(dx), abs(dy))
x_inc = dx / pasos
y_inc = dy / pasos
x, y = x0, y0
for _ in range(pasos):
plot(round(x), round(y))
x += x_inc
y += y_inc
def dda(x0, y0, x1, y1):
dx = x1 - x0
dy = y1 - y0
pasos = max(abs(dx), abs(dy))
x_inc = dx / pasos
y_inc = dy / pasos
x, y = x0, y0
for _ in range(pasos):
plot(round(x), round(y))
x += x_inc
y += y_inc
dy = y1 - y0
La distancia total en horizontal y en vertical entre el punto inicial y el final.
def dda(x0, y0, x1, y1):
dx = x1 - x0
dy = y1 - y0
pasos = max(abs(dx), abs(dy))
x_inc = dx / pasos
y_inc = dy / pasos
x, y = x0, y0
for _ in range(pasos):
plot(round(x), round(y))
x += x_inc
y += y_inc
El número de pasos es la mayor de las dos distancias: así avanzamos por el eje dominante y no dejamos huecos.
def dda(x0, y0, x1, y1):
dx = x1 - x0
dy = y1 - y0
pasos = max(abs(dx), abs(dy))
x_inc = dx / pasos
y_inc = dy / pasos
x, y = x0, y0
for _ in range(pasos):
plot(round(x), round(y))
x += x_inc
y += y_inc
y_inc = dy / pasos
Cuánto avanza cada eje en un solo paso. Son fracciones: aquí aparece el punto flotante.
def dda(x0, y0, x1, y1):
dx = x1 - x0
dy = y1 - y0
pasos = max(abs(dx), abs(dy))
x_inc = dx / pasos
y_inc = dy / pasos
x, y = x0, y0
for _ in range(pasos):
plot(round(x), round(y))
x += x_inc
y += y_inc
plot(round(x), round(y))
Repetimos esos pasos y pintamos el píxel redondeando la posición actual al entero más cercano.
def dda(x0, y0, x1, y1):
dx = x1 - x0
dy = y1 - y0
pasos = max(abs(dx), abs(dy))
x_inc = dx / pasos
y_inc = dy / pasos
x, y = x0, y0
for _ in range(pasos):
plot(round(x), round(y))
x += x_inc
y += y_inc
y += y_inc
Avanzamos sumando el incremento a la posición. Es solo una suma por paso: por eso DDA es más rápido que la ecuación.
DDA: ventajas y límites
Enfoque 3: Bresenham
Algoritmo de rasterización de líneas que usa únicamente aritmética entera. Nació para controlar un plotter y hoy sigue siendo el estándar en GPUs y librerías gráficas.
- La misma idea sirve para rasterizar círculos (variante del mismo autor).
- Sin flotantes ni redondeo: solo sumas, restas y comparaciones de enteros.
La idea: un término de error
- Recorremos el eje dominante un píxel a la vez.
- En cada columna la recta real cae entre dos píxeles candidatos: el de la misma fila y el de la fila siguiente.
- Un término de error entero acumula qué tan lejos va la recta del píxel elegido.
- Cuando el error cruza un umbral, el otro píxel está más cerca: avanzamos en el eje menor.
Bresenham: inicialización
dx = abs(x1 - x0)
dy = -abs(y1 - y0)
sx = 1 if x0 < x1 else -1
sy = 1 if y0 < y1 else -1
err = dx + dy
Se calcula una sola vez, antes del ciclo.
dx = abs(x1 - x0)
dy = -abs(y1 - y0)
sx = 1 if x0 < x1 else -1
sy = 1 if y0 < y1 else -1
err = dx + dy
dy = -abs(y1 - y0)
Distancias horizontal y vertical. La vertical se guarda negativa para simplificar las comparaciones del ciclo.
dx = abs(x1 - x0)
dy = -abs(y1 - y0)
sx = 1 if x0 < x1 else -1
sy = 1 if y0 < y1 else -1
err = dx + dy
sy = 1 if y0 < y1 else -1
Dirección de avance en cada eje: +1 o -1 según hacia dónde va la recta.
dx = abs(x1 - x0)
dy = -abs(y1 - y0)
sx = 1 if x0 < x1 else -1
sy = 1 if y0 < y1 else -1
err = dx + dy
El término de error arranca en dx + dy. Su signo decidirá, en cada paso, hacia dónde avanzar.
Bresenham: el ciclo
while True:
plot(x0, y0)
if x0 == x1 and y0 == y1:
break
e2 = 2 * err
if e2 >= dy:
err += dy
x0 += sx
if e2 <= dx:
err += dx
y0 += sy
while True:
plot(x0, y0)
if x0 == x1 and y0 == y1:
break
e2 = 2 * err
if e2 >= dy:
err += dy
x0 += sx
if e2 <= dx:
err += dx
y0 += sy
Pintamos el píxel donde estamos ahora mismo.
while True:
plot(x0, y0)
if x0 == x1 and y0 == y1:
break
e2 = 2 * err
if e2 >= dy:
err += dy
x0 += sx
if e2 <= dx:
err += dx
y0 += sy
break
Si el píxel actual es el punto final, terminamos el ciclo.
while True:
plot(x0, y0)
if x0 == x1 and y0 == y1:
break
e2 = 2 * err
if e2 >= dy:
err += dy
x0 += sx
if e2 <= dx:
err += dx
y0 += sy
El doble del error permite comparar contra dx y dy usando solo enteros, sin fracciones.
while True:
plot(x0, y0)
if x0 == x1 and y0 == y1:
break
e2 = 2 * err
if e2 >= dy:
err += dy
x0 += sx
if e2 <= dx:
err += dx
y0 += sy
err += dy
x0 += sx
Si conviene, avanzamos un píxel en horizontal y ajustamos el error sumándole dy.
while True:
plot(x0, y0)
if x0 == x1 and y0 == y1:
break
e2 = 2 * err
if e2 >= dy:
err += dy
x0 += sx
if e2 <= dx:
err += dx
y0 += sy
err += dx
y0 += sy
Si conviene, avanzamos en vertical y ajustamos el error sumándole dx. Si ambas condiciones se cumplen, el avance es diagonal.
Ejemplo: recta de (2, 3) a (8, 5)
Fórmulas generales
dx = |x1 - x0|
dy = -|y1 - y0|
sx = +1 si x0 < x1, si no -1
sy = +1 si y0 < y1, si no -1
err = dx + dy
Sustituyendo los valores
dx = |8 - 2| = 6
dy = -|5 - 3| = -2
sx = +1, sy = +1
err = 6 + (-2) = 4
La recta es más horizontal que vertical (dx > |dy|), así que X es el eje dominante: avanzamos en X en cada paso y solo a veces subimos en Y.
Paso 1: de (2, 3) a (3, 3)
En (2, 3) con err = 4. Pintamos (2, 3) y calculamos e2 = 2·err = 8. (dx = 6, dy = -2)
e2 ≥ dy → 8 ≥ -2 → sí. x pasa a 3 y err = 4 + (-2) = 2.
e2 ≤ dx → 8 ≤ 6 → no. y se queda en 3.
Siguiente píxel: (3, 3), err = 2.
Paso 2: de (3, 3) a (4, 4)
En (3, 3) con err = 2. Pintamos (3, 3) y calculamos e2 = 2·err = 4. (dx = 6, dy = -2)
e2 ≥ dy → 4 ≥ -2 → sí. x pasa a 4 y err = 2 + (-2) = 0.
e2 ≤ dx → 4 ≤ 6 → sí. y pasa a 4 y err = 0 + 6 = 6.
Siguiente píxel: (4, 4), err = 6. Avance diagonal (X e Y).
Paso 3: de (4, 4) a (5, 4)
En (4, 4) con err = 6. Pintamos (4, 4) y calculamos e2 = 2·err = 12. (dx = 6, dy = -2)
e2 ≥ dy → 12 ≥ -2 → sí. x pasa a 5 y err = 6 + (-2) = 4.
e2 ≤ dx → 12 ≤ 6 → no. y se queda en 4.
Siguiente píxel: (5, 4), err = 4.
Traza completa
Valores de err y e2 al pintar cada píxel.
| Paso | (x, y) | err | e2 | Avance |
|---|---|---|---|---|
| 1 | (2, 3) | 4 | 8 | X |
| 2 | (3, 3) | 2 | 4 | X e Y |
| 3 | (4, 4) | 6 | 12 | X |
| 4 | (5, 4) | 4 | 8 | X |
| 5 | (6, 4) | 2 | 4 | X e Y |
| 6 | (7, 5) | 6 | 12 | X |
| 7 | (8, 5) | — | — | fin |
La línea rasterizada
y=5 · · · · · ● ●
y=4 · · ● ● ● · ·
y=3 ● ● · · · · ·
─────────────────────
x= 2 3 4 5 6 7 8
7 píxeles para un dx de 6, todo con aritmética entera.
DDA frente a Bresenham
Incrementos flotantes y redondeo por píxel. Simple de entender, pero más lento y acumula error de redondeo.
Solo enteros, sin redondeo. Más rápido en hardware y sin error acumulado: es el que usan las librerías reales.
Polígonos
Figura cerrada formada por una secuencia de líneas.
Dibujar un polígono
- Un arreglo
[(x0, y0), (x1, y1), ..., (xn, yn)].
- Dibujar una línea (con Bresenham) entre cada par.
- Conectar el último punto con el primero.
Rellenar un polígono
Dibujar el contorno solo enciende el borde. Para pintar el interior hay que decidir qué píxeles quedan dentro de la figura. Existen dos familias clásicas.
Flood fill
Parte de un píxel semilla dentro de la figura y contagia el color de relleno a los vecinos que todavía tienen el color de fondo, hasta chocar con el borde.
- Es exactamente el balde de pintura de programas como Paint.
- Trabaja sobre los píxeles ya pintados, no sobre la geometría del polígono.
- Necesita un punto de partida: una semilla que esté dentro de la figura.
Flood fill: cómo funciona
- Elegir una semilla interior y recordar el color de fondo (viejo) y el de relleno (nuevo).
- Cambiar su color de viejo a nuevo.
- Mirar los 4 vecinos (arriba, abajo, izquierda, derecha). Con 8 vecinos se incluyen las diagonales.
- A cada vecino que aún tenga el color viejo, aplicarle lo mismo. El borde detiene la expansión.
Flood fill: el código
def flood_fill(x, y, viejo, nuevo):
if color(x, y) != viejo:
return
pila = [(x, y)]
while pila:
px, py = pila.pop()
if color(px, py) != viejo:
continue
pintar(px, py, nuevo)
pila += [(px+1, py), (px-1, py),
(px, py+1), (px, py-1)]
Se usa una pila explícita en lugar de recursión, para no desbordar la memoria en figuras grandes. Cada píxel se pinta una sola vez: al sacarlo de la pila se revisa que siga siendo del color viejo antes de pintarlo.
Scanline fill
Rellena la figura fila por fila. Cada fila horizontal es una scanline: para ella se calcula por dónde entra y sale del polígono y se pinta el tramo interior.
- Trabaja sobre la geometría (vértices y aristas), no sobre píxeles ya pintados.
- No necesita semilla: se deduce del propio polígono.
Scanline: cómo funciona
- Para cada fila, hallar dónde cruza las aristas.
- Ordenar esos cruces por su coordenada x.
- Pintar el tramo entre el 1º y 2º cruce, el 3º y 4º, etc.
Cada vez que la fila cruza una arista, alterna entre afuera y adentro. Por eso se pinta entre pares de cruces.
afuera │ ADENTRO │ afuera
───────●━━━━━━━━━●───────
cruce cruce
Scanline: el código
def scanline_fill(poligono):
for y in range(y_min, y_max):
cruces = []
for a, b in aristas(poligono):
if cruza(a, b, y):
cruces.append(x_corte(a, b, y))
cruces.sort()
for i in range(0, len(cruces), 2):
pintar_tramo(cruces[i], cruces[i+1], y)
Por cada fila se juntan y ordenan los cruces con las aristas, y se pinta entre pares. Los vértices y las aristas horizontales requieren cuidado extra para no contar un cruce de más.
Flood fill frente a Scanline
Trabaja sobre píxeles y necesita una semilla. Rellena cualquier forma, pero gasta memoria y visita todos los píxeles: costoso en figuras grandes.
Trabaja sobre la geometría, sin semilla. Más eficiente y es el estándar en rasterizadores y GPUs, aunque más complejo por los casos de vértices.