Geometría Computacional: Intersección de segmentos.

Maikel Arcia

Miguel Sancho

Motivación

Robótica

Detección / prevención de colisiones

Gráficos por Computadoras

Trazado de rayos

Sistemas de Información Geográfico (SIG/GIS)

Operaciones de Solapamiento de Mapas

Palabras claves y conceptos

Algoritmo Sensibles a la Salida

Técnica de Diseño “Barrido del Plano” (Plane Sweep)

Intersección de segmentos

Sistemas de Información Geográfico: (División de mapas en capas)

Los mapas son una importante fuente de información, sitios, calles, líneas, ríos, etc.

Puede ser difícil encontrar la información deseada.

Para hacer lo mapas comprensibles, los SIG dividen estos en muchas capas.

Cada capa corresponde a un mapa temático, donde se almacena solo un tipo de información.

Lecture 2

Line Segment Intersection

Computational Geometry

Prof.Dr.Th.Ottmann

Thematic map overlay in Geographical Information Systems

carreterasrios Solapamiento

de mapas

1. Thematic overlays provide important information.

2. Roads and rivers can both be regarded as networks of line

segments.

Motivación

Solapamientos de Mapa

Determinar intersecciones entre capas.

Intersección de redes.

Dada una colección de n segmentos de línea en el plano, computar todos los puntos de intersección

¿Cuantos puntos de intersección podemos esperar?

No. Mínimo = 0

No. Máximo = O(n2)

Intersección de Segmentos.

Algoritmo de Fuerza Bruta

Realizamos una consulta de intersección por todos los pares de segmetos.

Por tanto, un algoritmo O(n2) sería de cierta forma óptimo ya que el máximo de intersecciones es O(n2) Fácil de obtener: consulta todos los pares

En muchos casos, se espera pocas intersecciones « n2, sería bueno tener un algoritmo rápido para estos casos,

Algoritmo Fuerza Bruta IS(S)

Entrada: Conjunto S de segmentos en el plano.

Salida: Una lista L que contiene los puntos de

intersección de los segmentos de S.

Para cada par (s,t), st hacer

Si Interceptan(s,t)

adicionar en L Interseccion(s,t)

Reportar L

Alto costo debido a que se comprueban todas las posibles combinaciones: O(n2)

Algoritmo Sensible a la Salida

Algoritmo que no dependa solo de la cantidad de segmentos de la entrada sino del número de intersecciones.

Algoritmo Sensible a la Salida

Se denominan algoritmos Sensibles a la Salida, el tiempo del algoritmo depende del tamaño de la salida.

Algoritmo Sensible a la Salida

En este caso será un algoritmo Sensible a lasIntersecciones. El número de intersecciones determinará la complejidad temporal.

No podemos consultar todos los pares de segmentos.

Algoritmo Sensible a las Intersecciones

No podemos consultar todos los pares de segmentos.

Algoritmo Sensible a las Intersecciones

Idea: evitar consultar los pares de segmentos que están distantes.

No podemos consultar todos los pares de segmentos.

Algoritmo Sensible a las Intersecciones

Debemos utilizar la situación geométrica: los segmentos que están muy próximos son más probables de interceptar.

Idea: evitar consultar los pares de segmentos que están distantes.

Segmentos Cercanos

Segmentos Cercanos

Segmentos Cercanos

Algoritmo Barrido del PlanoPlane Sweep

(versión inicial)

Barrido del Plano: técnica incremental

Barrido del Plano: técnica incremental

Barrido del Plano: técnica incremental

Barrido del Plano: técnica incremental

Barrido del Plano: técnica incremental

Posibles intersecciones

Dos segmentos son candidatos de interceptarse si

se solapan sus proyecciones en el eje Y

Posibles intersecciones

Dos segmentos son candidatos de interceptarse si

se solapan sus proyecciones en el eje Y

Posibles intersecciones

Dos segmentos son candidatos de interceptarse si

se solapan sus proyecciones en el eje Y

Posibles intersecciones

Dos segmentos son candidatos de interceptarse si

se solapan sus proyecciones en el eje Y

Dos segmentos son «candidatos» de interceptarse si existe una línea horizontal que los intercepta.

Posibles intersecciones

Dos segmentos son candidatos de interceptarse si

se solapan sus proyecciones en el eje Y

Dos segmentos son candidatos de interceptarse si existe una línea horizontal que los intercepta.

Línea de barrido

Desplazamos una línea de barrido l imaginaria de arriba hacia abajo, lo que permite detectar los segmentos que se solapan en Y.

Línea de barrido

Desplazamos una línea de barrido l imaginaria de arriba hacia abajo, lo que permite detectar los segmentos que se solapan en Y.

Línea de barrido

Desplazamos una línea de barrido l imaginaria de arriba hacia abajo, lo que permite detectar los segmentos que se solapan en Y.

