Pr Ctica 01

Práctica 01: Diseño de Algoritmos usando Inducción
Problema de la línea horizonte (Skyline Problem)
Fecha de Entrega: 23 de septiembre 2014
Profesora: María de Luz Gasca Soto
Ayudante: Ma. Del PilarHernández Bastida

1. Planteamiento del problema:
Con la comercialización y popularidad de las estaciones de trabajo gráficas de alta
velocidad, el CAD (computer-aided design) y otras áreas hacen usomasivo y
efectivo de las computadoras. Un importante problema a la hora de dibujar
imágenes es la eliminación de líneas ocultas, es decir, la eliminación de líneas que
quedan ocultas por otras partesdel dibujo. Este interesante problema recibe el
nombre de “Problema de la Línea Horizonte” (Skyline Problem).

El problema se establece en los siguientes términos:
o La ciudad está definida en dosdimensiones. (Plano
cartesiano)
o Se consideran sólo edificios rectangulares.
o Los edificios parten de un fondo común.
o Cada edificio está representado por una tripleta (Li, Hi,
Ri), donde:
A. Li,coordenada del eje “x” que representa el
inicio del edificio en el plano cartesiano.
B. Ri, coordenada del eje “x” que representa el fin
del edificio en el plano cartesiano.
C. Hi, coordenada del eje “y”que representa la
altura del edificio.

Edificio
1
2
3
4
5
6
7

Tripleta
(1,3,4)
(2,4,5)
(6,1,7)
(8,4,15)
(8,5,11)
(9,3,12)
(13,5,16)

o La solución del problema es una secuencia de
coordenadas yalturas uniendo los edificios de manera
ordenada de izquierda a derecha.
Ejemplo: (representación skyline)

Ejemplo: (representación edificios)

La línea de rojo representa el skyline.
Skyline ={1,3,2,4,5,0,6,1,7,0,8,5,11,4,13,5,16,0}

2. Desarrollo:
Para está práctica se diseñará un algoritmo que solucione el problema de la línea
horizonte (skyline) usando inducción matemática, dicho algoritmoserá implementado de
manera gráfica en java.
o Entrada del programa: tripletas de edificios.
o Salida del programa: lista con coordenadas que represente el skyline.

3. Detalles implementación:
De...