En gráficos por computadora , el algoritmo de Liang-Barsky (llamado así por You-Dong Liang y Brian A. Barsky ) es un algoritmo de recorte de líneas . El algoritmo de Liang-Barsky utiliza la ecuación paramétrica de una línea y desigualdades que describen el rango de la ventana de recorte para determinar las intersecciones entre la línea y la ventana 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 . La idea del algoritmo de recorte de Liang-Barsky es realizar tantas pruebas como sea posible antes de calcular las intersecciones de líneas.
Considere primero la forma paramétrica habitual de una línea recta:
Un punto está en la ventana del clip, si
y
que se puede expresar como las 4 desigualdades
dónde
Para calcular el segmento de línea final:
- Una línea paralela al borde de una ventana de recorte tiene para ese límite.
- Si por eso , , entonces la línea está completamente afuera y se puede eliminar.
- Cuándo , la línea avanza de afuera hacia adentro de la ventana del clip, y cuando , la línea avanza de adentro hacia afuera.
- Para distinto de cero , da el punto de intersección.
- Para cada línea, calcule y . Para, mira los límites para los que (es decir, de afuera hacia adentro). Llevar ser el más grande entre . Para, mira los límites para los que (es decir, de adentro hacia afuera). Llevar ser el mínimo de . Si, la línea está fuera y por lo tanto rechazada.
// Liang - Algoritmo de recorte de línea de Barsky #include #include #include usando el espacio de nombres std ;// esta función da el máximo float maxi ( float arr [], int n ) { float m = 0 ; para ( int i = 0 ; i < n ; ++ i ) if ( m < arr [ i ]) m = arr [ i ]; return m ; }// esta función da el mínimo flotante mini ( float arr [], int n ) { float m = 1 ; para ( int i = 0 ; i < n ; ++ i ) if ( m > arr [ i ]) m = arr [ i ]; return m ; }void liang_barsky_clipper ( float xmin , flotador ymin , flotador xmax , flotador ymax , flotador x1 , flotador y1 , flotador x2 , flotador y2 ) { variables de // definen flotar p1 = - ( x2 - x1 ); flotar p2 = - p1 ; flotar p3 = - ( y2 - y1 ); flotar p4 = - p3 ; flotar q1 = x1 - xmin ; flotar q2 = xmax - x1 ; flotar q3 = y1 - ymin ; flotador q4 = ymax - y1 ; flotador posarr [ 5 ], negarr [ 5 ]; int posind = 1 , negind = 1 ; posarr [ 0 ] = 1 ; negarr [ 0 ] = 0 ; rectángulo ( xmin , ymin , xmax , ymax ); // dibujando la ventana de recorte si (( p1 == 0 && q1 < 0 ) || ( p2 == 0 && q2 < 0 ) || ( p3 == 0 && q3 < 0 ) || ( p4 == 0 && q4 < 0 )) { outtextxy ( 80 , 80 , "¡La línea es paralela a la ventana de recorte!" ); volver ; } if ( p1 ! = 0 ) { float r1 = q1 / p1 ; flotar r2 = q2 / p2 ; si ( p1 < 0 ) { negarr [ negind ++ ] = r1 ; // para p1 negativo, agréguelo a la matriz negativa posarr [ posind ++ ] = r2 ; // y agregue p2 a la matriz positiva } else { negarr [ negind ++ ] = r2 ; posarr [ posind ++ ] = r1 ; } } if ( p3 ! = 0 ) { float r3 = q3 / p3 ; flotar r4 = q4 / p4 ; si ( p3 < 0 ) { negarr [ negind ++ ] = r3 ; posarr [ posind ++ ] = r4 ; } else { negarr [ negind ++ ] = r4 ; posarr [ posind ++ ] = r3 ; } } flotar xn1 , yn1 , xn2 , yn2 ; flotar rn1 , rn2 ; rn1 = maxi ( negarr , negind ); // máximo de matriz negativa rn2 = mini ( posarr , posind ); // mínimo de matriz positiva if ( rn1 > rn2 ) { // rechazar outtextxy ( 80 , 80 , "¡La línea está fuera de la ventana de recorte!" ); volver ; } xn1 = x1 + p2 * rn1 ; yn1 = y1 + p4 * rn1 ; // calcular nuevos puntos xn2 = x1 + p2 * rn2 ; yn2 = y1 + p4 * rn2 ; setColor ( CYAN ); línea ( xn1 , yn1 , xn2 , yn2 ); // el dibujo de la nueva línea setlinestyle ( 1 , 1 , 0 ); línea ( x1 , y1 , xn1 , yn1 ); línea ( x2 , y2 , xn2 , yn2 ); }int main () { cout << " \ n Recorte de línea Liang-barsky" ; cout << " \ n El gasto de la ventana del sistema es: (0,0) en la parte inferior izquierda y (631, 467) en la parte superior derecha" ; cout << " \ n Introduzca las coordenadas de la ventana (wxmin, wxmax, wymin, wymax):" ; flotador xmin , xmax , ymin , ymax ; cin >> xmin >> ymín >> xmax >> ymáx ; cout << " \ n Introduzca los puntos finales de la línea (x1, y1) y (x2, y2):" ; flotar x1 , y1 , x2 , y2 ; cin >> x1 >> y1 >> x2 >> y2 ; int gd = DETECTAR , gm ; // usando la biblioteca winbgim para C ++, inicializando el modo de gráficos initgraph ( & gd , & gm , "" ); liang_barsky_clipper ( xmin , ymin , xmax , ymax , x1 , y1 , x2 , y2 ); getch (); closegraph (); }
Ver también
Algoritmos utilizados para el mismo propósito:
Referencias
- Liang, YD y Barsky, B., " A New Concept and Method for Line Clipping ", ACM Transactions on Graphics , 3 (1): 1–22, enero de 1984.
- Liang, YD, BA, Barsky y M. Slater, Algunas mejoras en un algoritmo de recorte de línea paramétrico , CSD-92-688, División de Ciencias de la Computación, Universidad de California, Berkeley, 1992.
- James D. Foley. Infografía: principios y práctica . Addison-Wesley Professional, 1996. pág. 117.