Línea de barrido

Desplazamos una línea de barrido l imaginaria de arriba hacia abajo, lo que permite detectar los segmentos que se solapan en Y.

Línea de barrido

Desplazamos una línea de barrido l imaginaria de arriba hacia abajo, lo que permite detectar los segmentos que se solapan en Y.

Línea de barrido

Desplazamos una línea de barrido l imaginaria de arriba hacia abajo, lo que permite detectar los segmentos que se solapan en Y.

Línea de barrido

Desplazamos una línea de barrido l imaginaria de arriba hacia abajo, lo que permite detectar los segmentos que se solapan en Y.

Línea de barrido

Desplazamos una línea de barrido l imaginaria de arriba hacia abajo, lo que permite detectar los segmentos que se solapan en Y.

Línea de barrido

Desplazamos una línea de barrido l imaginaria de arriba hacia abajo, lo que permite detectar los segmentos que se solapan en Y.

Estado de la línea de barrido

El estado de la línea de barrido está formado por los segmentos que ésta intercepta.

El estado no cambia de forma continua, sólo lo hace en ciertos puntos discretos: puntos eventos.

Los puntos de evento serán los puntos de inicio y final de cada segmento.

Posición General

Casos degenerados : Segmentos horizontales. Segmentos colinealeas Intersección de más de dos segmentos en un mismo

punto.

Asumimos puntos en Posición General.

Estructuras de datos

Cola-evento (Q): conjunto de puntos iniciales y finales de los segmentos, ordenados por coordenada y. Implementación: arreglo, lista enlazada.

Estructura-estado (L): lista de segmentos que interceptan la línea de barrido.

Implementación: arreglo, lista enlazada.

Algoritmo Barrido del Plano Inicial IS(S)

Entrada: Conjunto S de segmentos en el plano.

Salida: Reportar todos los puntos de intersección.

1.Insertar todos los puntos inicio y final de cada

segmento s en Q de forma ordenada según su y-

coordenada.

2. Mientras Q no esté vacía

3. p <- QuitarMin(Q)

4. Caso 1: p punto inicio del segmento s

adicionar s a L

5. Para cada segmento t de L

6. Si Interceptan(s,t)

8. Reportar interseccion(s,t)

9. Caso 2: p punto final del segmento s

10. Eliminar s de la L

Ejemplo

Hacer una traza del algoritmo con el siguiente ejemplo de segmentos

¿El algoritmo es sensible a la salida?

No es eficiente: podemos encontrar situaciones donde se realicen O(n2) comparaciones.

¿El algoritmo es sensible a la salida?

No es eficiente: podemos encontrar situaciones donde se realicen O(n2) comparaciones.

Problema: dos segmentos que sean interceptados por una línea horizontal no necesariamente tienen que ser cercanos en dirección horizontal.

Algoritmo Barrido del PlanoPlane Sweep

(versión final)

Mejora a la hora de comprobar con vecinos

Ordenemos de izquierda a derecha los segmentos que interceptan la línea de barrido según coordenada x de la intersección con la línea de barrido

Sólo comprobaremos segmentos adyacentes al nuevo segmento

Nuevos puntos evento

Los puntos intersección serán nuevos puntos evento: en ellos se cambia el orden de izquierda a derecha de los segmentos.

Estructura-estado: (s0,s1)

Estructura-estado: (s1,s0)

Estructuras de datos

Cola de Eventos (Q): conjunto de puntos iniciales, finales, y puntos de intersección.

Se necesita una Cola con Prioridad.Implementación:

Estado de la línea (T): segmentos que interceptan la línea de barrido, ordenados por la coordenada x del punto de intersección del segmento con la línea de barrido

Implementación:

Estructuras de datos

Cola de Eventos (Q): conjunto de puntos iniciales, finales, y puntos de intersección.

Se necesita una Cola con Prioridad.Implementación:

Estado de la línea (T): segmentos que interceptan la línea de barrido, ordenados por la coordenada x del punto de intersección del segmento con la línea de barrido

Implementación:

Heap

Árbol Binario de Búsqueda

Balanceado

Evento: Punto inicial

T : (s3,s2)

T : (s1,s3,s2)

Se añade segmento a T

Se comprueba con los segmentos adyacentes (sólo s3).

Se detecta un punto de intersección, este se inserta de forma ordenada en Q

Evento: Punto de intersección

Se intercambia en la lista-estado el orden de los segmentos

Al intercambiar s3 y s1, se debe comprobar intersección con sus nuevos vecinos: (s3 , s0) y (s1 ,s2).

Se detecta otra intersección

entre s1 y s2, esta se inserta de forma ordenada en Q

T : (s0,s1,s3,s2,s4)

T : (s0,s3,s1,s2,s4)

Evento: Punto final

Se elimina segmento de T.

