Пређи на садржај

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

С Википедије, слободне енциклопедије

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

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

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

и

,

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

,

где 

(left)
(right)
(bottom)
(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, линија је напољу и самим тим је одбијена. 

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

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

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

[уреди | уреди извор]