Seminarski
radovi 2011/12 godina
|
Tema |
Studenti |
Prezentacija |
Test primeri
(.rar) |
|
Marko Pavlović Sara Stojković Filip
Radulović Andrea Kolaček |
|||
|
Marina Brikić Marko Jelenković Aleksandar Pavlović Nemanja
Petrović |
|||
|
Tijana
Jakovljević Luka Trikić Nikola Divić |
|||
|
Darko
Stošič Uglješa
Pantić Đorđe
Dančetović Nikola Nestorović |
|||
|
Mirjana
Kostić Aleksandra Karadžić Safet
Isljami Stefan Isidorović |
|||
|
Ena
Šestić Slobodan Nikolić Marko Mihajlović |
|||
|
Ognjen
Kocić Sanja
Mijalković Tamara Savović Aleksandra Simić |
|||
|
Mladen
Drobnjaković Miloš
Manojlović Aleksandra Vidojević Miroslav Ostojić |
|||
|
Danilo
Vulićević Aleksandar Šuka Dušan
Radović Đorđe
Vasojević |
|
|
|
|
Nataša
Kuzmanović Tijana
Kostić Vladimir Martić |
|||
|
Stefan Đorđević Nikola Grujić Nenad
Avramović Aleksandra Mačkić |
|
|
|
|
Nikola Mihajlović Zdravko
Rakić Vladimir Dželetović Vedrana
Sofijanić |
|||
|
Uroš
Veličković Dragan
Jovanović Eva Tuba Dejan
Mirković |
|
|
|
|
Teselacija ravni trouglovima, četvorouglovima i petouglovima |
Darko
Vidaković Ivana
Ribić Katarina Milić Predrag
Ignjatović |
||
|
Uroš
Jovanović Boban
Piskulić Filip
Luković Jelena
Mirkov |
|||
|
Danijela Lazić Đorđe
Vlaisavljević Petar
Jovanović Dario Matić |
|||
|
Nikola Sojčić Petar
Stajić Mateja
Prpić |
|||
|
Vuk
Jovanović Marko Pozdnjakov Đuro
Nenadović Pavle
Perić |
|||
|
Uroš
Stegić Miloš
Novković Nikola Ristovski Željko
Jovanović |
|||
|
Marica
Bogićević Miloš
Nakalamić Marina Toromanović Tamara Milovanović |
|||
|
Bojan
Nestorović Vukašin
Jelić Strahinja Todorović |
|
||
|
Uroš
Milenković Milan Stojković Nemanja
Radosavljević Marko Stanačić |
|||
|
Vanja
Cvetković Dalibor
Stanisavljević Bogdan
Jovanović Predrag
Dimitrijević |
Opisi tema
Literatura:
1.
Lopandić strane 65-66 (http://poincare.matf.bg.ac.rs/~zlucic/LopandicGeometrija.pdf),
2.
http://alas.matf.bg.ac.rs/~vsrdjan/files/euklidska_scan.zip (ne sve)
Težina: lak-srednji
Opis seminarskog: Izometrija ravni je
određena sa tri para odgovarajućih tačaka ABC
i A’B’C’
takvih da su trouglovi ABC i A’B’C’ podudarni. Na osnovu Teoreme 3.1 ona
se moze predstaviti kao kompozicija najviše tri osne refleksije.
Zadatak je:
1.
da se za date dve trojke tačaka ABC i A’B’C’odredi
da li su trouglovi podudarni (tj. da li odredjuju izometriju);
2.
da se odrede ose tih triju (ili dve, ili jedne)
refleksija, te da se predstave slike trougla u toj kompoziciji redom;
3.
da se kaže o kojoj se izometriji
radi (osna refleksija, translacija, rotacija, klizajuća refleksija);
4.
da se naprave primeri trouglova ABC i A’B’C’ za svaku od tih izometrija.
Literatura:
1. http://cs.smith.edu/~orourke/books/compgeom.html strane 3-9, 36-41 (engleski)
Težina: srednji-lak
Opis seminarskog: Zamislimo da smo umetničku galeriju predstavili kao
poligon sa n temena. Pitanje je
koliko kamera je potrebno postaviti da bi se pokrio svaki kutak prostorije.
Kamera se može pokretati u svakom smeru i ne može da snima kroz zid. U
literaturi je opisano rešenje ovog problema korišćenjem triangulacije
poligona i 3-bojenja.
Zadatak je:
1.
Implemenirati algoritam za triangulaciju poligona (Ear removal algorithm).
2.
Implementirati algoritam za 3-bojenje.
3.
Nacrtati primere.
Literatura:
1. http://cs.smith.edu/~orourke/books/compgeom.html
strane 44-47 (engleski),
2. http://faculty.cs.tamu.edu/chen/notes/geo.pdf strane 45-53
(engleski)
Težina: srednji
Opis seminarskog: Prost poligon je monoton u odnosu na pravu l ako se njegova granica može podeliti
na dva lanca koji su monotoni u odnosu na pravu l, tj. ako svaka prava ortogonalna na l seče lanac u tačno jednoj tački. Monotona planina je monotoni
poligon čiji je jedan monotoni lanac sveden na segment (bazu).
Zbog specifičnih svojstava koja
monotoni poligoni poseduju, njihova triangulacija je
jednostavna – može se izvrišiti u linearnom vremenu.
Zadatak je:
1.
Za dati poligon ispitati da li je monoton.
2.
Implementirati algoritam za triangulaciju
monotonog poligona.
3.
Implementirati algoritam za triangulaciju
monotone planine.
4.
Nacrtati primere.
Literatura:
1.
http://en.wikipedia.org/wiki/Closest_pair_of_points_problem
2. http://www.cs.ucsb.edu/~suri/cs235/ClosestPair.pdf
Težina: lak
Opis seminarskog: Zadatak je da se u skupu tačaka nađu dve koje su
najbliže. Očigledno, primenom algoritma „grube sile“ možemo rešiti ovaj
problem. Ipak, poznat je i efikasniji algoritam iz skupa algoritama «podeli i
vladaj» (en. divide
and conquer algorithm). Potrebno je implementirati algoritam i za ravanski i za prostorni slučaj.
Zadatak je:
1.
Implemenirati trivijalni algoritam
reda O(n2).
2.
Implementirati algoritam reda O(n log(n)).
3.
Uporediti brzinu ta dva algoritma na primerima. Nacrtati
primere.
Literatura:
1.
http://faculty.cs.tamu.edu/chen/notes/geo.pdf strane 40-44
(engleski),
2. http://faculty.cs.tamu.edu/chen/notes/geo.pdf
strane 36-39 (engleski),
3.
http://poincare.matf.bg.ac.rs/~tijana/geometrija/konveksni
omotac/convex_hull.html
Težina: srednji
Opis seminarskog: Zadatak je da se u skupu tačaka nađu dve koje su
najudaljenije. Očigledno, primenom algoritma „grube sile“ možemo rešiti ovaj
problem. Ipak, poznat je i efikasniji algoritam koji ovaj problem svodi na
nalaženje antipodalnih tačaka konveksnog omotača.
Zadatak je:
1.
Implemenirati trivijalni algoritam
reda O(n2).
2.
Implementirati algoritam reda O(n log(n)). Koristiti Grahamov algoritam
za konstrukciju konveksnog omotača.
3.
Uporediti brzinu ta dva algoritma na primerima. Nacrtati
primere.
Literatura:
1. skripta (http://alas.matf.bg.ac.rs/~vsrdjan/files/geometrija7.pdf)
2. http://en.wikipedia.org/wiki/Platonic_solid
Težina: lak-srednji
Opis seminarskog: Platonova
tela (ili pravilni poliedri) su poliedri
čija je svaka strana pravilan poligon sa jednakim brojem temena i čije svako
teme sadrži jednak broj ivica. Postoji tačno pet platonovih tela (tetraedar, kocka, oktaedar, dodekaedar i ikosaedar). Ako se
svakoj pljosni Platonovog tela pridruži težište te pljosni, dobijaju se temena dualnog tela. Tako su dualni: tetraedar sam sebi, kocka i oktaedar, dodekaedar i
ikosaedar.
Zadatak je:
1. Iz datih fajlova učitati koordinate
temena i pljosni Platonovih tela
2. Za dato telo izračunati dualno telo
3. Nacrtati projekciju tela sa mogućošću rotacije oko koordinatnih osa.
Literatura:
1. http://poincare.matf.bg.ac.rs/~tijana/geometrija/seminarski/CG019028.zip
strane 19-28 (engleski),
2.
http://faculty.cs.tamu.edu/chen/notes/geo.pdf strane 31-34
(engleski)
Težina: srednji-težak
Opis seminarskog: Dato je n duži
u ravni. Potrebno je odrediti sve moguće
preseke tih duži. Naravno, postoji trivijalan algoritam-presecati svake dve
duži. Dosta bolji algoritam, reda O(n
log(n)), je opisan u literaturi i
pripada algoritmima «čišćenja ravni» (en. plane sweep algorithm). Za
realizaciju algoritma koristi se struktura drveta.
Zadatak je:
1.
Implemenirati trivijalni algoritam.
2.
Implementirati algoritam reda O(n log(n)).
3.
Uporediti brzinu ta dva algoritma na primerima. Nacrtati
primere.
Literatura:
1. http://cs.smith.edu/~orourke/books/compgeom.html strane 225-238 (engleski)
Težina: lak
Opis seminarskog: U zavisnosti od toga da li pripadaju istoj ravni ili ne,
presek duži i trougla može biti prazan, tačka, deo duži ili čitava duž.
Zadatak je:
1.
Napisati funkciju koja za zadati trougao i duž vraća
njihov presek.
2.
Napraviti test primere za sve slučajeve preseka. Nacrtati
primere.
Literatura:
1. http://cs.smith.edu/~orourke/books/compgeom.html strane 252-262 (engleski)
Težina: srednji-lak
Opis seminarskog: Presek dva konveksna poligona u ravni sa n i m
temena može biti prazan, tačka, duž, trougao, četvorougao…
Zadatak je:
3.
Implementirati algoritam linearne složenosti koji računa
presek dva konveksna poligona.
4.
Napraviti test primere za što više slučajeva preseka.
Nacrtati primere.
5.
Šta može biti presek trougla i kvadrata? Nacrtati sve
slučajeve.
Literatura:
1.
skripte
(http://demonstrations.wolfram.com/Intersecting3DTriangles/)
Težina: lak-srednji
Opis seminarskog: Dva trougla u prostoru
mogu da se seku na različite načine: da se ne seku, da im presek bude tačka,
duž, (a ako pripadaju istoj ravni i trougao, četvorougao...)
Zadatak je:
1.
Napisati funkciju koja za data
dva trougla vraća njihov presek.
2.
Napraviti test primere za sve
moguće slučajeve.
3.
Nacrtati rezultat koristeci projekciju na ravan.
Literatura:
1. http://faculty.cs.tamu.edu/chen/notes/geo.pdf strane 58-62, 85-89 (engleski)
Težina: srednji-težak
Opis seminarskog: Dato je n tačaka
u ravni. Konveksni omotač tih tačaka je najmanji konveksan skup koji te tačke
sadrži. Pokazuje se da je konveksni omotač zapravo poligon čija su temena neke
od datih tačaka.
Zadatak je:
1.
Implementirati Kirkpatrick-Seidel-ov algoritam za konstrukciju konveksnog omotača.
2.
Implementirati Mergehull algoritam za konstrukciju konveksnog omotača.
3.
Uporediti brzinu ta dva algoritma na primerima. Nacrtati
primere.
Literatura:
1.
http://faculty.cs.tamu.edu/chen/notes/geo.pdf strane 58-62
(engleski)
2.
http://poincare.matf.bg.ac.rs/~tijana/geometrija/konveksni
omotac/convex_hull.html#quickHull
Težina: srednji
Opis seminarskog: Dato je n tačaka
u ravni. Konveksni omotač tih tačaka je najmanji konveksan skup koji te tačke
sadrži. Pokazuje se da je konveksni omotač zapravo poligon čija su temena neke
od datih tačaka.
Zadatak je:
1.
Implementirati Quickhull algoritam za konstrukciju konveksnog omotača.
2.
Implementirati Mergehull algoritam za konstrukciju konveksnog omotača.
3.
Uporediti brzinu ta dva algoritma na primerima. Nacrtati
primere.
Literatura:
1.
http://poincare.matf.bg.ac.rs/~tijana/geometrija/konveksni
omotac/convex_hull.html#quickHull
Težina: srednji
Opis seminarskog: Dato je n tačaka
u ravni. Konveksni omotač tih tačaka je najmanji konveksan skup koji te tačke
sadrži. Pokazuje se da je konveksni omotač zapravo poligon čija su temena neke
od datih tačaka.
Zadatak je:
1.
Implementirati algoritam reda O(n3) sa predavanja.
2.
Implementirati Jarvis March („pakovanje poklona“ ) algoritam za konstrukciju konveksnog omotača.
3.
Implementirati Graham-ov
algoritam za konstrukciju konveksnog omotača.
4.
Uporediti brzinu ta tri algoritma na primerima. Nacrtati
primere.
Literatura:
1. http://library.thinkquest.org/16661/index2.html
2. http://demonstrations.wolfram.com/AnyQuadrilateralCanTile/
3. http://demonstrations.wolfram.com/AnyTriangleCanTile
Težina:
srednji
Opis seminarskog: Teselacija (ili popločavanje) je
razbijanje ravni podudarnim figurama (ili figurom). Postoji mnogo zanimljivih teselacija ravni (tražiti «tesselation»
na images.google.com). Najjednostavnije su teselacije
jednakostraničnim trouglovima, kvadratima i
šestouglovima. Interesantno je da je moguca teselacija ravni i proizvoljnim trouglom i četvorouglom,
što je cilj ovog seminarskog. Eventualni dodatni cilj
je teselacija nekim petouglovima (nije moguća teselacija proizvoljnim petouglom).
Zadatak je:
1.
Implementirati algoritme za trougao i četvorougao.
2.
Nacrtati teselacije
3.
Uraditi teselaciju petouglom.
Nacrtati primere.
Literatura:
1. http://poincare.matf.bg.ac.rs/~tijana/geometrija/seminarski/GTCG847852.zip
strane 847-852 (engleski),
Težina:
srednji
Opis seminarskog: Poznato je da je svaka direktna izometrija
prostora (tj. ona koja čuva orjentaciju), rotacija oko neke prave za neki ugao.
Ojlerova teorema kaže da se svaka direktna izometrija
prostora može predstaviti kao kompozicija tri rotacije oko koordinatnih osa i
to za uglove koje je moguće odrediti. Ovo ima velike primene u kompjuterskoj
grafici, robotici....
Zadatak je:
1.
Za datu matricu proveriti da li je matrica izometrije i da li je direktna
2.
Ako jeste, treba joj naći Ojlerove
dekompozicije
3.
Ilustrovati prethodno na primeru kocke: primeniti na
kocku proizvoljnu izometriju (nacrtati kocku, osu
rotacije i zarotiranu kocku), a zatim istu izometriju realizovati trima rotacijama (nacrtati
odgovarajuće međupoložaje kocke).
Literatura:
1. http://faculty.cs.tamu.edu/chen/notes/geo.pdf strane 186-193 (engleski)
Težina: srednji
Opis seminarskog: Neka je S
skup n tačaka u ravni.
Potrebno je naći trougao najmanje površine čija su temena tačke skupa S. Za realizaciju algoritma koristi se
struktura drveta.
Zadatak je:
1.
Implemenirati trivijalni algoritam
složenosti O(n3).
2.
Implementirati algoritam
složenosti O(n2 log(n) ).
3.
Uporediti brzinu ta dva algoritma na primerima. Nacrtati
primere.
Literatura:
1. skripte (http://alas.matf.bg.ac.rs/~vsrdjan/files/geometrija5.pdf)
Težina: lak
Opis seminarskog: Elipsa, hiperbola i parabola
imaju takozvane optičke osobine. Kod elipse i hiperbole svetlosni zrak koji
izlazi iz jedne žiže elipse prolazi kroz drugu žižu (eliptički
bilijar).
Kod parabole svetlosni
zrak koji izlazi iz žiže se odbija paralelno osi parabole.
Zadatak je:
1.
Za dati pravc a odrediti jednačinu zraka i odbijenog
zraka (za slučaj svake od krivih).
2.
Za dati prirodan broj n
odrediti kako će izgledati elipsa sa svetlosnim zrakom nakon n odbijanja.
3.
Nacrtati slike koje ilustruju navedene optičke osobine
(za slučaj svake od krivih).
Literatura:
1. skripte (http://alas.matf.bg.ac.rs/~vsrdjan/files/geometrija5.pdf)
Težina: težak-srednji
Opis seminarskog: Poznato je da se svaka kriva drugog reda izometrijskim transformacijama (rotacija, translacija i
refleksija) može svesti na kanonski oblik.
Zadatak je:
1.
Odrediti formule rotacije, translacije i
eventualno refleksije kojima se kriva
svodi na kanonski oblik
2.
Odrediti kanonski oblik krive i koja je kriva u pitanju
3. Nacrtati datu krivu,
originalni koordinatni sistem kao i koordinatne sisteme dobijene nakon
rotacije, translacije i refleksije.
Literatura:
1.
http://poincare.matf.bg.ac.rs/~tijana/geometrija/bezier/bezier-promena_stepena.html
Težina: srednji
Zadatak je:
1.
Napisati funkciju int PodelaKrive(Tacka* ktacke,int
n,Tacka* niz1,Tacka* niz2) koja deli datu Bézier-ovu krivu n-tog reda oderđenu svojim kontrolnim tačkama na dva jednaka
dela. Funkcija treba da upiše
u nizove niz1 i niz2 nove kontrolne tačke Bézier-ovih krivih. Funkcija vraća 0 ako je došlo do greške, a 1 inače.
2.
Napisati funkciju int PovecajStepen(Tacka* ktacke,int
n,int m,Tacka* niz) koja povećava
stepen Bézier-ove krive za m. Funkcija treba da upise u niz
nove kontrolne tačke.
3.
Napisati program koji datu Bézier-ovu krivu krivu n-tog stepena oderđenu svojim kontrolnim tačkama deli na
dva jednaka dela, a zatim povećava
stepen prvog dela krive za
m, a drugog dela za k.
4.
Nacrtati početnu krivu
i njen konveksni
omotač, a zatim i konveksni omotač
nove krive.
Literatura:
1.
http://mathworld.wolfram.com/Inversion.html
2.
Lopandic, od strane 201 (http://poincare.matf.bg.ac.rs/~zlucic/LopandicGeometrija.pdf)
Težina:
lak-srednji
Opis seminarskog: Inverzija u odnosu na krug je preslikavanje ravni koje
dati krug preslikava na sebe, unutrašnjost kruga slika u njegovu spoljašnjost i
obrnuto. Inverzija slika prave i krugove
te ravni opet u prave i krugove. Naime, ako objekat koji preslikavamo sadrži
centar inverzije (centar kruga), tada se on slika u pravu, u suprotnom se slika
u krug.
Zadatak je:
1.
Napisati funkciju koja realizuje inverziju u odnosu na
krug sa centrom (0,0) i poluprečnikom
r.
2.
Napisati funkciju koja za datu pravu ili krug određuje
njenu sliku u inverziji.
3.
Napisati funkciju koja crta kružni luk (kome su dati centar
i krajnje tačke).
4.
Za dati trougao odrediti sliku u inverziji (to je trougao
koji se sastoji od kružnih lukova)
5.
Napraviti test primere i nacrtati
Literatura:
1.
http://poincare.matf.bg.ac.rs/~tijana/geometrija/seminarski/tree_drawing.pdf
Težina: lak-srednji
Opis seminarskog:
Drvo je graf koji nema
ciklusa i kada se nacrta upravo tako i izgleda. Struktura drveta dobro je
poznata: sastoji se od čvorova i listova koji su povezani granama. Problem crtanja grafova, specijalno drveta, u
ravni je relativno jednostavan ako nam nije vazno kako crtež izgleda. Ipak,
minimalan je zahtev da se grane grafa ne seku, da bi
taj crtež bio iole upotrebljiv.
Zadatak je:
1. Napisati
funkciju koja dati graf crta u ravni (koristiti
Algoritam 1 iz literature).
2. Napraviti
test primere.
Literatura:
1. Skripte, predavanja
2. http://demonstrations.wolfram.com/PoolShot/
3. http://demonstrations.wolfram.com/PoolShot3D/
Težina: lak-srednji
Opis seminarskog:
U 2D slucaju
pretpostavljamo da nam je dat pravougaonik ivica a i b, čije je levo donje
teme tačka (0,0). Sa tačke (x0,y0) koja
pripada pravougaoniku u pravcu p ispaljujemo kuglu koja se odbija od jedne ivice, pa od
druge ivice... kao na bilijarskom stolu. U 3D slučaju slično, samo je umesto
pravougaonika dat kvadar.
Zadatak je:
1. Napisati
funkciju koja za datu tačku, pravac i broj n,
crta putanju kugle nakon n odbijanja
(2D).
2. Napisati
funkciju koja za datu tačku, pravac i broj n,
crta putanju kugle nakon n odbijanja
(3D).
3. Napraviti
test primere i crteže. U 3D slucaju zarotirati objekte, pa ih projektovati.
Literatura:
1. http://en.wikipedia.org/wiki/Fractal
2.
http://en.wikipedia.org/wiki/Hilbert_curve#Computer_implementations_of_the_drawing_algoritms
3.
http://www.cut-the-knot.org/do_you_know/hilbert.shtml
4.
http://www.compuphase.com/hilbert.htm
5.
http://www.cut-the-knot.org/Curriculum/Calculus/NoLimit.shtml
6.
http://mathworld.wolfram.com/KochSnowflake.html
Težina: lak-srednji
Opis seminarskog: Fraktali su „sebi slični“ likovi, odnosno
likovi kojima kad uvećamo deo dobijamo oblik nalik polaznom. Fraktalne
strukture su veoma česte u prirodi, te su važne u mnogim granama nauke i
umetnosti.
Hilbertova i Peanova kriva su poznate kao
neprekidne krive koje ispunjavaju ceo kvadrat, tako da „na neki način imaju
dimenziju i jedan (jer su krive) i dva (jer popunjavaju deo ravni)“.
Zadatak je:
1.
Napraviti popularan prikaz (predavanje) fraktala (fractals) i krivih koje popunjavaju ravan (plane filling curves), sa slikama. Koristiti materijal sa Interneta.
2.
Napraviti funciju koja crta Hilbertovu, Peanovu i Kohovu
krivu (ili bar dve od njih) zadatog reda.