Geometrijski algoritmi igraju važnu ulogu u mnogim oblastima, poput računarske grafike, projektovanja pomoću računara, projektovanju integrisanih kola visoke rezolucije (VLSI), robotike i baza podataka. U računarski generisanoj slici može biti na hiljade ili čak na milione tačaka, linija, trouglova, kvadrata ili krugova; slično, projektovanje računarskog čipa može da zahteva rad sa milionima elemenata koji se predstavljaju geometrijskim figurama. Sve ove primene zahtevaju obradu geometrijskih objekata. Pošto veličina ulaza za ove probleme može biti vrlo velika, veoma je značajno razviti što efikasnije algoritme za njihovo rešavanje.
Česta neugodna karakteristika geometrijskih problema je postojanje mnogih specijalnih slučajeva. Na primer, dve prave u ravni se seku u jednoj tački, sem ako su paralelne ili se poklapaju. Pri rešavanju problema sa dve prave, moraju se predvideti sva tri moguća slučaja. Složenije figure prouzrokuju pojavu mnogo većeg broja specijalnih slučajeva o kojima treba voditi računa. Obično se većina tih specijalnih slučajeva direktno rešava, ali potreba da se oni uzmu u obzir čini ponekad konstrukciju algoritma vrlo iscrpljujućom. U nastavku teksta su ignorisani neki detalji koji nisu od suštinskog značaja za razumevanje osnovnih ideja algoritama, a čitaocu savetujemo da razmotri rešavanje svih specijalnih slučajeva na koji se pri konstrukciji algoritma naiđe, da bi se dobili algoritmi koji su u potpunosti ispravni.
U prvom poglavlju ćemo obnoviti osnovne pojmove analitičke geometrije ravni: tačke, vektore, koordinate, operacije nad vektorima, sa posebnim naglaskom na primene skalarnog i vektorskog proizvoda, računanje površine trougla i orijentacije trojke tačaka.
Prikazaćemo algoritam određivanja svih presečnih tačaka datog skupa horizontalnih i vertikalnih duži.
Poseban naglasak je stavljen na mnogouglove. Najpre će biti razmotren algoritam za konstrukciju prostog mnogougla. Nakon toga, biće prikazan algoritam za ispitivanje pripadnosti tačke prostom mnogouglu i biće opisan efikasniji algoritam za ispitivanje pripadnosti tačke konveksnom mnogouglu. Na kraju će biti diskutovani razni algoritmi za konstrukciju konveksnog omotača: induktivni algoritam zasnovan na dodavanju jedne po jedne tačke, algoritam uvijanja poklona, Grejemov algoritam i brzi algoritam za određivanje konveksnog omotača (engl. QuickHull).
Zadaci: