Korisnik:Sv4i8/prevod2

Algoritam pomerajuće prave

U računarskoj geometriji, algoritam „pomerajuće prave“ ili „sweep line“ algoritam je algoritamska paradigma koja koristi konceptualnu pravu ili površ koja se „pomera“ kako bi rešila različite probleme u Euklidskom prostoru. Ovo je jedna od ključnih tehnika u računarskoj geometriji.

Ideja iza ovih algoritama je zamišljanje da se prava (često vertikalna) „pomera“ preko ravni, zaustavljajući se na određenim tačkama. Geometrijske operacije su ograničene na objekte koji se presecaju ili se nalaze u neposrednoj blizini ove prave kada se ona zaustavi, a konačno rešenje je dostupno nakon što prava pređe sve objekte.

Istorija

Ovaj pristup vodi poreklo od algoritama za skeniranje (scanline algorithms) za renderovanje u kompjuterskoj grafici, a zatim se primenjuje u raznim algoritmima za projektovanje integrisanih kola, gde je geometrijski opis IC-a obrađivan u paralelnim trakama jer ceo opis nije mogao da stane u memoriju.

Primene

Primena ovog pristupa dovela je do napretka u računarskoj složenosti geometrijskih algoritama kada su Šamos i Hoi predstavili algoritme za presecanje duži u ravni 1976. godine. Posebno su opisali kako kombinacija ovog pristupa sa efikasnim strukturama podataka (samo-balansirajuća binarna stabla) omogućava detekciju da li postoje presekanja između N duži u ravni sa vremenskom složenošću O(N log N). Srodni Bentli-Otman algoritam koristi tehniku pomerajuće prave za pronalaženje svih K preseka među N duži u ravni sa vremenskom složenošću O((N + K) log N) i prostornom složenošću O(N).

Od tada, ovaj pristup se koristi za dizajniranje efikasnih algoritama za brojne probleme u računarskoj geometriji, kao što su konstrukcija Voronojevog dijagrama (Fortune-ov algoritam), Deloneova triangulacija ili Bulove operacije nad poligonima.

Generalizacije i proširenja

Topološko pomeranje je oblik „pomerajuće prave“ sa jednostavnim redosledom obrade tačaka, što izbegava potrebu za potpunim sortiranjem tačaka i omogućava da se neki algoritmi ove vrste izvedu efikasnije.

Tehnika rotirajućih kalpera za dizajniranje geometrijskih algoritama takođe se može interpretirati kao oblik „pomerajuće prave“, u projektivnom dualu ulazne ravni: oblik projektivnog dualiteta transformiše nagib prave u jednoj ravni u x-koordinatu tačke u dualnoj ravni, tako da je napredak kroz prave sortirane po nagibu u algoritmu sa rotirajućim kalperom dualan napretku kroz tačke sortirane po x-koordinatama u algoritmu sa pomerajućom pravom.

Ovaj pristup se može generalizovati na više dimenzija.