Intersección de segmentos de recta

En geometría computacional el problema de intersección de segmentos de recta está dado de la siguiente manera: dado un conjunto $S$ de n segmentos en el plano euclidiano se deben reportar todos los puntos de intersección en todo el conjunto $S$.

Mucha de la motivación para el estudio de los problemas de intersección recae en el simple hecho de que dos cuerpos no pueden ocupar el mismo lugar. La importancia de estudiar y diseñar algoritmos eficientes para detectar intersecciones está dada por la ambición de la industria, una imagen complicada puede contener cientos de miles de vectores. Una base de datos puede contener más de un millón de elementos, un circuito integrado puede contener millones de componentes; en estos casos tener un algoritmo inclusive de complejidad cuadrática son inaceptables. En geometría existen problemas los cuales puede ser resueltos mediante la solución del problema de intersección de segmentos como pueden ser el decidir cuando un polígono es simple o no.

Un primer intento en resolver este problema está dado por lo siguiente: tomar todas las parejas de segmentos y ver si se intersecan. Este método es de orden $O(n^{2})$ (se dice que este algoritmo usa fuerza bruta, pues prueba todas las opciones posibles). A primera instancia es un algoritmo óptimo; sin embargo, es de orden $\Omega (n^{2})$, es decir, aun si no se presenta alguna intersección el algoritmo toma tiempo cuadrático. Es necesario un algoritmo "output sensitive" (sensible a la salida) para reducir este tiempo a algo cercano a $O(n\log(n))$​

Barrido de recta

El algoritmo mencionado al final de la sección anterior es un algoritmo basado en un método conocido como barrido de recta, el cual consiste en recorrer los segmentos del conjunto $S$ utilizando una recta (a esta línea se le conoce como línea de barrido). En este caso podemos pensar que la recta recorre el plano de arriba hacia abajo y de esa manera recorre los segmentos. Para poder recorrer los segmentos se necesita que estén ordenados, podemos usar quicksort para este propósito. La primera observación que puede hacerse para diferenciar este algoritmo del algoritmo de fuerza bruta mencionado anteriormente es que si tenemos un segmento, solo verificamos a sus vecinos y no a los demás. Definimos a los vecinos de un segmento $s$ como los segmentos que se encuentren a la derecha e izquierda del segmento $s$.

Los vecinos de a son c y b con respecto a la recta f.

Antes de proseguir con el algoritmo cabe mencionar que el barrido de recta funcionará deteniéndose en ciertos puntos los cuales más adelante definiremos como eventos. Esto es importante, puesto que en una computadora no podemos representar el movimiento continuo de la recta, entonces debemos discretizar este movimiento, es decir definir un conjunto finito y numerable de puntos en los cuales la recta se detendrá. Observar que necesitamos definir puntos suficientes para poder hallar todos los puntos de intersección y no demasiados para llegar a tener un orden $O(n^{2})$ (menor a $n^{2}$ puntos).

Eventos

A continuación definiremos los tipos de eventos que se tendrán en el algoritmo.

1. Punto inicial del segmento.
2. Punto final del segmento.
3. Punto de intersección entre un par de segmentos.

Punto inicial

En cada punto inicial de un segmento se añade el segmento a una estructura de almacenamiento, la cual mantendrá los segmentos activos y los puntos activos. De igual forma se guarda en otra estructura el orden de los segmentos intersecados por la línea de barrido para tener los vecinos derechos e izquierdos de cada segmento.

Punto final

Al procesar un punto final se elimina de la estructura mencionada anteriormente.

Punto de intersección

En un punto de intersección se intercambian los vecinos derechos e izquierdos respectivamente de los segmentos que se intersecan en dicho punto.

Cambio de vecinos en un punto de intersección.

Algoritmos

A continuación se presenta el algoritmo descrito con anterioridad. Se utilizarán 2 estructuras, una cola de eventos $Q$, y un árbol binario de búsqueda $T$.

Algoritmo: EncontrarIntersecciones($S$)​

Entrada: Un conjunto $S$ de segmentos de recta en el plano.

Salida: El conjunto de puntos de intersección de los segmentos en $S$, junto con los segmentos que se intersecan en cada punto.

1. Inicializar la cola de eventos $Q$. Insertar los puntos iniciales y finales de los segmentos en $Q$. Cada vez que se inserta un punto inicial se inserta el correspondiente segmento que lo contiene.

2. Inicializar la estructura vacía $T$.

3. Mientras $Q$ sea no vacía

4. Hacer: Determinar el siguiente punto de evento $p$ en $Q$ y borrarlo.

5. ManejarPuntoDeEvento($p$)

Algoritmo: ManejarPuntoDeEvento($p$)​

1. Definamos $U(p)$ como el conjunto de segmentos cuyo punto inicial es p; estos segmentos son guardados con el punto de evento $p$. (Para segmentos horizontales el punto inicial es el punto a la izquierda).

2. Encontrar todos los segmentos almacenados en $T$ que contienen a $p$; estos son adyacentes en $T$. Definamos $L(p)$ como el conjunto de segmentos cuyo punto final es $p$, y $C(p)$ el conjunto de segmentos que contienen a $p$ en su interior.

