Liang-Barski algoritam

U oblasti računarska grafika, Liang- Barski algoritam je algoritam za seckanje linija. Ovaj algoritam koristi parametričnu jednačinu linije i nejednakosti koja opisuje raspon prozora za seckanje da bi se definisala raskrsnica između linije i prozora za seckanje. Pomoću ovih raskrsnica algoritam zna koji deo linije treba da se nacrta. Ovaj algoritam je efikasniji od Kohen-Saterlendov algoritam. Ideja Liand – Barski algoritma je da se radi što više tesiranja pre računanja raskrsnica.

Razmatramo prvo klasičan parametrični oblik od početne linije:

$x=x_{0}+u(x_{1}-x_{0})=x_{0}+u\Delta x\,\!$

$y=y_{0}+u(y_{1}-y_{0})=y_{0}+u\Delta y\,\!$

Tačka je u prozoru za seckanje ako:

$x_{\text{min}}\leq x_{0}+u\Delta x\leq x_{\text{max}}\,\!$

i

$y_{\text{min}}\leq y_{0}+u\Delta y\leq y_{\text{max}}\,\!$,

koja se može predstaviti kao 4 nejednakosti

$up_{k}\leq q_{k},\quad k=1,2,3,4\,\!$,

gde 

$p_{1}=-\Delta x,q_{1}=x_{0}-x_{\text{min}}\,\!$ (left)

$p_{2}=\Delta x,q_{2}=x_{\text{max}}-x_{0}\,\!$ (right)

$p_{3}=-\Delta y,q_{3}=y_{0}-y_{\text{min}}\,\!$ (bottom)

$p_{4}=\Delta y,q_{4}=y_{\text{max}}-y_{0}\,\!$ (top)

Da bi se izračunao poslednji segment linije:To compute the final line segment:

1. 1. Linija koja je paralelna sa ivicom prozora ima pk = 0 za tu granicu 
2. 2. Ako za to k, qk<0, linija je potpuno napolju i može biti eliminisana 
3. 3. Kada pk<0 linija ulazi u prozor spolja i kada je pk>0 linija iz prozora ide napolje 
4. 4. Za nenula pk, u = qk/pk daje tačku raskrsnice 
5. 5. Za svaku liniju, računaj u1 i u2. Za u1 gledaj granice za koje je pk<0 (tj. linija ide od spolja ka unutra). Uzmi u1 da bude najveći među {0, qk/pk}. Za u2, gledaj granice gde je pk>0(tj. linija ide iznutra ka spolja). Uzmi u2 da bude minimum među {1, qk/pk}. Ako je u1>u2, linija je napolju i samim tim je odbijena. 

Vidi još

Algoritmi koji se koristi za istu svrhu:

• Sajrus-Bekov algoritam
• Nicholl–Lee–Nicholl
• Fast-clipping

Izvori

• Liang, Y.D., and Barsky, B., "A New Concept and Method for Line Clipping", ACM Transactions on Graphics, 3(1):1-22, January 1984.
• Liang, Y.D., B.A., Barsky, and M. Slater, Some Improvements to a Parametric Line Clipping Algorithm, CSD-92-688, Computer Science Division, University of California, Berkeley, 1992.
• Foley, James D. (1996). Computer Graphics: Principles and Practice. Addison-Wesley Professional. ISBN 978-0-201-84840-3. 

Spoljašnje veze

• http://hinjang.com/articles/04.html#eight