En gráficos por computadora , el recorte de líneas es el proceso de eliminar líneas o partes de líneas fuera de un área de interés. Por lo general, se elimina cualquier línea o parte 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. Las pruebas se realizan en un segmento de línea determinado para averiguar si se encuentra fuera del volumen de la vista. Posteriormente, los cálculos de intersección se llevan a cabo 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.
Cohen – Sutherland
En gráficos por computadora, el algoritmo de 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 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 Cohen-Sutherland, creados con Ivan Sutherland.
Liang – Barsky
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 se debe trazar. Este algoritmo es significativamente más eficiente que Cohen-Sutherland, pero Cohen-Sutherland acepta y rechaza 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 .
Cyrus – Beck
Muy similar al algoritmo de recorte de línea de Liang-Barsky. La diferencia es que Liang – Barsky es una variación simplificada de Cyrus – Beck que se optimizó para una ventana de clip rectangular.
El algoritmo de Cyrus-Beck está diseñado 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]
Nicholl – Lee – Nicholl
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, según la posición del punto inicial de la línea que se va a recortar.
Recorte rápido
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 manejador especializado para ese caso. En contraste, Cohen-Sutherland puede tener que iterar varias veces para manejar el mismo caso. [3]
Algoritmo O (lg N )
Este algoritmo clasifica los vértices contra la línea dada en la forma implícita p : ax + por + c = 0. Como se supone que el polígono es convexo y los vértices se ordenan en sentido horario o antihorario, la búsqueda binaria se puede aplicar y conduce a un O (lg N ) complejidad en tiempo de ejecución. [4]
Skala
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 contra un medio espacio dado por una línea p : ax + por + c = 0. El resultado de la clasificación determina los bordes cortados por la línea p . El algoritmo es simple, fácil de implementar y también extensible 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 usando el producto cruzado como
- p = r 1 × r 2 = ( x 1 , y 1 , w 1 ) × ( x 2 , y 2 , w 2 )
o como
- p = r 1 × r 2 = ( x 1 , y 1 , 1) × ( x 2 , y 2 , 1).
Ver también
Referencias
- ↑ Renka, RJ (19 de octubre de 2014). "Recorte de línea" (PDF) . Departamento de Ingeniería y Ciencias de la Computación, Universidad del Norte de Texas . Consultado el 12 de enero de 2016 .
- ^ Cyrus, M., Beck, J .: Recorte generalizado de dos y tres dimensiones , Computadoras y gráficos, vol. 3, núm. 1, págs. 23-28, 1978.
- ^ Mark S. Sobkow, Paul Pospisil y Yee-Hong Yang. Un rápido algoritmo de recorte de línea bidimensional a través de codificación de línea // Computadora y gráficos, vol. 11, núm. 4, págs. 459–467, 1987.
- ^ Skala, V .:Algoritmo de recorte de línea O (lg N ) en E2, Computadoras y gráficos, Pergamon Press, Vol. 18, N ° 4, 1994.
- ^ Skala, V .: Un nuevo enfoque para el recorte de línea y segmento de línea en coordenadas homogéneas , The Visual Computer, ISSN 0178-2789, Vol. 21, núm. 11, págs. 905–914, Springer Verlag, 2005.