Hispanopedia Wiki
En gráficos por computadora , el recorte de líneas es el proceso de eliminar ( recortar ) líneas o porciones de líneas que se encuentran fuera del área de interés (una ventana gráfica o volumen de visualización ). Por lo general, se elimina cualquier parte de una línea que esté fuera del área de visualización.
Existen dos algoritmos comunes para el recorte de líneas: Cohen-Sutherland y Liang-Barsky .
Un método de recorte de líneas consta de varias partes. Se realizan pruebas en un segmento de línea dado para determinar si se encuentra fuera del área de visualización o del volumen. Luego, se realizan cálculos de intersección con uno o más límites de recorte. [ 1 ] La determinación de qué porción 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 Cohen-Sutherland (llamado así en honor 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 (área de visualización) es visible.
En 1967, el trabajo de simulación de vuelo realizado por Danny Cohen condujo al desarrollo de los algoritmos de recorte de líneas bidimensionales y tridimensionales para gráficos por computadora Cohen-Sutherland, creados junto 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 dicho cuadro. Con estas intersecciones, sabe qué porción de la línea debe dibujarse. Este algoritmo es significativamente más eficiente que el de Cohen-Sutherland, pero este último realiza las operaciones de aceptación y rechazo triviales mucho más rápido, por lo que debería considerarse si la mayoría de las líneas que se necesitan recortar se encuentran completamente dentro o fuera de la ventana de recorte .
Cyrus-Beck
Muy similar al algoritmo de recorte de líneas de Liang-Barsky. La diferencia radica en que Liang-Barsky es una variación simplificada de Cyrus-Beck optimizada para una ventana de recorte 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 rápido para recortar líneas que reduce la probabilidad de recortar un mismo segmento varias veces, como puede ocurrir con el algoritmo de Cohen-Sutherland. La ventana de recorte se divide en varias áreas, 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 el de Cohen-Sutherland. Las posiciones inicial y final se clasifican según la porción de la cuadrícula de 9 áreas que ocupan. Una instrucción switch extensa salta a un manejador especializado para ese caso. En cambio, Cohen-Sutherland puede requerir varias iteraciones para manejar el mismo caso. [ 3 ]
Algoritmo O (lg N )
Este algoritmo clasifica los vértices con respecto a la línea dada en la forma implícita p : ax + by + c = 0. Dado que se supone que el polígono es convexo y los vértices están ordenados en sentido horario o antihorario, se puede aplicar una búsqueda binaria , lo que resulta en una complejidad temporal de O (lg N ). [ 4 ]
Skala
Este algoritmo se basa en coordenadas homogéneas y dualidad . [ 5 ] Puede utilizarse 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 semiplano dado por una línea p : ax + by + c = 0. El resultado de la clasificación determina las aristas intersectadas 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 puede calcularse a partir de los puntos r 1 , r 2 dados en coordenadas homogéneas directamente utilizando el producto vectorial 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).
Véase también
Referencias
- ↑ Renka, RJ (19 de octubre de 2014). "Recorte de línea" (PDF) . Departamento de Ciencias de la Computación e Ingeniería, Universidad del Norte de Texas . Recuperado el 12 de enero de 2016 .
- ↑ Cyrus, M., Beck, J.: Recorte generalizado bidimensional y tridimensional , Computers & Graphics, vol. 3, n.º 1, págs. 23–28, 1978.
- ↑ Sobkow, Mark S.; Pospisil, Paul; Yang, Yee-Hong (1987). "Un algoritmo rápido de recorte de líneas bidimensional mediante codificación de líneas" . Computers & Graphics . 11 (4): 459–467 .
- ↑ Skala, V. : O (lg N ) Algoritmo de recorte de línea en E2, Computers & Graphics, Pergamon Press, Vol. 18, No. 4, 1994.
- ↑ Skala, V.: Un nuevo enfoque para el recorte de líneas y segmentos de línea en coordenadas homogéneas , The Visual Computer, ISSN 0178-2789, Vol. 21, No. 11, pp. 905–914, Springer Verlag, 2005.
- Recorte (gráficos por computadora)
