Intersección de segmentos de recta
de n segmentos en el plano euclidiano se deben reportar todos los puntos de intersección en todo el conjunto
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.
(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
, es decir, aun si no se presenta alguna intersección el algoritmo toma tiempo cuadrático.
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
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
.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
A continuación definiremos los tipos de eventos que se tendrán en el algoritmo.
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.
Al procesar un punto final se elimina de la estructura mencionada anteriormente.
En un punto de intersección se intercambian los vecinos derechos e izquierdos respectivamente de los segmentos que se intersecan en dicho punto.A continuación se presenta el algoritmo descrito con anterioridad.
Se utilizarán 2 estructuras, una cola de eventos
, y un árbol binario de búsqueda
)[1] Notar que en este algoritmo en las líneas 8-16 se asume que los vecinos derechos e izquierdos existen.
, 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
como un árbol binario balanceado, construirlo nos toma
El número de eventos, llamémosle m, es lineal, deseamos que fuese
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(
es el número de aristas, el cual a su vez está acotado por
es el número de vértices, el cual en este caso es
Ahora cada segmento aporta 2 vértices entonces el número de eventos está acotado por
Como en cada evento se realizan operaciones en T tenemos que el algoritmo de EncuentrarIntersecciones toma tiempo
