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:
Tačka je u prozoru za seckanje ako:
i
- ,
koja se može predstaviti kao 4 nejednakosti
- ,
gde
- (left)
- (right)
- (bottom)
- (top)
Da bi se izračunao poslednji segment linije:To compute the final line segment:
- 1. Linija koja je paralelna sa ivicom prozora ima pk = 0 za tu granicu
- 2. Ako za to k, qk<0, linija je potpuno napolju i može biti eliminisana
- 3. Kada pk<0 linija ulazi u prozor spolja i kada je pk>0 linija iz prozora ide napolje
- 4. Za nenula pk, u = qk/pk daje tačku raskrsnice
- 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š uredi
Algoritmi koji se koristi za istu svrhu:
- Sajrus-Bekov algoritam
- Nicholl–Lee–Nicholl
- Fast-clipping
Izvori uredi
- 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.