En gráficos por computadora , el recorte de líneas es el proceso de eliminar ( recortar ) líneas o porciones de líneas fuera de un área de interés (una ventana gráfica o un volumen de vista ). Normalmente, se elimina cualquier parte de una línea que esté fuera del área de visualización.
Hay dos algoritmos comunes para el recorte de líneas: Cohen-Sutherland y Liang-Barsky .
Un método de recorte de línea consta de varias partes. Se realizan pruebas en un segmento de línea determinado para determinar si se encuentra fuera del área o volumen de la vista. Luego, se llevan a cabo cálculos de intersección con uno o más límites de recorte. [1] La determinación de qué parte de la línea está dentro o fuera del volumen de recorte se realiza procesando los puntos finales de la línea con respecto a la intersección.
En gráficos por computadora, el algoritmo Cohen-Sutherland (llamado así por Danny Cohen e Ivan Sutherland) es un algoritmo de recorte de líneas. El algoritmo divide un espacio 2D en 9 regiones, de las cuales sólo la parte media (ventana gráfica) es visible.
En 1967, el trabajo de simulación de vuelo de Danny Cohen condujo al desarrollo de los algoritmos de recorte de líneas bidimensionales y tridimensionales de gráficos por computadora Cohen-Sutherland, creados con Ivan Sutherland.
El algoritmo de Liang-Barsky utiliza la ecuación paramétrica de una línea y desigualdades que describen el rango del cuadro de recorte para determinar las intersecciones entre la línea y el cuadro de recorte. Con estas intersecciones sabe qué parte de la línea debe trazarse. Este algoritmo es significativamente más eficiente que Cohen-Sutherland, pero Cohen-Sutherland realiza aceptaciones y rechazos triviales mucho más rápido, por lo que se debe considerar si la mayoría de las líneas que necesita recortar estarían completamente dentro o fuera de la ventana de recorte .
Muy similar al algoritmo de recorte de líneas de Liang-Barsky. La diferencia es que Liang-Barsky es una variación simplificada de Cyrus-Beck que fue optimizada para una ventana de clip rectangular.
El algoritmo de Cyrus-Beck está destinado principalmente a recortar una línea en forma paramétrica contra un polígono convexo en 2 dimensiones o contra un poliedro convexo en 3 dimensiones. [2]
El algoritmo de Nicholl-Lee-Nicholl es un algoritmo de recorte de línea rápido que reduce las posibilidades de recortar un solo segmento de línea varias veces, como puede suceder en el algoritmo de Cohen-Sutherland. La ventana de recorte se divide en varias áreas diferentes, dependiendo de la posición del punto inicial de la línea a recortar.
Este algoritmo tiene similitudes con Cohen-Sutherland. Las posiciones inicial y final se clasifican según la parte de la cuadrícula de 9 áreas que ocupan. Una declaración de cambio grande salta a un controlador especializado para ese caso. Por el contrario, Cohen-Sutherland puede tener que repetir varias veces para manejar el mismo caso. [3]
Este algoritmo clasifica los vértices frente a la línea dada en la forma implícita p : ax + by + c = 0. Como se supone que el polígono es convexo y los vértices están ordenados en el sentido de las agujas del reloj o en el sentido contrario a las agujas del reloj, se puede aplicar la búsqueda binaria y conduce a una O (lg N ) complejidad del tiempo de ejecución. [4]
Este algoritmo se basa en coordenadas homogéneas y dualidad . [5] Se puede utilizar para recortar líneas o segmentos de línea contra una ventana rectangular, así como contra un polígono convexo. El algoritmo se basa en clasificar un vértice de la ventana de recorte frente a un medio espacio dado por una recta p : ax + by + c = 0. El resultado de la clasificación determina las aristas intersecadas por la recta p . El algoritmo es simple, fácil de implementar y también extensible a una ventana convexa. La recta o segmento de recta p se puede calcular a partir de los puntos r 1 , r 2 dados en coordenadas homogéneas directamente usando el producto cruzado como
o como