Algoritmo de línea de barrido
En geometría computacional , el algoritmo de Bentley-Ottmann es un algoritmo de línea de barrido para enumerar todos los cruces en un conjunto de segmentos de línea , es decir, encuentra los puntos de intersección (o, simplemente, intersecciones ) de los segmentos de línea. Extiende el algoritmo de Shamos-Hoey, un algoritmo similar anterior para probar si un conjunto de segmentos de línea tiene o no cruces. Para una entrada que consiste en segmentos de línea con cruces (o intersecciones), el algoritmo de Bentley-Ottmann toma tiempo . En los casos en que , esto es una mejora de un algoritmo ingenuo que prueba cada par de segmentos, que toma .
El algoritmo fue desarrollado inicialmente por Jon Bentley y Thomas Ottmann (1979); se describe con más detalle en los libros de texto Preparata & Shamos (1985), O'Rourke (1998) y de Berg et al. (2000). Aunque ahora se conocen algoritmos asintóticamente más rápidos por Chazelle & Edelsbrunner (1992) y Balaban (1995), el algoritmo Bentley-Ottmann sigue siendo una opción práctica debido a su simplicidad y bajos requisitos de memoria [ cita requerida ] .
Estrategia general
La idea principal del algoritmo de Bentley-Ottmann es utilizar un enfoque de línea de barrido , en el que una línea vertical L se mueve de izquierda a derecha (o, por ejemplo, de arriba a abajo) a través del plano, intersectando los segmentos de línea de entrada en secuencia a medida que se mueve. [2] El algoritmo se describe más fácilmente en su posición general , es decir:
- No hay dos puntos finales o cruces de segmentos de línea que tengan la misma coordenada x
- Ningún extremo de un segmento de línea se encuentra sobre otro segmento de línea.
- No hay tres segmentos de línea que se crucen en un solo punto.
En tal caso, L siempre intersectará los segmentos de línea de entrada en un conjunto de puntos cuyo orden vertical cambia solo en un conjunto finito de eventos discretos . Específicamente, un evento discreto puede estar asociado con un punto final (izquierdo o derecho) de un segmento de línea o un punto de intersección de dos segmentos de línea. Por lo tanto, el movimiento continuo de L se puede descomponer en una secuencia finita de pasos y simularse mediante un algoritmo que se ejecuta en una cantidad finita de tiempo.
Hay dos tipos de eventos que pueden ocurrir durante el curso de esta simulación. Cuando L barre a través de un punto final de un segmento de línea s , la intersección de L con s se agrega o elimina del conjunto ordenado verticalmente de puntos de intersección. Estos eventos son fáciles de predecir, ya que los puntos finales ya se conocen a partir de la entrada al algoritmo. Los eventos restantes ocurren cuando L barre a través de un cruce entre (o intersección de) dos segmentos de línea s y t . Estos eventos también se pueden predecir a partir del hecho de que, justo antes del evento, los puntos de intersección de L con s y t son adyacentes en el orden vertical de los puntos de intersección [ aclaración necesaria ] .
El algoritmo de Bentley-Ottmann mantiene estructuras de datos que representan el ordenamiento vertical actual de los puntos de intersección de la línea de barrido con los segmentos de línea de entrada, y una colección de posibles eventos futuros formados por pares adyacentes de puntos de intersección. Procesa cada evento por turno, actualizando sus estructuras de datos para representar el nuevo conjunto de puntos de intersección.
Estructuras de datos
Para mantener de manera eficiente los puntos de intersección de la línea de barrido L con los segmentos de línea de entrada y la secuencia de eventos futuros, el algoritmo Bentley-Ottmann mantiene dos estructuras de datos :
- Un árbol binario de búsqueda (el "árbol de estado de la línea de barrido"), que contiene el conjunto de segmentos de línea de entrada que cruzan L , ordenados por las coordenadas y de los puntos donde estos segmentos cruzan L . Los puntos de cruce en sí no están representados explícitamente en el árbol binario de búsqueda. El algoritmo Bentley-Ottmann insertará un nuevo segmento s en esta estructura de datos cuando la línea de barrido L cruce el punto final izquierdo p de este segmento (es decir, el punto final del segmento con la coordenada x más pequeña , siempre que la línea de barrido L comience desde la izquierda, como se explicó anteriormente en este artículo). La posición correcta del segmento s en el árbol binario de búsqueda puede determinarse mediante una búsqueda binaria, cada paso de la cual prueba si p está por encima o por debajo de algún otro segmento que sea cruzado por L . Por lo tanto, una inserción puede realizarse en tiempo logarítmico. El algoritmo Bentley-Ottmann también eliminará segmentos del árbol binario de búsqueda y utilizará el árbol binario de búsqueda para determinar los segmentos que están inmediatamente por encima o por debajo de otros segmentos; Estas operaciones pueden realizarse utilizando únicamente la estructura del árbol en sí, sin referencia a la geometría subyacente de los segmentos.
- Una cola de prioridad (la "cola de eventos"), utilizada para mantener una secuencia de eventos futuros potenciales en el algoritmo de Bentley-Ottmann. Cada evento está asociado con un punto p en el plano, ya sea un extremo de segmento o un punto de cruce, y el evento ocurre cuando la línea L pasa por encima de p . Por lo tanto, los eventos pueden priorizarse por las coordenadas x de los puntos asociados con cada evento. En el algoritmo de Bentley-Ottmann, los eventos futuros potenciales consisten en extremos de segmentos de línea que aún no han sido barridos y los puntos de intersección de pares de líneas que contienen pares de segmentos que están inmediatamente arriba o abajo uno del otro.
El algoritmo no necesita mantener explícitamente una representación de la línea de barrido L o de su posición en el plano. En cambio, la posición de L se representa indirectamente: es la línea vertical que pasa por el punto asociado con el evento procesado más recientemente.
El árbol binario de búsqueda puede ser cualquier estructura de datos de árbol binario de búsqueda balanceada , como un árbol rojo-negro ; todo lo que se requiere es que las inserciones, eliminaciones y búsquedas tomen un tiempo logarítmico. De manera similar, la cola de prioridad puede ser un montón binario o cualquier otra cola de prioridad de tiempo logarítmico; no son necesarias colas de prioridad más sofisticadas, como un montón de Fibonacci . Tenga en cuenta que la complejidad espacial de la cola de prioridad depende de la estructura de datos utilizada para implementarla.
Algoritmo detallado
El algoritmo Bentley-Ottmann realiza los siguientes pasos.
- Inicialice una cola de prioridad Q de posibles eventos futuros, cada uno asociado con un punto en el plano y priorizado por la coordenada x del punto. Por lo tanto, inicialmente, Q contiene un evento para cada uno de los puntos finales de los segmentos de entrada.
- Inicialice un árbol binario de búsqueda autoequilibrado T de los segmentos de línea que cruzan la línea de barrido L , ordenados por las coordenadas y de los puntos de cruce. Inicialmente, T está vacío. (Aunque la línea de barrido L no está representada explícitamente, puede ser útil imaginarla como una línea vertical que, inicialmente, está a la izquierda de todos los segmentos de entrada).
- Mientras Q no esté vacío, busque y elimine el evento de Q asociado con un punto p con la coordenada x mínima . Determine de qué tipo de evento se trata y procese según el siguiente análisis de caso:
- Si p es el extremo izquierdo de un segmento de línea s , inserte s en T . Encuentre los segmentos de línea r y t que están respectivamente inmediatamente por encima y por debajo de s en T (si existen); si el cruce de r y t (los vecinos de s en la estructura de datos de estado) forma un posible evento futuro en la cola de eventos, elimine este posible evento futuro de la cola de eventos. Si s cruza r o t , agregue esos puntos de cruce como posibles eventos futuros en la cola de eventos.
- Si p es el extremo derecho de un segmento de línea s , elimine s de T . Encuentre los segmentos r y t que (antes de la eliminación de s ) estaban respectivamente inmediatamente por encima y por debajo de él en T (si existen). Si r y t se cruzan, agregue ese punto de cruce como un posible evento futuro en la cola de eventos.
- Si p es el punto de cruce de dos segmentos s y t (con s debajo de t a la izquierda del cruce), intercambie las posiciones de s y t en T. Después del intercambio, encuentre los segmentos r y u (si existen) que están inmediatamente debajo y encima de t y s , respectivamente. Elimine cualquier punto de cruce rs (es decir, un punto de cruce entre r y s ) y tu (es decir, un punto de cruce entre t y u ) de la cola de eventos y, si r y t se cruzan o s y u se cruzan, agregue esos puntos de cruce a la cola de eventos.
Análisis
El algoritmo procesa un evento por punto final o punto de cruce de segmento, en el orden ordenado de las coordenadas de estos puntos, como se puede probar por inducción. Esto se debe a que, una vez procesado el evento , el siguiente evento (si es un punto de cruce) debe ser un cruce de dos segmentos que sean adyacentes en el orden de los segmentos representados por , y a que el algoritmo mantiene todos los cruces entre segmentos adyacentes como posibles eventos futuros en la cola de eventos; por lo tanto, el siguiente evento correcto siempre estará presente en la cola de eventos. Como consecuencia, encuentra correctamente todos los cruces de segmentos de línea de entrada, el problema que fue diseñado para resolver.
El algoritmo de Bentley-Ottmann procesa una secuencia de eventos, donde denota el número de segmentos de línea de entrada y denota el número de cruces. Cada evento se procesa mediante un número constante de operaciones en el árbol de búsqueda binaria y la cola de eventos, y (debido a que solo contiene puntos finales de segmento y cruces entre segmentos adyacentes) la cola de eventos nunca contiene más de eventos. Todas las operaciones toman tiempo . Por lo tanto, el tiempo total para el algoritmo es .
Si los cruces encontrados por el algoritmo no necesitan ser almacenados una vez que se han encontrado, el espacio utilizado por el algoritmo en cualquier punto en el tiempo es : cada uno de los segmentos de línea de entrada corresponde a lo sumo a un nodo del árbol binario de búsqueda T , y como se indicó anteriormente, la cola de eventos contiene como máximo elementos. Este límite de espacio se debe a Brown (1981); la versión original del algoritmo era ligeramente diferente (no eliminaba los eventos de cruce cuando algún otro evento hace que los dos segmentos de cruce se vuelvan no adyacentes), lo que hace que utilice más espacio. [3]
Chen y Chan (2003) describieron una versión del algoritmo Bentley-Ottmann que utiliza muy poco espacio y que codifica la mayor parte de su información en el orden de los segmentos de una matriz que representa la entrada, requiriendo únicamente celdas de memoria adicionales. Sin embargo, para acceder a la información codificada, el algoritmo se ve ralentizado por un factor logarítmico.
Posición especial
La descripción del algoritmo anterior supone que los segmentos de línea no son verticales, que los puntos finales de los segmentos de línea no se encuentran en otros segmentos de línea, que los cruces están formados por solo dos segmentos de línea y que no hay dos puntos de evento que tengan la misma coordenada x . En otras palabras, no tiene en cuenta los casos extremos, es decir, supone la posición general de los puntos finales de los segmentos de entrada. Sin embargo, estas suposiciones de posición general no son razonables para la mayoría de las aplicaciones de intersección de segmentos de línea. Bentley y Ottmann (1979) sugirieron perturbar ligeramente la entrada para evitar este tipo de coincidencias numéricas, pero no describieron en detalle cómo realizar estas perturbaciones. de Berg et al. (2000) describen con más detalle las siguientes medidas para manejar entradas de posición especial:
- Rompa los vínculos entre puntos de evento con la misma coordenada x utilizando la coordenada y . Los eventos con diferentes coordenadas y se manejan como antes. Esta modificación maneja tanto el problema de múltiples puntos de evento con la misma coordenada x como el problema de los segmentos de línea verticales: el punto final izquierdo de un segmento vertical se define como el que tiene la coordenada y más baja, y los pasos necesarios para procesar dicho segmento son esencialmente los mismos que los necesarios para procesar un segmento no vertical con una pendiente muy alta.
- Defina un segmento de línea como un conjunto cerrado que contiene sus puntos finales. Por lo tanto, dos segmentos de línea que comparten un punto final, o un segmento de línea que contiene un punto final de otro segmento, ambos cuentan como una intersección de dos segmentos de línea.
- Cuando varios segmentos de línea se intersecan en el mismo punto, se crea y procesa un único punto de evento para esa intersección. Las actualizaciones del árbol de búsqueda binaria causadas por este evento pueden implicar la eliminación de cualquier segmento de línea para el cual este sea el punto final derecho, la inserción de nuevos segmentos de línea para los cuales este sea el punto final izquierdo y la inversión del orden de los segmentos de línea restantes que contengan este punto de evento. El resultado de la versión del algoritmo descrito por de Berg et al. (2000) consiste en el conjunto de puntos de intersección de segmentos de línea, etiquetados por los segmentos a los que pertenecen, en lugar del conjunto de pares de segmentos de línea que se intersecan.
En la implementación de LEDA del algoritmo Bentley-Ottmann se utilizó un enfoque similar a las degeneraciones . [4]
Problemas de precisión numérica
Para que el algoritmo sea correcto, es necesario determinar sin aproximación las relaciones arriba-abajo entre el punto final de un segmento de línea y otros segmentos de línea, y priorizar correctamente los diferentes puntos de evento. Por esta razón, es estándar utilizar coordenadas enteras para los puntos finales de los segmentos de línea de entrada, y representar las coordenadas de números racionales de los puntos de intersección de dos segmentos exactamente, utilizando aritmética de precisión arbitraria . Sin embargo, puede ser posible acelerar los cálculos y comparaciones de estas coordenadas utilizando cálculos de punto flotante y probando si los valores calculados de esta manera están lo suficientemente lejos de cero como para que puedan usarse sin ninguna posibilidad de error. [4] Los cálculos aritméticos exactos requeridos por una implementación ingenua del algoritmo Bentley-Ottmann pueden requerir cinco veces más bits de precisión que las coordenadas de entrada, pero Boissonat y Preparata (2000) describen modificaciones al algoritmo que reducen la cantidad necesaria de precisión al doble de la cantidad de bits que las coordenadas de entrada.
Algoritmos más rápidos
La parte O( n log n ) del límite de tiempo para el algoritmo de Bentley–Ottmann es necesaria, ya que hay límites inferiores coincidentes para el problema de detectar segmentos de línea que se cruzan en modelos de árboles de decisión algebraicos de computación. [5] Sin embargo, la dependencia de k , el número de cruces, se puede mejorar. Clarkson (1988) y Mulmuley (1988) proporcionaron algoritmos aleatorios para construir el grafo planar cuyos vértices son puntos finales y cruces de segmentos de línea, y cuyos bordes son las porciones de los segmentos que conectan estos vértices, en el tiempo esperado O( n log n + k ), y este problema de construcción de arreglos se resolvió de manera determinista en el mismo límite de tiempo O( n log n + k ) por Chazelle y Edelsbrunner (1992). Sin embargo, construir este arreglo como un todo requiere un espacio O( n + k ), mayor que el límite espacial O( n ) del algoritmo de Bentley-Ottmann; Balaban (1995) describió un algoritmo diferente que enumera todas las intersecciones en el tiempo O( n log n + k ) y el espacio O( n ).
Si los segmentos de línea de entrada y sus puntos finales forman los bordes y vértices de un grafo conectado (posiblemente con cruces), la parte O( n log n ) del límite de tiempo para el algoritmo de Bentley-Ottmann también puede reducirse. Como muestran Clarkson, Cole y Tarjan (1992), en este caso hay un algoritmo aleatorio para resolver el problema en el tiempo esperado O( n log* n + k ), donde log * denota el logaritmo iterado , una función que crece mucho más lentamente que el logaritmo. Un algoritmo aleatorio estrechamente relacionado de Eppstein, Goodrich y Strash (2009) resuelve el mismo problema en el tiempo O( n + k log ( i ) n ) para cualquier constante i , donde log ( i ) denota la función obtenida iterando la función logaritmo i veces. El primero de estos algoritmos toma tiempo lineal siempre que k sea mayor que n en un factor log ( i ) n , para cualquier constante i , mientras que el segundo algoritmo toma tiempo lineal siempre que k sea menor que n en un factor log ( i ) n . Ambos algoritmos implican la aplicación del algoritmo Bentley-Ottmann a pequeñas muestras aleatorias de la entrada.
Notas
- ^ En la descripción del algoritmo en de Berg et al. (2000), la línea de barrido es horizontal y se mueve verticalmente; este cambio implica intercambiar el uso de las coordenadas x e y de manera consistente a lo largo del algoritmo, pero por lo demás no es de gran importancia para la descripción o el análisis del algoritmo.
- ^ La complejidad espacial no lineal de la versión original del algoritmo fue analizada por Pach y Sharir (1991).
- ^ ab Bartuschka, Mehlhorn y Näher (1997).
- ^ Preparata y Shamos (1985), Teorema 7.6, p. 280.
Referencias
- Balaban, IJ (1995), "Un algoritmo óptimo para encontrar intersecciones de segmentos", Proc. 11th ACM Symp. Computational Geometry , págs. 211–219, doi : 10.1145/220279.220302 , ISBN 0-89791-724-3, S2CID6342118 .
- Bartuschka, U.; Mehlhorn, K .; Näher, S. (1997), "Una implementación robusta y eficiente de un algoritmo de línea de barrido para el problema de intersección de segmentos de línea recta", en Italiano, GF ; Orlando, S. (eds.), Proc. Worksh. Algorithm Engineering, archivado desde el original el 2017-06-06 , consultado el 2009-05-27.
- Bentley, JL ; Ottmann, TA (1979), "Algoritmos para informar y contar intersecciones geométricas", IEEE Transactions on Computers , C-28 (9): 643–647, doi :10.1109/TC.1979.1675432, S2CID 1618521.
- .
- Boissonat, J.-D.; Preparata, FP (2000), "Barrido plano robusto para segmentos que se intersecan" (PDF) , SIAM Journal on Computing , 29 (5): 1401–1421, doi :10.1137/S0097539797329373.
- Brown, KQ (1981), "Comentarios sobre "Algoritmos para informar y contar intersecciones geométricas"", IEEE Transactions on Computers , C-30 (2): 147, doi :10.1109/tc.1981.6312179, S2CID 206622367.
- Chazelle, Bernard ; Edelsbrunner, Herbert (1992), "Un algoritmo óptimo para la intersección de segmentos de línea en el plano", Journal of the ACM , 39 (1): 1–54, doi : 10.1145/147508.147511 , S2CID 785741.
- Chen, EY; Chan, TM (2003), "Un algoritmo de uso eficiente del espacio para la intersección de segmentos", Actas de la 15.ª Conferencia Canadiense sobre Geometría Computacional (PDF).
- Clarkson, KL (1988), "Aplicaciones del muestreo aleatorio en geometría computacional, II", Proc. 4th ACM Symp. Computational Geometry , págs. 1–11, doi : 10.1145/73393.73394 , ISBN 0-89791-270-5, Número de identificación del sujeto 15134654.
- Clarkson, KL ; Cole, R.; Tarjan, RE (1992), "Algoritmos paralelos aleatorios para diagramas trapezoidales", Revista internacional de geometría computacional y aplicaciones , 2 (2): 117–133, doi :10.1142/S0218195992000081. Corrección, 2 (3): 341–343.
- Eppstein, D. ; Goodrich, M. ; Strash, D. (2009), "Algoritmos de tiempo lineal para grafos geométricos con un número sublineal de cruces", Proc. 20th ACM-SIAM Symp. Discrete Algorithms (SODA 2009) , págs. 150–159, arXiv : 0812.0893 , Bibcode :2008arXiv0812.0893E, doi :10.1137/090759112, S2CID 13044724.
- Mulmuley, K. (1988), "Un algoritmo rápido de partición planar, I", Proc. 29th IEEE Symp. Foundations of Computer Science (FOCS 1988) , págs. 580–589, doi :10.1109/SFCS.1988.21974, ISBN 0-8186-0877-3, Número de identificación del sujeto 34582594.
- O'Rourke, J. (1998), "Sección 7.7: Intersección de segmentos", Computational Geometry in C (2.ª ed.), Cambridge University Press, págs. 263-265, ISBN 978-0-521-64976-6.
- Preparata, FP ; Shamos, MI (1985), "Sección 7.2.3: Intersección de segmentos de línea", Geometría computacional: una introducción , Springer-Verlag, págs. 278–287, Bibcode :1985cgai.book.....P.
- Pach, J. ; Sharir, M. (1991), "Sobre la visibilidad vertical en disposiciones de segmentos y el tamaño de la cola en el algoritmo de barrido de línea de Bentley-Ottmann", SIAM Journal on Computing , 20 (3): 460–470, doi :10.1137/0220029, MR 1094525.
- Shamos, MI ; Hoey, Dan (1976), "Problemas de intersección geométrica", 17.ª Conferencia IEEE sobre Fundamentos de la informática (FOCS 1976) , págs. 208-215, doi :10.1109/SFCS.1976.16, S2CID 124804.
Enlaces externos
- Smid, Michiel (2003), Cálculo de intersecciones en un conjunto de segmentos de línea: el algoritmo Bentley-Ottmann (PDF).