Download Algoritmos de línea de barrer

Técnicas de diseño de algoritmos
Algoritmos de línea de barrer
Dra. Elisa Schaeffer
[email protected]
PISIS / FIME / UANL
Lı́nea de barrer– p. 1
Algoritmos de línea de barrer
Los algoritmos de lı́nea de barrer (inglés: sweep line o
scan line) dividen el problema en partes que se puede
procesar en secuencia.
Son particularmente comúnes para los problemas de
geometrı́a computacional, donde se procesa objetos
geométricos como apuntos, líneas, polígonos, etcétera.
La instancia del problema está compuesta por la
información de la ubicación de los objetos en un espacio
definido.
Lı́nea de barrer– p. 2
Intuición en plano
Para el caso que es espacio sea un plano, se puede
imaginar que una línea mueva en el plano, cruzando la
parte relevante del espacio donde se ubican los objetos.
El movimiento de la línea sigue uno de los ejes u otra línea
fija y la línea se para en puntos relevantes al problema.
Los puntos de parada se guarda en un montı́culo. La
inicialización del montículo y su actualización son asuntos
importantes en el diseño del algoritmo.
Lı́nea de barrer– p. 3
Información auxiliar
También se puede aprovechar de otras estructuras de
datos auxiliares, por ejemplo para guardar información
sobre cuáles objetos están actualmente bajo de la
lı́nea.
Entre dos paradas de la línea, los papeles relativos de los
objetos pueden cambiar, pero los factores esenciales de la
solución del problema no deben cambiar de una parada a
otra.
Lı́nea de barrer– p. 4
Otras dimensionalidades
Si el espacio tiene una sola dimensión, en vez de una
línea basta con usar un punto. Para dimensiones mayores
n, se “barre” con un hiperplano de dimensión n − 1.
Lı́nea de barrer– p. 5
Intersecciones de segmentos
Dado: n segmentos de líneas en plano de dos
dimensiones
Pregunta: ¿Cuáles son los puntos de intersección entre
todos los segmentos?
Lı́nea de barrer– p. 6
Ejemplo
Lı́nea de barrer– p. 7
Algoritmo ingenuo
Procesar cada uno de los n(n − 1) = Θ (n2 ) pares de
segmentos si ∈ S y sj ∈ S tal que i 6= j y computa su
intersección.
El el peor caso, esto es el comportamiento óptimo: si todos
los segmentos se intersectan, habrá que calcular todas las
intersecciones en cualquier caso y solamente imprimir la
lista de las instrucciones ya toma Θ (n2 ) tiempo.
Lı́nea de barrer– p. 8
Instancias típicas
Sin embargo, en una instancia promedia o típica, el
número de puntos de intersección k es mucho menor que
n(n − 1).
El algoritmo mejor imaginable tuviera complejidad
asintótica O (n + k), porque se necesita tiempo O (n) para
leer la entrada y tiempo O (k) para imprimir la salida.
Ahora veremos un algoritmo de línea de barrer que corre
en tiempo O ((n + k) log n).
Lı́nea de barrer– p. 9
El algoritmo
Los puntos de parada serán todos los puntos donde
empieza o termina un segmento y además los
puntos de intersección.
Lı́nea de barrer– p. 10
El algoritmo
Los puntos de parada serán todos los puntos donde
empieza o termina un segmento y además los
puntos de intersección.
Son n puntos de comienzo, n puntos finales y k
intersecciones.
Lı́nea de barrer– p. 10
El algoritmo
Los puntos de parada serán todos los puntos donde
empieza o termina un segmento y además los
puntos de intersección.
Son n puntos de comienzo, n puntos finales y k
intersecciones.
La línea de barrer moverá en perpendicular al
x, o sea, en paralelo al eje y.
eje
Lı́nea de barrer– p. 10
El algoritmo
Los puntos de parada serán todos los puntos donde
empieza o termina un segmento y además los
puntos de intersección.
Son n puntos de comienzo, n puntos finales y k
intersecciones.
La línea de barrer moverá en perpendicular al
x, o sea, en paralelo al eje y.
eje
Se guardará los puntos de parada en un montículo.
Lı́nea de barrer– p. 10
El algoritmo
Los puntos de parada serán todos los puntos donde
empieza o termina un segmento y además los
puntos de intersección.
Son n puntos de comienzo, n puntos finales y k
intersecciones.
La línea de barrer moverá en perpendicular al
x, o sea, en paralelo al eje y.
eje
Se guardará los puntos de parada en un montículo.
Las actualizaciones necesarias del montículo tomarán
O (log n) tiempo cada una.
Lı́nea de barrer– p. 10
Observaciones
Entre dos puntos de parada, por definición no hay ninguna
intersección.
El subconjunto de segmentos cuales quedan “bajo” de la
línea de barrer, o sea, los segmentos que intersectan con
la línea de barrer mientras mueva de un punto de parada
al siguiente no cambia.
El orden de los puntos de intersección en comparación a
cualquier de los dos ejes está fijo.
Lı́nea de barrer– p. 11
Ejemplo preprocesado
Lı́nea de barrer– p. 12
Estructura de segmentos
Guardamos en un árbol binario balanceado los segmentos
que quedan actualmente bajo de la línea de barrer.
El árbol nos da acceso en tiempo O (log n).
Se insertarán según el orden de la coordenada y del punto
de intersección del segmento con la línea de barrer.
Lı́nea de barrer– p. 13
Actualización del árbol
(I) cuando comienza un segmento, se inserta el
segmento en el lugar adecuado en el árbol binario
(II) cuando termina un segmento, se saca el segmento del
árbol, y
(III) cuando se intersectan dos segmentos, el segmento
que antes estaba arriba se cambia por abajo y
viceversa — en este último caso también se imprime
el punto de intersección encontrada a la salida
Lı́nea de barrer– p. 14
Momento de intersección
Por el hecho que el orden está según la coordenada y,
a llegar a la intersección de dos segmentos si y sj , son
“vecinos” en el árbol por lo menos justo antes de llegar
al punto de intersección.
Lı́nea de barrer– p. 15
Momento de intersección
Por el hecho que el orden está según la coordenada y,
a llegar a la intersección de dos segmentos si y sj , son
“vecinos” en el árbol por lo menos justo antes de llegar
al punto de intersección.
Ser vecinos quiere decir que son vértices hoja del
árbol que están uno al lado del otro en el nivel bajo.
Lı́nea de barrer– p. 15
Momento de intersección
Por el hecho que el orden está según la coordenada y,
a llegar a la intersección de dos segmentos si y sj , son
“vecinos” en el árbol por lo menos justo antes de llegar
al punto de intersección.
Ser vecinos quiere decir que son vértices hoja del
árbol que están uno al lado del otro en el nivel bajo.
=⇒ Al haber actualizado la estructura, lo único que
tenemos que hacer es calcular las puntos de
intersección de los vecinos actuales y añadirles en la
cola de puntos de parada.
Lı́nea de barrer– p. 15
Momento de intersección
Por el hecho que el orden está según la coordenada y,
a llegar a la intersección de dos segmentos si y sj , son
“vecinos” en el árbol por lo menos justo antes de llegar
al punto de intersección.
Ser vecinos quiere decir que son vértices hoja del
árbol que están uno al lado del otro en el nivel bajo.
=⇒ Al haber actualizado la estructura, lo único que
tenemos que hacer es calcular las puntos de
intersección de los vecinos actuales y añadirles en la
cola de puntos de parada.
El número máximo de puntos de parada nuevos
encontrados al haber hecho una parada es 2.
Lı́nea de barrer– p. 15
Pseudocódigo
M := un montículo vacío
para todo si ∈ S,
si = (x1 , y1 ), (x2 , y2 ) tal que x1 ≤ x2
insertar en M el dato [(x1 , y1 ), C, i, −]
insertar en M el dato [(x2 , y2 ), F, i, −]
B := un árbol binario balanceado vacío
mientras M no está vacío
(x, y) := el elemento mínimo de M
remueve (x, y) de M
...
Lı́nea de barrer– p. 16
Pseudocódigo: puntos de inicio
si (x, y) es de tipo C como “comienzo”
insertar si a B ordenado según la clave y
si el vecino izquiero de si en B está definido y está sℓ
computar la intersección (x′ , y ′ ) de si y sℓ
si x′ > x
insertar en M el dato [(x′ , y ′ ), I, ℓ, i]
si el vecino derecho de si en B está definido y está sr
computar la intersección (x′′ , y ′′ ) de si y sr
si x′′ > x
insertar en M el dato [(x′′ , y ′′ ), I, i, r]
...
Lı́nea de barrer– p. 17
Pseudocódigo: puntos finales
si (x, y) es de tipo F como “final”
sℓ := el segmento a la izquierda de si en B
sr := el segmento a la derecha de si en B
remueve si de B
si están definidos ambos sℓ y sr ,
computar la intersección (x′ , y ′ ) de sℓ y sr
si x′′ > x
insertar en M el dato [(x′ , y ′ ), I, ℓ, r]
...
Lı́nea de barrer– p. 18
Pseudocódigo: intersecciones
si (x, y) es de tipo “intersección”
i := el primer índice definido en el dato
j := el segundo índice definido en el dato
intercambia las posiciones de si y sj en B
si el nuevo vecino izq. de sj en B es sℓ
computar la intersección (x′ , y ′ ) de sj y sℓ
si x′ > x, insertar en M el dato [(x′ , y ′ ), I, j, ℓ]
si el nuevo vecino der. de si en B es sr
computar la intersección (x′′ , y ′′ ) de si y sr
si x′′ > x, insertar en M el dato [(x′′ , y ′′ ), I, i, r]
imprimir (x, y)
Lı́nea de barrer– p. 19
Análisis: montículo
La construcción al inicio: O (n)
Lı́nea de barrer– p. 20
Análisis: montículo
La construcción al inicio: O (n)
En cada punto preprocesado se realiza una inserción
o un retiro de un elemento de un árbol binario
balanceado.
Lı́nea de barrer– p. 20
Análisis: montículo
La construcción al inicio: O (n)
En cada punto preprocesado se realiza una inserción
o un retiro de un elemento de un árbol binario
balanceado.
Son en total 2n de tales operaciones.
Lı́nea de barrer– p. 20
Análisis: montículo
La construcción al inicio: O (n)
En cada punto preprocesado se realiza una inserción
o un retiro de un elemento de un árbol binario
balanceado.
Son en total 2n de tales operaciones.
Juntas necesitan O (n log n) tiempo.
Lı́nea de barrer– p. 20
Análisis: montículo
La construcción al inicio: O (n)
En cada punto preprocesado se realiza una inserción
o un retiro de un elemento de un árbol binario
balanceado.
Son en total 2n de tales operaciones.
Juntas necesitan O (n log n) tiempo.
Se añade máx. 2 elementos por cada inserción y al
máximo un elemento por cada retiro.
Lı́nea de barrer– p. 20
Análisis: montículo
La construcción al inicio: O (n)
En cada punto preprocesado se realiza una inserción
o un retiro de un elemento de un árbol binario
balanceado.
Son en total 2n de tales operaciones.
Juntas necesitan O (n log n) tiempo.
Se añade máx. 2 elementos por cada inserción y al
máximo un elemento por cada retiro.
Cada operación es O (log n) y son O (n) operaciones.
Lı́nea de barrer– p. 20
Análisis: intersecciones
Hasta ahora todo necesita O (n log n) tiempo.
En los puntos de intersección se intercambian
posiciones.
Lı́nea de barrer– p. 21
Análisis: intersecciones
Hasta ahora todo necesita O (n log n) tiempo.
En los puntos de intersección se intercambian
posiciones.
Implementar con dos retiros seguidos por dos
inserciones al árbol, de costo O (log n) cada uno.
Lı́nea de barrer– p. 21
Análisis: intersecciones
Hasta ahora todo necesita O (n log n) tiempo.
En los puntos de intersección se intercambian
posiciones.
Implementar con dos retiros seguidos por dos
inserciones al árbol, de costo O (log n) cada uno.
Además se inserta al máximo dos puntos al montículo,
de costo O (log n) por inserción.
Lı́nea de barrer– p. 21
Análisis: intersecciones
Hasta ahora todo necesita O (n log n) tiempo.
En los puntos de intersección se intercambian
posiciones.
Implementar con dos retiros seguidos por dos
inserciones al árbol, de costo O (log n) cada uno.
Además se inserta al máximo dos puntos al montículo,
de costo O (log n) por inserción.
En total son k intersecciones =⇒ O (k log n).
Lı́nea de barrer– p. 21
Análisis: intersecciones
Hasta ahora todo necesita O (n log n) tiempo.
En los puntos de intersección se intercambian
posiciones.
Implementar con dos retiros seguidos por dos
inserciones al árbol, de costo O (log n) cada uno.
Además se inserta al máximo dos puntos al montículo,
de costo O (log n) por inserción.
En total son k intersecciones =⇒ O (k log n).
Tiempo total: O (n log n) + O (k log n) = O ((n + k) log n)
Lı́nea de barrer– p. 21
Tarea para entregar el martes
Busca en línea un algoritmo de línea de barrer para la
construcción de diagramas de Voronoia para un
conjunto de puntos en R2 .
Da un resumen de las estructuras de datos necesarias y
pseudocódigo de nivel general, junto con un análisis de la
complejidad.
La idea no es tanto copiar directamente el pseudocódigo y el análisis de algún lugar,
sino encontrar las definiciones y la idea del algoritmo en línea y después pensar.
a
Sirven por ejemplo para convertir un conjunto de puntos en un grafo plano
— tarea extra es explicar cómo.
Lı́nea de barrer– p. 22