Algoritmo de línea de barrido
En geometría computacional , un algoritmo de barrido de línea o un algoritmo de barrido de 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.
Este enfoque se puede rastrear a algoritmos de línea de exploración de renderizado 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 IC se procesaba en tiras paralelas, porque la descripción completa no podía encajar en 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 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 todos los Kintersecciones entre cualesquiera 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 .
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.
