Andrés Cruz Chipol
Tarea 1: Algoritmo para el trazo de una línea en cualquier sentido
Fecha de entrega: jueves 11 de septiembre, 2025
1. Análisis de casos
Analizaremos el algoritmo para el trazo de una línea en cualquier sentido. Tenemos la representación de dos puntos extremos: A(x1, y1) y B(x2, y2). Este algoritmo utiliza solamente enteros, evitando operaciones costosas. Partimos del punto A, avanzando de acuerdo a la pendiente calculada con la diferencial de x y y. Se tienen 16 casos posibles, en los 8 octantes, como se muestra en el diagrama.
1.1 Diagrama para visualizar todos los casos
2. Tabla de cada caso (Cómo detectarlo)
| Caso | Descripción | Signos (dx, dy) | Condición Teórica | Pendiente (m) | Eje Dominante y Acción Principal |
|---|---|---|---|---|---|
| 1 | Horizontal → | +, 0 |
dy = 0 |
m = 0 |
Iterar sobre X (Incrementar X) |
| 2 | Octante 1 | ++ |
|dx| > |dy| |
0 < m < 1 |
Eje X domina: Iterar sobre X, decidir Y |
| 3 | Diagonal ↘ | ++ |
|dx| = |dy| |
m = 1 |
Iterar en ambos (Incrementar X e Y) |
| 4 | Octante 2 | ++ |
|dy| > |dx| |
m > 1 |
Eje Y domina: Iterar sobre Y, decidir X |
| 5 | Vertical ↑ | 0, + |
dx = 0 |
Indefinida |
Iterar sobre Y (Incrementar Y) |
| 6 | Octante 3 | -+ |
|dy| > |dx| |
m < -1 |
Eje Y domina: Iterar sobre Y, decidir X |
| 7 | Diagonal ↖ | -+ |
|dx| = |dy| |
m = -1 |
Iterar en ambos (Decrementar X, Incrementar Y) |
| 8 | Octante 4 | -+ |
|dx| > |dy| |
-1 < m < 0 |
Eje X domina: Iterar sobre X, decidir Y |
| 9 | Horizontal ← | -, 0 |
dy = 0 |
m = 0 |
Iterar sobre X (Decrementar X) |
| 10 | Octante 5 | -- |
|dx| > |dy| |
0 < m < 1 |
Eje X domina: Iterar sobre X, decidir Y |
| 11 | Diagonal ↙ | -- |
|dx| = |dy| |
m = 1 |
Iterar en ambos (Decrementar X e Y) |
| 12 | Octante 6 | -- |
|dy| > |dx| |
m > 1 |
Eje Y domina: Iterar sobre Y, decidir X |
| 13 | Vertical ↓ | 0, - |
dx = 0 |
Indefinida |
Iterar sobre Y (Decrementar Y) |
| 14 | Octante 7 | +- |
|dy| > |dx| |
m < -1 |
Eje Y domina: Iterar sobre Y, decidir X |
| 15 | Diagonal ↘ | +- |
|dx| = |dy| |
m = -1 |
Iterar en ambos (Incrementar X, Decrementar Y) |
| 16 | Octante 8 | +- |
|dx| > |dy| |
-1 < m < 0 |
Eje X domina: Iterar sobre X, decidir Y |
3. Código en Python
import sys
n = len(sys.argv)
if n != 5:
print("Args: x1 y1 x2 y2")
sys.exit(1)
x1 = int(sys.argv[1])
y1 = int(sys.argv[2])
x2 = int(sys.argv[3])
y2 = int(sys.argv[4])
dx = x2 - x1
dy = y2 - y1
x = x1
y = y1
print(x, y)
# Caso 1: Octante 0 (pendiente 0, horizontal →)
if dy == 0 and dx > 0:
while x < x2:
x += 1
print(x, y)
# Caso 2: Octante 1 (0 < m < 1)
elif dx > 0 and dy > 0 and dx > dy:
d = 2*dy - dx
dE = 2*dy
dNE = 2*(dy - dx)
while x < x2:
if d < 0:
d += dE
x += 1
else:
d += dNE
x += 1
y += 1
print(x, y)
# Caso 3: Octante 1 bis (m = 1 diagonal ↘)
elif dx > 0 and dy > 0 and dx == dy:
while x < x2:
x += 1
y += 1
print(x, y)
# Caso 4: Octante 2 (m > 1)
elif dx > 0 and dy > 0 and dy > dx:
d = 2*dx - dy
dE = 2*dx
dNE = 2*(dx - dy)
while y < y2:
if d < 0:
d += dE
y += 1
else:
d += dNE
x += 1
y += 1
print(x, y)
# Caso 5: Vertical ↑
elif dx == 0 and dy > 0:
while y < y2:
y += 1
print(x, y)
# Caso 6: Octante 3 (m > 1)
elif dx < 0 and dy > 0 and dy > abs(dx):
d = 2*abs(dx) - dy
dE = 2*abs(dx)
dNE = 2*(abs(dx) - dy)
while y < y2:
if d < 0:
d += dE
y += 1
else:
d += dNE
x -= 1
y += 1
print(x, y)
# Caso 7: Octante 3 bis (m = 1 diagonal ↖)
elif dx < 0 and dy > 0 and abs(dx) == dy:
while y < y2:
x -= 1
y += 1
print(x, y)
# Caso 8: Octante 4 (0 < m < 1)
elif dx < 0 and dy > 0 and abs(dx) > dy:
d = 2*dy - abs(dx)
dE = 2*dy
dNE = 2*(dy - abs(dx))
while x > x2:
if d < 0:
d += dE
x -= 1
else:
d += dNE
x -= 1
y += 1
print(x, y)
# Caso 9: Horizontal ←
elif dy == 0 and dx < 0:
while x > x2:
x -= 1
print(x, y)
# Caso 10: Octante 5 (0 < m < 1)
elif dx < 0 and dy < 0 and abs(dx) > abs(dy):
d = 2*abs(dy) - abs(dx)
dE = 2*abs(dy)
dNE = 2*(abs(dy) - abs(dx))
while x > x2:
if d < 0:
d += dE
x -= 1
else:
d += dNE
x -= 1
y -= 1
print(x, y)
# Caso 11: Octante 5 bis (m = 1 diagonal ↙)
elif dx < 0 and dy < 0 and abs(dx) == abs(dy):
while x > x2:
x -= 1
y -= 1
print(x, y)
# Caso 12: Octante 6 (m > 1)
elif dx < 0 and dy < 0 and abs(dy) > abs(dx):
d = 2*abs(dx) - abs(dy)
dE = 2*abs(dx)
dNE = 2*(abs(dx) - abs(dy))
while y > y2:
if d < 0:
d += dE
y -= 1
else:
d += dNE
x -= 1
y -= 1
print(x, y)
# Caso 13: Vertical ↓
elif dx == 0 and dy < 0:
while y > y2:
y -= 1
print(x, y)
# Caso 14: Octante 7 (m > 1)
elif dx > 0 and dy < 0 and abs(dy) > dx:
d = 2*dx - abs(dy)
dE = 2*dx
dNE = 2*(dx - abs(dy))
while y > y2:
if d < 0:
d += dE
y -= 1
else:
d += dNE
x += 1
y -= 1
print(x, y)
# Caso 15: Octante 7 bis (m = -1 diagonal ↗)
elif dx > 0 and dy < 0 and dx == abs(dy):
while x < x2:
x += 1
y -= 1
print(x, y)
# Caso 16: Octante 8 (−1 < m < 0)
elif dx > 0 and dy < 0 and dx > abs(dy):
d = 2*abs(dy) - dx
dE = 2*abs(dy)
dNE = 2*(abs(dy) - dx)
while x < x2:
if d < 0:
d += dE
x += 1
else:
d += dNE
x += 1
y -= 1
print(x, y)
print()
4. Prueba de código y gráfica de salida
import numpy as np
import matplotlib.pyplot as plt
def leer(f):
lineas = []
current = []
with open(f, 'r') as file:
for line in file:
line = line.strip()
if line == "":
if current:
lineas.append(np.array(current))
current = []
else:
try:
x, y = map(int, line.split())
current.append([x, y])
except:
continue
if current:
lineas.append(np.array(current))
return lineas
#leer el archivo
ls = leer("lineas.txt")
fig, ax = plt.subplots(figsize=(8, 8))
ax.set_aspect('equal')
ax.grid(True, alpha=0.3)
# Colorespor cada caso
colors = plt.cm.tab20(np.linspace(0, 1, 16))
# Graficar cada línea con su color y label
for i, l in enumerate(ls):
if len(l) > 0:
ax.scatter(l[:, 0], l[:, 1], color=colors[i], s=200, marker='s', linewidths=0, label=f"Caso {i+1}")
xs = np.concatenate([l[:, 0] for l in ls if len(l) > 0])
ys = np.concatenate([l[:, 1] for l in ls if len(l) > 0])
ax.set_xlim(min(xs)-1, max(xs)+1)
ax.set_ylim(min(ys)-1, max(ys)+1)
ax.legend(bbox_to_anchor=(1.05, 1), loc='upper left', title="Casos")
plt.tight_layout()
plt.show()
Gráfica
Resultados en archivo txt: Descargar lineas.txt
