Liang–Barsky-algoritm

Inom datorgrafik är Liang –Barsky-algoritmen (uppkallad efter You-Dong Liang och Brian A. Barsky ) en linjeklippningsalgoritm . Liang–Barsky-algoritmen använder den parametriska ekvationen för en linje och olikheter som beskriver intervallet för klippfönstret för att bestämma skärningspunkterna mellan linjen och klippfönstret . Med dessa skärningar vet den vilken del av linjen som ska dras. Så den här algoritmen är betydligt effektivare än Cohen–Sutherland . Tanken med Liang–Barsky-klippningsalgoritmen är att göra så mycket testning som möjligt innan man beräknar linjekorsningar.

Betrakta först den vanliga parametriska formen av en rät linje:

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

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

En punkt finns i klippfönstret, om

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

och

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

som kan uttryckas som de 4 ojämlikheterna

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

var

{\begin{aligned}p_{1}&=-\Delta x,&q_{1}&=x_{0}-x_{\text{min}},&&{\text{(vänster )}}\\p_{2}&=\Delta x,&q_{2}&=x_{\text{max}}-x_{0},&&{\text{(höger)}}\\p_{3 }&=-\Delta y,&q_{3}&=y_{0}-y_{\text{min}},&&{\text{(nederst)}}\\p_{4}&=\Delta y, &q_{4}&=y_{\text{max}}-y_{0}.&&{\text{(top)}}\end{aligned}}

Så här beräknar du det sista linjesegmentet:

En linje parallell med en klippfönsterkant har $p_{i}=0$ för den gränsen.
Om för det $i$ , $q_{i}<0$ , så är linjen helt utanför och kan elimineras.
När $p_{i}<0$ fortsätter linjen utanför till innanför klippfönstret, och när $p_{i}>0$ fortsätter linjen inifrån och ut.
För icke-noll $p_{i}$ ger $u=q_{i}/p_{i}$ / $t$ skärningspunkten för linjen och fönsterkanten (eventuellt projicerad).
De två faktiska skärningarna av linjen med fönsterkanterna, om de finns, beskrivs av $u_{1}$ och $u_{2}$ , beräknade enligt följande. För $u_{1}$ , titta på gränser för vilka $p_{i}<0$ (dvs utanför till insidan). Ta $u_{1}$ för att vara störst bland $\{0,q_{i}/p_{i}\}$ . För $u_{2}$ , titta på gränser för vilka $p_{i}>0$ (dvs. inifrån till utanför). Ta $u_{2}$ som minimum av $\{1,q_{i}/p_{i}\}$ .
Om $u_{1}>u_{2}$ är linjen helt utanför klippfönstret. Om $u_{1}<0<1<u_{2}$ är det helt inuti det.






  


    
     0
      0    
       
        
   



     
     
      0    
       
        
   


        
                                  
  
       
     
       
     

       
       
       
       

    
        
  0  
  0  0

      

     0    0    0    0    0    0    0    0 
        
      
  
     0 
         
         
       0 
         
         
      
        
        
    
  
     0 
         
         
       0 
        
        
      
        
        
    
  

      
    
      
      

        
      
    
  

        
         

        
        

  

      

    0

     
     


  
    
    
    
      
          
    
      
          

      

  
    
         
  
  
 // Liang—Barsky linjeklippningsalgoritm  #include  <iostream>  #include  <graphics.h>  #include  <math.h>  med  namnutrymme  std  ;  // denna funktion ger den maximala  float  maxi  (  float  arr  [],  int  n  )  {  float  m  =  ;  för  (  int  i  =  ;  i  <  n  ;  ++  i  )  if  (  m  <  arr  [  i  ])  m  =  arr  [  i  ];  returnera  m  ;  }  // den här funktionen ger minimum  float  mini  (  float  arr  [],  int  n  )  {  float  m  =  1  ;  för  (  int  i  =  ;  i  <  n  ;  ++  i  )  if  (  m  >  arr  [  i  ])  m  =  arr  [  i  ];  returnera  m  ;  }  void  liang_barsky_clipper  (  float  xmin  ,  float  ymin  ,  float  xmax  ,  float  ymax  ,  float  x1  ,  float  y1  ,  float  x2  ,  float  y2  )  {  // definierar variabler  float  p1  =  -  (  x2  -  x1  );  float  p2  =  -  pl  ;  float  p3  =  -  (  y2  -  yl  );  float  p4  =  -  p3  ;  float  q1  =  x1  -  xmin  ;  float  q2  =  xmax  -  x1  ;  float  q3  =  y1  -  ymin  ;  float  q4  =  ymax  -  y1  ;  float  posarr  [  5  ],  negarr  [  5  ];  int  posind  =  1  ,  negind  =  1  ;  posarr  [  ]  =  1  ;  negarr  [  ]  =  ;  rektangel  (  xmin  ,  ymin  ,  xmax  ,  ymax  );  // rita urklippsfönstret  om  ((  p1  ==  &&  q1  <  )  ||  (  p2  ==  &&  q2  <  )  ||  (  p3  ==  &&  q3  <  )  ||  (  p4  ==  &&  q4  <  ))  {  outtextxy  (  80  ,  80  ,  "Linjen är parallell med klippfönstret!" )  ;  återvända  ;  }  if  (  p1  !=  )  {  float  r1  =  q1  /  p1  ;  float  r2  =  q2  /  p2  ;  if  (  p1  <  )  {  negarr  [  negind  ++  ]  =  r1  ;  // för negativ p1, lägg till den till negativ array  posarr  [  posind  ++  ]  =  r2  ;  // och lägg till p2 till positiv array  }  else  {  negarr  [  negind  ++  ]  =  r2  ;  posarr  [  posind  ++  ]  =  r1  ;  }  }  if  (  p3  !=  )  {  float  r3  =  q3  /  p3  ;  float  r4  =  q4  /  p4  ;  if  (  p3  <  )  {  negarr  [  negind  ++  ]  =  r3  ;  posarr  [  posind  ++  ]  =  r4  ;  }  annat  {  negarr  [  negind  ++  ]  =  r4  ;  posarr  [  posind  ++  ]  =  r3  ;  }  }  float  xn1  ,  yn1  ,  xn2  ,  yn2  ;  flyta  rn1  ,  rn2  ;  rn1  =  maxi  (  negarr  ,  negind  );  // maximum av negativ array  rn2  =  mini  (  posarr  ,  posind  );  // minimum av positiv array  if  (  rn1  >  rn2  )  {  // reject  outtextxy  (  80  ,  80  ,  "Linjen är utanför klippfönstret!"  );  återvända  ;  }  xnl  =  xl  +  p2  *  rnl  ;  ynl  =  yl  +  p4  *  rnl  ;  // beräkna nya punkter  xn2  =  x1  +  p2  *  rn2  ;  yn2  =  yl  +  p4  *  rn2  ;  setcolor  (  CYAN  );  linje  (  xnl  ,  ynl  ,  xn2  ,  yn2  );  // ritningen av den nya linjen  setlinestyle  (  1  ,  1  ,  );  linje  (  xl  ,  yl  ,  xnl  ,  ynl  );  linje  (  x2  ,  y2  ,  xn2  ,  yn2  );  }  int  main  ()  {  cout  <<  "  \n  Liang-barsky linjeklippning"  ;  cout  <<  "  \n  Systemfönstrets utgifter är: (0,0) längst ner till vänster och (631, 467) uppe till höger"  ;  cout  <<  "  \n  Ange koordinaterna för fönstret(wxmin, wymin, wxmax, wymax):"  ;  flyta  xmin  ,  ymin  ,  xmax  ,  ymax  ;  cin  >>  xmin  >>  ymin  >>  xmax  >>  ymax  ;  cout  <<  "  \n  Ange slutpunkterna för linjen (x1, y1) och (x2, y2):"  ;  flyta  xl  ,  y1  ,  x2  ,  y2  ;  cin  >>  x1  >>  y1  >>  x2  >>  y2  ;  int  gd  =  DETECT  ,  gm  ;  //  använder winbgim-biblioteket för C++, initialiserar grafikläget  initgraph  (  &  gd  ,  &  gm ,   ""  );  liang_barsky_clipper  (  xmin  ,  ymin  ,  xmax  ,  ymax  ,  x1  ,  y1  ,  x2  ,  y2  );  getch  ();  closegraph  ();  }

Se även

Algoritmer som används för samma ändamål:

Liang, YD och Barsky, B., " A New Concept and Method for Line Clipping ", ACM Transactions on Graphics , 3(1):1–22, januari 1984.
Liang, YD, BA, Barsky och M. Slater, Some Improvements to a Parametric Line Clipping Algorithm ^{[ död länk ]} , CSD-92-688, Computer Science Division, University of California, Berkeley, 1992.
James D. Foley. Datorgrafik: principer och praxis . Addison-Wesley Professional, 1996. sid. 117.

externa länkar