En gráficos por computadora , el recorte de líneas es el proceso de eliminar ( recortar ) líneas o partes de líneas que se encuentran fuera de un área de interés (una ventana gráfica o un volumen de visualización ). Por lo general, se elimina cualquier parte de una línea que se encuentre 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 averiguar si se encuentra fuera del área o volumen de visualización. Luego, se realizan 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 de Cohen-Sutherland (que debe su nombre a 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 solo la parte central (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 de 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é porción de la línea debe dibujarse. 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 debería considerarse en su lugar 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ínea de Liang-Barsky. La diferencia es que Liang-Barsky es una variante simplificada de Cyrus-Beck que se optimizó para una ventana de recorte rectangular.
El algoritmo Cyrus-Beck está pensado principalmente para 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 Nicholl–Lee–Nicholl es un algoritmo rápido de recorte de líneas que reduce las posibilidades de recortar un mismo segmento de línea varias veces, como puede suceder en el algoritmo Cohen–Sutherland. La ventana de recorte se divide en varias áreas diferentes, según la posición del punto inicial de la línea que se va a recortar.
Este algoritmo tiene similitudes con Cohen-Sutherland. Las posiciones de inicio y fin se clasifican según la porción de la cuadrícula de 9 áreas que ocupan. Una sentencia switch grande salta a un controlador especializado para ese caso. Por el contrario, Cohen-Sutherland puede tener que iterar varias veces para manejar el mismo caso. [3]
Este algoritmo clasifica los vértices contra 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 sentido contrario, se puede aplicar la búsqueda binaria y conduce a una complejidad de tiempo de ejecución de O (lg N ). [4]
Este algoritmo se basa en coordenadas homogéneas y dualidad . [5] Puede utilizarse para el recorte de líneas o segmentos de líneas 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 contra un semiespacio dado por una línea p : ax + by + c = 0. El resultado de la clasificación determina los bordes intersectados por la línea p . El algoritmo es simple, fácil de implementar y extensible también a una ventana convexa. La línea o segmento de línea p se puede calcular a partir de los puntos r 1 , r 2 dados en coordenadas homogéneas directamente utilizando el producto vectorial como
o como