3. Si $L(p)\cup U(p)\cup C(p)$ contiene más de un segmento

4. Entonces reportar $p$ como punto de intersección, junto con $L(p),U(p)$ y $C(p)$.

5. Borrar los segmentos $L(p)\cup C(p)$ de $T$.

6. Insertar los segmentos en $U(p)\cup C(p)$ en $T$. El orden de los segmentos en $T$ debe corresponder con el orden en el cual fueron intersecados por la línea de barrido justo debajo de $p$. Si es un segmento horizontal, se coloca de último entre los segmentos que contienen a $p$.

7. (* Borrar y reinsertar los segmentos de $C(p)$ invierte su orden. *)

8. Si $U(p)\cup C(p)=\emptyset$

9. Entonces definimos $s_{l}$ y $s_{r}$ como los vecinos izquierdo y derecho, respectivamente, de $p$ en $T$.

10. EncuentraNuevoEvento($s_{l},s_{r},p$)

11. Si no, definimos $s'$ para ser el segmento más a la izquierda de $U(p)\cup C(p)$ en $T$.

12. Definimos $s_{l}$ como el vecino izquierdo de $s'$ en $T$.

13. EncuentraNuevoEvento($s_{l},s',p$)

14. Definimos $s''$ como el segmento más a la derecha de $U(p)\cup C(p)$ en $T$.

15. Definimos $s_{r}$ como el vecino derecho de $s''$ en $T$

16. EncuentraNuevoEvento($s'',s_{r},p$)

Notar que en este algoritmo en las líneas 8-16 se asume que los vecinos derechos e izquierdos existen. En caso de que no existan los pasos correspondientes no se ejecutarán.

Algoritmo: EncuentraNuevoEvento($s_{l},s_{r},p$)​

1. Si $s_{l}$ y $s_{r}$ se intersecan debajo de la línea de barrido, o en ella y a la derecha del punto de evento actual, y la intersección todavía no se ha presentado como un evento en $Q$

2. Entonces insertar el punto de intersección como un evento en $Q$

Puede consultar la prueba de la correctitud del algoritmo en la referencia de donde se tomaron.

El tiempo de ejecución de este algoritmo es $O(n\log(n)+I\log(n))$, donde I es el número de intersecciones entre los segmentos. Un breve bosquejo para poder observar esta afirmación es el siguiente: Implementando a $Q$ como un árbol binario balanceado, construirlo nos toma $O(n\log(n))$. Las operaciones en $T$ nos toman $O(\log(n))$. El número de eventos, llamémosle m, es lineal, deseamos que fuese $O(n+I)$ lo cual se demuestra utilizando la fórmula de Euler y tomando el conjunto de segmentos como un grafo plano, tenemos que a lo más el número de caras($n_{f}$) que se pueden formar es ${\frac {2n_{e}}{3}}$, donde $n_{e}$ es el número de aristas, el cual a su vez está acotado por $O(n_{v})$, donde $n_{v}$ es el número de vértices, el cual en este caso es $2n+I$, entonces la fórmula de Euler nos da $n_{v}-n_{e}+n_{f}\geq 2\Rightarrow 2\leq (2n+I)-{\frac {n_{e}}{3}}\Rightarrow n_{e}\leq 6n+3I-6$. Ahora cada segmento aporta 2 vértices entonces el número de eventos está acotado por $m=2n_{e}$, entonces $m\leq 6n+6I-12$, lo cual nos da $O(n+I)$ . Como en cada evento se realizan operaciones en T tenemos que el algoritmo de EncuentrarIntersecciones toma tiempo $O(n\log(n)+I\log(n))$.

Aplicaciones

Algunas aplicaciones que tiene el resolver el problema de intersección de segmentos son:

• Remoción de líneas ocultas​ y de superficies ocultas.
• Hallar intersección de polígonos convexos
• Determinar si un polígono es simple o no.

Otros trabajos

Existen otros algoritmos desarrollados por diferentes personas las cuales tratan de mejorar el tiempo de ejecución, Entre los cuales tenemos.

• Bernard Chazelle(1992).​ Establece que el problema se puede resolver en $O({\frac {n\log ^{2}(n)}{\log \log(n)}}+I)$.
• Mairson and Stolfi.​ Dados dos conjuntos A,B de segmentos tales que $|A|+|B|=n$ se puede resolver el problema de hallar las intersecciones entre los conjuntos de segmentos en $O(n\log(n)+I)$
• Bentley-Ottman​

Véase también

• Intersección recta-recta

Bibliografía

1. Preparata, Franco P.; Shamos, Michael Ian (1985). Computational Geometry, An Introduction. Springer-Verlag New York Inc. ISBN 0-387-96131-3. 
2. Berg, Mark de; Cheong, Otfried; van Kreveld, Marc; Overmars, Mark (2008). Computational Geometry, Algorithms and Applications (tercera edición). Springer-Verlag Berlin Heidelberg. ISBN 978-3-540-77973-5. 

• Datos: Q6553330