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

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

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

$x=x_0+u(x_1-x_0)=x_0+u\mathrm{\Delta }x$

$y=y_0+u(y_1-y_0)=y_0+u\mathrm{\Delta }y$

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

$x_{\text{min}}\le x_0+u\mathrm{\Delta }x\le x_{\text{max}}$

и

$y_{\text{min}}\le y_0+u\mathrm{\Delta }y\le y_{\text{max}}$,

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

$u{p}_k\le q_k,k=1,2,3,4$,

где 

$p_1=-\mathrm{\Delta }x,q_1=x_0-x_{\text{min}}$ (left)

$p_2=\mathrm{\Delta }x,q_2=x_{\text{max}}-x_0$ (right)

$p_3=-\mathrm{\Delta }y,q_3=y_0-y_{\text{min}}$ (bottom)

$p_4=\mathrm{\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.
• Шаблон:Cite book

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

• -{R|http://hinjang.com/articles/04.html#eight}-