En geometría computacional , un algoritmo de línea de barrido o algoritmo de barrido plano es un paradigma algorítmico que utiliza una línea de barrido conceptual o una superficie de barrido para resolver diversos problemas en el espacio euclidiano . Es una de las técnicas críticas en geometría computacional.
La idea detrás de los algoritmos de este tipo es imaginar que una línea (a menudo una línea vertical) recorre o se mueve a través del plano, deteniéndose en algunos puntos. Las operaciones geométricas están restringidas a objetos geométricos que intersecan o están en las inmediaciones de la línea de barrido cuando esta se detiene, y la solución completa está disponible una vez que la línea ha pasado por todos los objetos.
Este enfoque se puede rastrear hasta los algoritmos de línea de exploración de renderizado en gráficos de computadora , seguidos por la explotación de este enfoque en los primeros algoritmos de diseño de circuitos integrados , en los que una descripción geométrica de un CI se procesaba en tiras paralelas porque la descripción completa no podía caber en la memoria. [ cita requerida ]
La aplicación de este enfoque condujo a un gran avance en la complejidad computacional de los algoritmos geométricos cuando Shamos y Hoey presentaron algoritmos para la intersección de segmentos de línea en el plano en 1976. En particular, describieron cómo una combinación del enfoque de línea de barrido con estructuras de datos eficientes ( árboles de búsqueda binaria autoequilibrados ) permite detectar si hay intersecciones entre N segmentos en el plano en una complejidad temporal de O ( N log N ) . [1] El algoritmo Bentley-Ottmann, estrechamente relacionado , utiliza una técnica de línea de barrido para informar todas las K intersecciones entre N segmentos cualesquiera en el plano en una complejidad temporal de O(( N + K ) log N ) y una complejidad espacial de O( N ) . [2]
Desde entonces, este enfoque se ha utilizado para diseñar algoritmos eficientes para una serie de problemas de geometría computacional, como la construcción del diagrama de Voronoi ( algoritmo de Fortune ) y la triangulación de Delaunay o las operaciones booleanas sobre polígonos .
El barrido topológico es una forma de barrido plano con un ordenamiento simple de puntos de procesamiento, lo que evita la necesidad de ordenar completamente los puntos; permite que algunos algoritmos de línea de barrido se realicen de manera más eficiente.
La técnica de calibradores rotatorios para diseñar algoritmos geométricos también puede interpretarse como una forma de barrido plano, en el dual proyectivo del plano de entrada: una forma de dualidad proyectiva transforma la pendiente de una línea en un plano en la coordenada x de un punto en el plano dual, por lo que la progresión a través de líneas en orden ordenado por su pendiente como se realiza mediante un algoritmo de calibradores rotatorios es dual a la progresión a través de puntos ordenados por sus coordenadas x en un algoritmo de barrido plano. [ cita requerida ]
El enfoque de barrido puede generalizarse a dimensiones superiores. [3]