Algoritmo de Liang-Barsky

Algoritmo de recorte de línea

En gráficos por computadora , el algoritmo Liang-Barsky (llamado así por You-Dong Liang y Brian A. Barsky ) es un algoritmo de recorte de líneas . El algoritmo 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é porción de la línea debe dibujarse. Por lo tanto, este algoritmo es significativamente más eficiente que Cohen-Sutherland . La idea del algoritmo de recorte Liang-Barsky es hacer tantas pruebas como sea posible antes de calcular las intersecciones de líneas.

El algoritmo utiliza la forma paramétrica de una línea recta:

${\displaystyle x=x_{0}+t(x_{1}-x_{0})=x_{0}+t\Delta x,}$

${\displaystyle y=y_{0}+t(y_{1}-y_{0})=y_{0}+t\Delta y.}$

Un punto está en la ventana de clip, si

${\displaystyle x_{\text{min}}\leq x_{0}+t\Delta x\leq x_{\text{max}}}$

y

${\displaystyle y_{\text{min}}\leq y_{0}+t\Delta y\leq y_{\text{max}},}$

que se puede expresar como las 4 desigualdades

${\displaystyle tp_{i}\leq q_{i},\quad i=1,2,3,4,}$

dónde

${\displaystyle {\begin{aligned}p_{1}&=-\Delta x,&q_{1}&=x_{0}-x_{\text{min}},&&{\text{(left)}}\\p_{2}&=\Delta x,&q_{2}&=x_{\text{max}}-x_{0},&&{\text{(right)}}\\p_{3}&=-\Delta y,&q_{3}&=y_{0}-y_{\text{min}},&&{\text{(bottom)}}\\p_{4}&=\Delta y,&q_{4}&=y_{\text{max}}-y_{0}.&&{\text{(top)}}\end{aligned}}}$

Para calcular el segmento de línea final:

1. Una línea paralela al borde de una ventana de recorte tiene como límite ese borde. ${\displaystyle p_{i}=0}$
2. Si por eso , entonces la línea queda completamente fuera y puede eliminarse. ${\displaystyle i}$ ${\displaystyle q_{i}<0}$
3. Cuando , la línea avanza desde afuera hacia adentro de la ventana del clip, y cuando , la línea avanza desde adentro hacia afuera. ${\displaystyle p_{i}<0}$ ${\displaystyle p_{i}>0}$
4. Para un valor distinto de cero , da como resultado el punto de intersección de la línea y el borde de la ventana (posiblemente proyectado). ${\displaystyle p_{i}}$ ${\displaystyle u=q_{i}/p_{i}}$ ${\displaystyle t}$
5. Las dos intersecciones reales de la línea con los bordes de la ventana, si existen, se describen mediante y , calculados de la siguiente manera. Para , observe los límites para los cuales (es decir, de afuera hacia adentro). Tome como el más grande entre . Para , observe los límites para los cuales (es decir, de adentro hacia afuera). Tome como el mínimo de . ${\displaystyle u_{1}}$ ${\displaystyle u_{2}}$ ${\displaystyle u_{1}}$ ${\displaystyle p_{i}<0}$ ${\displaystyle u_{1}}$ ${\displaystyle \{0,q_{i}/p_{i}\}}$ ${\displaystyle u_{2}}$ ${\displaystyle p_{i}>0}$ ${\displaystyle u_{2}}$ ${\displaystyle \{1,q_{i}/p_{i}\}}$
6. Si , la línea está completamente fuera de la ventana de recorte. Si está completamente dentro de ella. ${\displaystyle u_{1}>u_{2}}$ ${\displaystyle u_{1}<0<1<u_{2}}$

