Seckanje linija

U oblasti računarska grafika, secekanje linija je proces koji eliminiše linije ili delove linija koje se ne nalaze u oblasti interesa. Tako da bilo koja linija ili deo nje koji se ne nalazi u toj oblasti biva odstranjen.

P1

Postoje dva klasična algoritma za seckanje linija: Koen-Saderlend algoritam i Liang-Barski algoritam.

Metoda seckanja linija se sastoji iz različitih delova. Prvo možemo da testiramo određen segment linije da bismo otrkili da li leži potpuno van oblasti interesa. Mora se gledati postojanje raskrsnica tj preseka linija.

Linija se procesuira unutar oblasti kao i spolja tako što se gledaju gde se linije završavaju. Linija čija se oba završetka nalaze unutar oblasti se čuva, a linija kojoj se jedan ili oba kraju završavaju van oblasti interesa mora da se danje procesuira jer nije moguća momentalna procena njene tačne lokacije zbog mogućnosti postojanja nekoliko raskrsnica.

Koen–Saderland

Glavni članak: Koen-Saderlandov algoritam

Ovo je jedan od algoritama za secaknje linija. Algoritam deli dvodimenzioni prostor na 9 manjih regija, od kojih je samo srednji deo, tačka pogleda, vidljiv.

1967. simulacija avionskog leta Denija Koena je dovela do razvoja Koen–Saderlandovog algoritma koji radi dvodimenzionim i trodimenzionim algoritmima koje je kreirao Ivan Saderland.

Liang–Barski

Glavni članak: Liang–Barski algoritam

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 Koen-Saderland-ovog algoritma. Ideja Liand – Barski algoritma je da se radi što više tesiranja pre računanja raskrsnica.

Sajrus–Bek

Ovaj algoritam je vrlo sličan prethodnom (Liang–Barski). Razlika je u tome što je Liang–Barski pojednostavljena varijacija Sajrus–Bek- ovog algoritma koji vrši optimizaciju za pravougaoni prozor za seckanje.

Sajrus – Bek ima složenost O(N), i primarno je namenjen za seckanje linije u parametričnom obliku koja se nalazi na konveksnom mnogouglu u dve dimenzije ili poliedra u tri dimenzije.

Nišol–Li–Nišol

Ovaj algoritam je brz algoritam za ceskanje linija koji smanjuje šanse seckanja segmenata iste linije iz nekoliko puta, kao što može da se desi u Koen – Saderladovom algoritmu. Prozor za seckanje se deli na nekoliko različitih oblasti, u zavisnosti od pozicije početne tačke linije koja treba da se secka.

Brzo seckanje

Ovaj algoritam ima sličnosti sa Koen–Saderlandovim algoritmom. Početne i krajnje pozicije se klasifikuju po tome koji deo od 9 oblasti one zauzimaju. Velika switch naredba skače na sprecijalizovani hendler za svaki mogući slučaj. U kontrastu, Koen–Saderland će iterativno da prođe nekoliko puta da bi rešio taj problem.

O(lg N) algoritam

Ovaj algoritam klasifikuje čvorove protiv zadate linije u implicitnom obliku: p: ax + by + c = 0. Kako se pretpostavlja da je mnogougao konveksan i da su čvorovi poređani suprotno od kazaljke na satu možemo zaključiti da se vreme potrebno da se izvrši ovaj algoritam O(lg N) složenosti.

Skala

Ovaj algoritam je zasnovan na homogenim koordinatama i dualnosti. Može da se koristi za seckanje linija ili njihovih segmenata uz upotrebu pravougaonog prozora ili konveksnog mnogougla. Algoritam se zasniva na klasifikaciji čvorova pomoću polu-prostora koji zadaje linija : p: ax + by + c = 0. Rezultat ove klasifikacija određuje ivice koje se presečene linijom p. Algoritam je vrlo jednostavan, jednostavan za implementaciju i moguće ga je unaprediti da radi i sa konveksnim prozorom. Linija ili njen segment p može da se izračuna od tačaka x1, x2 koje su zadate pomoću homogenih koordinata direktno koristeći međuproizvod kao  p = x1 x x2 = [x1,y1,w1] x [x2,y2,w2] or as p = x1 x x2 = [x1,y1,1] x [x2,y2,1]

Vidi još

• Seckanje (računarska grafika)