mislo

Fakulteta za elektrotehniko, računalništvo in informatiko · Univerza v Mariboru

Uvod v računalniško geometrijo

Za Uvod v računalniško geometrijo še ni zapiskov.

Imaš svoje zapiske? Objavi jih: ceno določiš ti, z naročnino ti ostane cela, DDV se doda kupcu.

Objavi zapiske

Čakaš na zapiske? Prijavi se in povej. Ko jih kdo objavi, dobiš sporočilo.

Želim zapiske

Kaj lahko narediš že danes

Naloži svoje gradivo za Uvod v računalniško geometrijo: Mai ga prebere in ti iz njega naredi kartice, kviz in razlago, ko ti kaj ni jasno. Če zapiske kasneje objaviš, jih prodajaš tukaj.

Naloži svoje gradivo

Učni načrt

Podatki so iz učnega načrta, ki ga objavlja Fakulteta za elektrotehniko, računalništvo in informatiko. Prebrano 6. 9. 2026. Poglej izvirnik

6 kreditnih točk

Obveznosti v urah

  • Predavanja30 ur
  • Vaje45 ur
  • Samostojno delo105 ur

Vsebina

  1. Uvod: pomen in aplikacije algoritmov računalniške geometrije.
  2. Pasti algoritmov z aritmetiko s plavajočo vejico.
  3. Pogoji od dobrooblikovanih površjih.
  4. Predstavitvene metode (dvoumne in nedvoumne).
  5. Eulerjevi operatorji.
  6. Osnovne podatkovne strukture za iskanje v ravnini: enakomerna delitev ravnine, štiriško drevo, drevo BSP.
  7. Izbočena (konveksna) lupina: definicija in uporaba, naivna metoda, Grahamovo preiskovanje, Jarvishev obhod, inkrementalna metoda, metoda s preiskovalno premico, hitra konveksna lupine, aproksimativna rešitev.
  8. Iskanje najbližje točke: delitev problemov najbližje točke in aplikacije, reševanje inkrementalnega problema najbližje točke z enakomerno delitvijo ravnine.
  9. Triangulacija: definicija in lastnosti, triangulacija MWT, Hammiltonova triangulacija, Delaunayeva triangulacija.
  10. Algoritmi za konstrukcijo Delaunayeve triangulacije: inkrementalne metode, konstrukcijska metoda, pristop deli in vladaj, metoda s prebirno premico, metoda s preslikavo na paraboloid, Delaunayeva lomljenka.
  11. Algoritmi konstrukcije Voronoievih diagramov: definicija in lastnosti, aplikacije, posplošeni Voronoievi diagrami, naivna metoda, metoda deli in vladaj, inkremetalna metoda, metoda s prebirno premico.
  12. Definicija in klasifikacija mnogokotnikov.
  13. Vsebnostni testi: brez priprave podatkov (s poltrakom, z vsoto kotov, s kodiranim koordinatnim sistemom, test enakega predznaka) in s pripravo podatkov (delitev v trakove, algoritem s klini, algoritem CBCA).
  14. Triangulacija mnogokotnika: brez kriterija, Delaunayeva triangulacija, triangulacija s Steinerjevimi točkami.
  15. Omejena Delaunayeva triangulacija.
  16. Trapezna delitev mnogokotnika: Seidlov algoritem, algoritem z dvema preiskovalnima premicama, algoritem z odprtimi trapezi.
  17. Boolove operacije nad mnogokotniki.

Ocenjevanje

Laboratorijsko delo 50 %, Pisni izpit 50 %

Pogoji za vključitev

Pogojev ni.

Literatura

  • Berg, M. de, Cheong, O., Kreveld, M. van, & Overmars, M. H. (2010). Computational geometry: algorithms and applications (3rd ed., p. XII, 386). Springer. http://link.springer.com/book/10.1007/978-3-540-77974-2
  • Preparata, F. P., & Shamos, M. I. (1990). Computational geometry: an introduction (Corrected and expanded 2nd print., p. XIV, 398). Springer.
  • O’Rourke, J. (1998). Computational geometry in C (2nd ed., p. XIII, 376). Cambridge University Press.
  • Žalik, B. (2006). Algoritmi računalniške geometrije (p. XXII, 288). Fakulteta za elektrotehniko, računalništvo in informatiko.

Kako deluje

  1. Zapiske kupiš enkrat in ostanejo tvoji.
  2. V aplikaciji iz njih dobiš kartice, kvize in Mai, ki pozna gradivo.
  3. Ceno določi avtor. Prodajalec je Mislo AI, račun dobiš od nas.