// Algoritmo de recorte de línea de Liang—Barsky #include <iostream> #include <graphics.h> #include <math.h>utilizando el espacio de nombres std ;  // esta función proporciona el float máximo maxi ( float arr [], int n ) { float m = 0 ; for ( int i = 0 ; i < n ; ++ i ) if ( m < arr [ i ]) m = arr [ i ]; return m ; }                          // esta función proporciona el float mínimo mini ( float arr [], int n ) { float m = 1 ; for ( int i = 0 ; i < n ; ++ i ) if ( m > arr [ i ]) m = arr [ i ]; return m ; }                           void liang_barsky_clipper ( float xmin , float ymin , float xmax , float ymax , float x1 , float y1 , float x2 , float y2 ) { // definiendo variables float p1 = - ( x2 - x1 ); float p2 = - p1 ; float p3 = - ( y2 - y1 ); float p4 = - p3 ;                                       flotante q1 = x1 - xmin ; flotante q2 = xmax - x1 ; flotante q3 = y1 - ymin ; flotante q4 = ymax - y1 ;                        float posarr [ 5 ], negarr [ 5 ]; int posición = 1 , negind = 1 ; posar [ 0 ] = 1 ; negar [ 0 ] = 0 ;                rectángulo ( xmin , ymin , xmax , ymax ); // dibujando la ventana de recorte     if (( 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!" ); return ; } if ( p1 != 0 ) { float r1 = q1 / p1 ; float r2 = q2 / p2 ; if ( 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 ; } } si ( p3 != 0 ) { flotante r3 = q3 / p3 ; flotante r4 = q4 / p4 ; si ( p3 < 0 ) { negarr [ negind ++ ] = r3 ; posarr [ posind ++ ] = r4 ; } de lo contrario { negarr [ negind ++ ] = r4 ; posarr [ posind ++ ] = r3 ; } }                                                                                                                      float xn1 , yn1 , xn2 , yn2 ; float rn1 , rn2 ; rn1 = maxi ( negarr , negind ); // máximo de la matriz negativa rn2 = mini ( posarr , posind ); // mínimo de la matriz positiva                  if ( rn1 > rn2 ) { // rechazar outtextxy ( 80 , 80 , "¡La línea está fuera de la ventana de recorte!" ); return ; }           xn1 = x1 + p2 * rn1 ; yn1 = y1 + p4 * rn1 ; // calculando nuevos puntos               yn2 = y1 + p4 * rn2 ;​​​​​​​​              setcolor ( CIAN ); línea ( xn1 , yn1 , xn2 , yn2 ); // el dibujo de la nueva línea     estilo de línea de conjunto ( 1 , 1 , 0 );   línea ( x1 , y1 , xn1 , yn1 ); línea ( x2 , y2 , xn2 , yn2 ); }       int main () { cout << " \n Recorte de línea de Liang-barsky" ; cout << " \n La distribución de la ventana del sistema es: (0,0) en la parte inferior izquierda y (631, 467) en la parte superior derecha" ; cout << " \n Ingrese las coordenadas de la ventana (wxmin, wymin, wxmax, wymax):" ; float xmin , ymin , xmax , ymax ; cin >> xmin >> ymin >> xmax >> ymax ; cout << " \n Ingrese los puntos finales de la línea (x1, y1) y (x2, y2):" ; float x1 , y1 , x2 , y2 ; cin >> x1 >> y1 >> x2 >> y2 ;                                           int gd = DETECTAR , gm ;     // usando la biblioteca winbgim para C++, inicializando el modo gráfico initgraph ( & gd , & gm , "" ); liang_barsky_clipper ( xmin , ymin , xmax , ymax , x1 , y1 , x2 , y2 ); getch (); closegraph (); }             

Véase también

Algoritmos utilizados para el mismo propósito:

• Algoritmo de Cyrus-Beck
• Algoritmo de Nicholl-Lee-Nicholl
• Recorte rápido

Referencias

• Liang, YD, y Barsky, B., "Un nuevo concepto y método para el recorte de líneas", 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. Gráficos por ordenador: principios y práctica . Addison-Wesley Professional, 1996. pág. 117.

Enlaces externos

• http://hinjang.com/articles/04.html#eight
• Skytopia: ¡El algoritmo de recorte de línea de Liang-Barsky en pocas palabras!