Al eliminar s1, aparecen dos nuevos vecinos que hay que comprobar: (s0 , s4).

Generando la última intersección que se inserta de forma ordenada en Q

T: (s0,s1,s4)

T: (s0,s4)

Algoritmo Barrido del Plano Final IS(S)

Entrada: Conjunto S de segmentos en el

plano.

1. Insertar los puntos inicio y final de cada

segmento en Q de forma ordenada según su

coordenada y

2. Mientras Q no esté vacía hacer

3. p <- QuitarMin(Q)

4. TratarPuntoEvento(p)

Algoritmo Tratar Punto Evento (p)

Entrada: Punto de evento p asociado al segmento s

Salida: Vacio

Caso 1: p punto inicio del segmento s

Insertar s de forma ordenada en T

Si intercepta con segmentos adyacentes

Añadir putos de intersección en Q

Caso 2: p punto final del segmento s

Eliminar s de T

Si intercepta los nuevos segmentos adyacentes

Añadir putos de intersección en Q

Caso 3: p punto de intersección de segmentos s y t

Intercambiar el orden de s y t en T

Si intercepta con los nuevos adyacentes

Añadir putos de intersección en Q

Cola de Eventos (Q): Heap

No todos los puntos se conocen a priori, hay que inserta nuevos puntos.

Se necesita una Cola con Prioridad.

Su mejor implementación es un Heap.

Hojas: almacenan los segmentos en el orden en que son interceptados

Nodos Internos: Almacena segmento extremo derecho del subárbol izquierdo

Para buscar el vecino izquierdo/derecho se “baja” en el árbol comparando con los segmentos en los nodos internos.

Insertar/buscar toma tiempo O(log n′), donde n′ es el número de segmentos en T, n′<n.

Árbol Binario de Búsqueda Balanceado

lsi

sj

slsk

smp

si sjsl sk sm

si

sj

slsk

Casos Degenerados

Tres o más segmentos interceptan en el mismo punto

Para manejar estos casos es necesario garantizar

Insertar un solo punto de evento

Intercambiar el orden en T cuando sea procesado.

Dos o más segmentos comparten un mismo punto extremo

También será tratado.

Insertar un solo punto de evento

Solapamientos de segmentos

Puede ser manejado pero es un poco más complejo

si

sj

Algoritmo Tratar Punto Evento (p)

Entrada: Un punto de evento p

Salida: Puntos de intersección y segmentos asociados

Sea U(p) los segmentos cuyo punto superior es p

Sea L(p) los segmentos en T cuyo punto inferior es p

Sea C(p) segmentos en T que contienen a p

Si |L(p) U(p) C(p)| > 0

Reportar a p como intersección con L(p),U(p),C(p)

Eliminar los segmentos L(p) C(p) en T.

Insertar U(p) C(p) en T según orden de intersección

Si U(p)C(p) es vacío

Sea sl y sr vecinos izq y der de p en T.

BuscarNuevoEvento(sl,sr,p)

Sino

Sea s’ segmento extremo izquierdo de U(p) y C(p) en

T y sea sl el vecino izquierdo de s’ en T

BuscarNuevoEvento(sl ,s’,p)

Sea s’’ el segmento extremo derecho de U(p) y C(p)

en T Sea sr el vecino derecho de s’’ en T

BuscarNuevoEvento(s’’, sr , p)

Buscar nueva intersección

Es fácil: simplemente buscar la intersección para dos segmentos.

La complejidad es saber si esa intersección se ha tratado o no con anterioridad.

Las intersecciones no han sido manejadas si están por debajo de la línea de barrido.

Segmentos Horizontales (caso degenerado): los puntos con igual y-coordenadas son tratados de izquierda a derecha.

Los puntos de intersección que estén sobre la línea de barrido a la derecha faltarán por ser tratados.

Algoritmo BuscarNuevoEvento (sl,sr,p)

Entrada: Un punto de evento p y los

segmentos adyacentes por la derecha y la

izquierda respectivamente

Si la Interseccion(sl,sr) está por debajo

de la línea de barrido o sobre esta a la

derecha del punto p

Insertar Interseccion(sl,sr) en Q.

Cada segmento es colocado en la cola 2 veces: O(n log n)

La línea de barrido tiene a lo máximo n segmentos y por tanto insertar o remover un evento tiene complejidad O (log n)

El procesamiento de un evento puede requerir hasta 2 consultas de intersección, esto es O (2n + I) consultas.

El procesamiento de todos los eventos tiene complejidad

O ((2n + I ) (1 + log n)) = O (n log n + I log n)= O ((n+ I) log n)

Complejidad del Algoritmo

Bibliografía base

MM. de Berg, M. van Kreveld, M. Overmars, O. Schawarzkopf: Computational Geometry, Springer Verlag, 1997.

Geometría ComputacionalGeometría Computacional