Sajrus-Bekov algoritam
Sajrus-Bekov algoritam (engl. Cyrus-Beck) je geometrijski algoritam za seckanje linije. Seckanje linije predstavlja odstranjivanje dela duži (ili prave), koja je izvan neke posmatrane oblasti. Potrebno je da bude ispunjen uslov da je oblast konveksan poligon.
Uvod[uredi | uredi izvor]
U ovom algoritmu se koristi parametarska jednačina prave. Prava je zadata preko dve različite tačke, P0 i P1, tako da njena parametarska jednačina glasi . Parametarska jednačina prave koristi jednu tačku prave i vektor pravca. Vektor pravca se dobija tako što se oduzmu koordinate dve date tačke (P1-P0). Parametar t fizički posmatrano predstavlja vreme, a geometrijski posmatrano u pravcu vektora pravca. Ovom jednačinom su opisane sve jednačine na pravoj. (U slučaju duži, parametar t uzima vrednosti između 0 i 1)
Algoritam[uredi | uredi izvor]
Ukoliko se traži presek prave sa svim stranicama posmatrane oblasti. Da bi se našao presek P(t) prave sa nekom stranicom, potrebno je prvo izračunati vektor normale N na stranicu i uočiti neku proizvoljnu tačku na pravoj, Pe (to može da bude jedno od temena). Vektor P(t)-Pe je normalan u odnosu na vektor N, pa je njihov proizvod jednak nuli. Znači potrebno je naći takvo t, koje zadovoljava . Kada se jednačina reši po t, dobije se . Ovde je potrebno pokriti i specijalni slučaj kada su prava i stranica paralelne (tada ova formula ne važi).
Na ovaj način su pronađene presečne tačke sa svim stranicama oblasti. Zatim se sve ove tačke klasifikuju na potencijalno ulazne i potencijalno izlazne. Tačka je potencijalno ulazna ukoliko vektor pravca sa vektorom normale stranice zaklapa ugao veći od 90° (N*(P1-P0)<0), a potencijalno izlazna ukoliko je ovaj ugao manji od 90° (N*(P1-P0)>0).
Zatim se sve presečne tačke sortiraju (po parametru t), i uočimo najveću od potencijalno ulaznih tačaka, MAX Pu i najmanju od potencijalno izlaznih tačaka, MIN Pi. Ukoliko uočena ulazna tačka dolazi pre izlazne, deo prave koji je unutar oblasti je između tačaka MAX Pu i MIN Pi. U suprotnom prava nema presek sa oblašću.
Složenost[uredi | uredi izvor]
Ukoliko se pretpostavi da poligon ima n stranica. Presek prave sa svakom od stranica se nalazi u konstantnom vremenu, pa se svi preseci nalaze u linearnom vremenu, (vidi: notacija velikog O). Presečne tačke je potrebno sortirati, a složenost sortiranja je . Pronalaženje najveće ulazne i najmanje izlazne tačke se sprovodi prolaskom kroz sortirani niz (složenost ), tako da je sveukupna složenost algoritma .
