En geometría computacional , un algoritmo de línea de barrido o un algoritmo de barrido plano es un paradigma algorítmico que utiliza una línea de barrido conceptual o una superficie de barrido para resolver varios problemas en el espacio euclidiano . Es una de las técnicas clave 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) se barre 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 se cruzan o se encuentran en las inmediaciones de la línea de barrido cuando se detiene, y la solución completa está disponible una vez que la línea ha pasado sobre todos los objetos.
Historia
Este enfoque puede rastrearse hasta los algoritmos de renderizado en línea de exploración en gráficos por computadora , seguido de la explotación de este enfoque en los primeros algoritmos de diseño de diseño de circuitos integrados , en los que una descripción geométrica de un circuito integrado se procesaba en tiras paralelas, porque la descripción completa no podía encajar en memoria. [ cita requerida ]
Aplicaciones
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 y, en particular, describieron cómo una combinación del enfoque de línea de exploración con estructuras de datos eficientes ( autoequilibrio árboles de búsqueda binaria ) permite detectar si hay intersecciones entre N segmentos en el plano en la complejidad temporal de O ( N log N ). [1] El algoritmo de Bentley-Ottmann, estrechamente relacionado , utiliza una técnica de línea de barrido para informar todas las K intersecciones entre N segmentos en el plano en la complejidad temporal de O (( N + K ) log N ) y la complejidad espacial de O ( N ). [2]
Desde entonces, este enfoque se ha utilizado para diseñar algoritmos eficientes para una serie de problemas, como la construcción del diagrama de Voronoi ( algoritmo de Fortune ) y la triangulación de Delaunay u operaciones booleanas en polígonos .
Generalizaciones y extensiones
El barrido topológico es una forma de barrido plano con un ordenamiento relajado de los puntos de procesamiento, lo que evita la necesidad de clasificar completamente los puntos; permite que algunos algoritmos de líneas de barrido se realicen de manera más eficiente.
La técnica de calibradores giratorios 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 las líneas en orden ordenado por su pendiente tal como la realiza un algoritmo de calibradores giratorios es dual a la progresión a través de puntos ordenados por sus coordenadas x en un algoritmo de barrido plano.
El enfoque de barrido puede generalizarse a dimensiones superiores.
Referencias
- ^ Shamos, Michael I .; Hoey, Dan (1976), "Problemas de intersección geométrica", Proc. 17º IEEE Symp. Fundamentos de la informática (FOCS '76) , págs. 208–215, doi : 10.1109 / SFCS.1976.16 , S2CID 124804.
- ^ Souvaine, Diane (2008), Intersección de segmento de línea usando un algoritmo de línea de barrido (PDF).