Лианг-Барски алгоритам

У области рачунарска графика, Лианг- Барски алгоритам је алгоритам за сецкање линија. Овај алгоритам користи параметричну једначину линије и неједнакости која описује распон прозора за сецкање да би се дефинисала раскрсница између линије и прозора за сецкање. Помоћу ових раскрсница алгоритам зна који део линије треба да се нацрта. Овај алгоритам је ефикаснији од Кохен-Сатерлендов алгоритам. Идеја Лианд – Барски алгоритма је да се ради што више тесирања пре рачунања раскрсница.

Разматрамо прво класичан параметрични облик од почетне линије:

$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\,\!$

Тачка је у прозору за сецкање ако:

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

и

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

која се може представити као 4 неједнакости

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

где 

$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)

Да би се израчунао последњи сегмент линије:To compute the final line segment:

1. 1. Линија која је паралелна са ивицом прозора има pk = 0 за ту границу 
2. 2. Ако за то k, qk<0, линија је потпуно напољу и може бити елиминисана 
3. 3. Када pk<0 линија улази у прозор споља и када је pk>0 линија из прозора иде напоље 
4. 4. За ненула pk, u = qk/pk даје тачку раскрснице 
5. 5. За сваку линију, рачунај u1 и u2. За u1 гледај границе за које је pk<0 (тј. линија иде од споља ка унутра). Узми u1 да буде највећи међу {0, qk/pk}. За u2, гледај границе где је pk>0(тј. линија иде изнутра ка споља). Узми u2 да буде минимум међу {1, qк/pk}. Ако је u1>u2, линија је напољу и самим тим је одбијена. 

Види још

Алгоритми који се користи за исту сврху:

• Сајрус-Беков алгоритам
• Nicholl–Lee–Nicholl
• Fast-clipping

Извори

• 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. 

Спољашње везе

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