Seminarski
radovi 2010/11 godina
|
Tema |
Studenti |
Prezentacija |
Test primeri
(.rar) |
|
075/09 Marko Makarić 059/09 Jovana Bogdanović 226/09 Stajka Đenić 221/09 Tamara Zimonjić |
|
||
|
044/09 Stefan Cerovina 316/10 Marko Milošević 109/09 Đorđe Rakonjac 149/09 Perica Trajkov |
|||
|
008/09 Gligorov Vladimir 208/09 Stefan Janjić 137/09 Luka Lazić 066/09 Žana Mrdalj |
|||
|
053/09 Petković Stefan 229/09 Sarić Srđan 282/09 Grujičić Ivan 088/09 Sanja Petrović |
|||
|
243/07 Miloš Bjeloš 153/07 Vladan Divnić 158/07 Miloš Kuveljić |
|||
|
078/09 Milica Mijailović 224/08 Lazar Mijailović 173/09 Dragan Tošić 230/09 Biljana Janković |
|||
|
030/09 Davor Grubač 075/09 Marija Ševković 105/09 Milan Jakovac 207/08 Đorđe Vlaisavljević |
|||
|
069/08 Nemanja Sikimić 121/07 Nenad Matić 163/08 Uroš Veličković 137/07 Nikola Cvetković |
|||
|
153/09 Milica Ostojić 154/09 Nikola Veselinović 152/09 Nikola Živković 247/09 Marko Milosavljević |
|
||
|
087/09 Nemanja Veljković 203/08 Nikola Nikolić 190/09 Igor Simović 219/09 Đorđe Simić |
|||
|
097/09 Uroš Mihailović 052/09 Branko Popović 002/09 Dragoslav Stojčić 242/09 Sava Gavran |
|||
|
004/09 Petar Atanasovski 182/09 Andrija Miljković 012/09 Stevan Prodanović 045/09 Uroš Delić |
|||
|
145/09 Nikola Nikolić 151/09 Aleksandar Jovanović 194/09 Sava Ilić 216/09 Nikola Maravić |
|||
|
036/09 Aleksandar Nedeljković 136/09 Tomica Brković 269/09 Milan Kosanović |
|||
|
175/07 Rastko Radinović 319/10 Aleksandar Popović 298/10 Miloš Milekić 373/06 Miloš Mitrović |
|
||
|
146/09 Nemanja Tošić 055/09 Saša Jekić 091/09 Dušan Mančić 150/09 Nebojša Ložnjaković |
|||
|
157/09 Nemanja Janjić 160/09 Miloš Milaković 057/09 Katarina Batinić |
|
||
|
072/09 Dejan Knežević 253/09 Dragan Jovanović 203/09 Nemanja Jevtić 035/07 Andrea Kolaček |
|||
|
017/09 Nikola Stanković 008/09 Nikola Stanojević 005/09 Srđan Terzić |
|||
|
108/09 Dragan Đurđević 104/09 Petar Blažić 238/09 Matei Stanču |
|||
|
041/10 Nebojša Muljava 148/09 Stana Obrenić 241/09 Jelena Mladenović 127/08 Filip Todorović |
Opisi tema
Literatura:
1.
http://poincare.matf.bg.ac.rs/~tijana/geometrija/seminarski/CTCG729738.zip strane 729-738
(engleski),
2.
http://www.cse.unsw.edu.au/~lambert/java/3d/hull.html
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.
Za datih n
tačaka treba odrediti konveksni omotač algoritmom inkrementalnog tipa,
složenosti reda O(n2),
koji je opisan u literaturi
2.
Implementirati algoritam reda O(n3) sa predavanja
3.
Uporediti brzinu algoritama
Literatura:
1.
http://poincare.matf.bg.ac.rs/~tijana/geometrija/seminarski/CG002010.zip strane 2-10 (engleski),
2.
http://www.cse.unsw.edu.au/~lambert/java/3d/hull.html
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.
Za datih n
tačaka treba odrediti konveksni omotač algoritmom inkrementalnog tipa,
složenosti reda O(n log(n)), koji je
opisan u literaturi.
2.
Implementirati algoritam reda O(n3) sa predavanja
3.
Uporediti brzinu algoritama
Literatura:
1.
http://w3.jouy.inra.fr/unites/miaj/public/vigneron/cs4235/l10cs4235.pdf
Težina: srednji
Opis seminarskog: Delunijeva triangulacija poligona (tačnije
skupa tačaka ravni) je takva triangulacija da nijedno teme ne pripada nijednom
trouglu te triangulacije. Moze se pokazati da se takvom triangulacijom
maksimizira minimalni ugao svih trouglova. Tako se izbegavaju uski (tj.
degenerisani) trouglovi.
Zadatak je:
1.
Implementirati neki algoritam
za triangulaciju skupa od n tačaka
2.
Napraviti i nacrtati test
primere
Literatura:
1. http://poincare.matf.bg.ac.rs/~tijana/geometrija/seminarski/CG019028.zip
strane 19-28 (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.
skripte, predavanja
Težina: lak
Opis
seminarskog: Presek prave i kruga se lako određuje. Za presek dva kruga potrebno
odrediti njihovu radikalnu osu.
Zadatak je:
1.
Napisati funkciju za presek prave i kruga
2.
Napisati funkciju za presek dva kruga
3.
Napisati program koji učitava dva objekta iz fajla,
odredjuje im presek, a zatim crta rezultat.
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.
Eventualno uraditi teselaciju petouglom.
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. 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: 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.
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.
skripte (http://demonstrations.wolfram.com/TheIntersectionOfTwoTriangles/)
Težina: lak
Opis seminarskog: Dva trougla u ravni mogu da se seku na
različite načine: da se ne seku, da im presek bude tačka, duž, 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
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://www.tsplines.com/technology/edu/CurveIntersection.pdf (engleski)
2.
http://poincare.matf.bg.ac.rs/~tijana/geometrija/bezier/bezier-podela.html
Težina: srednji
Zadatak je:
1.
Napisati
funkciju int PodelaKrive(Tacka* tniz,int
n,float u,Tacka* niz1,Tacka* niz2) koja deli datu
Bézier-ovu krivu n-tog reda praveći rez u tački B(u) za dato u.
Argumenti funkcije su niz kontrolnih tačaka
tniz dužine n+1>2 i realna vrednost 0<u<1. 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 program
koji traži sve tačke preseka dve Bézier-ove krive koristeći standardni
algoritam Bézier-ove podele.
3.
Nacrtati obe
Bézier-ove krive, njihove konveksne omotače i tačke preseka.
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://poincare.matf.bg.ac.rs/~tijana/geometrija/bezier/bezier-pomeranje_kontrolnih_tacaka.html
Težina: lak
Zadatak je:
Napisati
program koji ilustruje promenu oblika Bézier-ove krive pri promeni položaja
kontrolnih tačaka. Korisnik zadaje krivu nizom kontrolnih tačaka, a zatim bira
kontrolnu tačku i translira je za neki vektor. Program treba da nacrta početnu
Bézier-ovu krivu i njen konveksni omotač, a zatim i svaku novu krivu dobijenu
translacijom neke kontrolne tačke.
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.
Literatura:
1.
predavanja,
2.
skripta (http://alas.matf.bg.ac.rs/~vsrdjan/files/geometrija2.pdf)
Težina: lak
Opis
seminarskog: Afino preslikavanje ravni je određeno sa tri para odgovarajućih
tačaka ABC i A’B’C’u proizvoljnom položaju. Afino preslikavanje preslikava
krugove u elipse, paralelne prave u paralelne prave (zato, recimo, preslikava
kvadrat u paralelogram). Afino preslikavanje čuva razmeru (pa recimo slika
središte duži u središte duži, i težište trougla u težište trougla), ali ne
čuva dužine, uglove (pa samim time i pojam ortocentra, središta upisanog i
opisanog kruga).
Zadatak je
1.
Za dva data trougla ABC i A’B’C’odrediti jednačine afinog
preslikavanja koje slika jedan u drugi
2.
Odrediti (i nacrtati) opisani i upisani krug trougla ABC
i slike tih krugova.
3.
Za dati paralelogram A’B’C’D’ odrediti elipsu koja je u
njega upisana, a koja dodiruje strane paralelograma u njihovom središtu
(uputstvo: preslikati paralelogram na pogodan kvadrat)
Literatura:
1.
http://poincare.matf.bg.ac.rs/~tijana/geometrija/seminarski/GTCG816822.zip
strane 816-822 (engleski)
Težina:
lak-srednji
Opis
seminarskog: Neka je dat poligon u ravni (ne obavezno konveksan). Ako je poligon
trougao tada se njegova površina računa pomoću vektorskog proizvoda.
Interesantno je da se za proizvoljan poligon u ravni z=0 ova formula lako uopštava. Ako poligon ne pripada ravni z=0, situacija je komplikovanija, ali ne
mnogo.
Zadatak je:
1.
Implementirati funkciju za površinu proizvoljnog poligona
u ravni z=0.
2.
Implementirati funkciju za površinu poligona ako on
pripada proizvoljnoj ravni – koristeći normalu te ravni.
3.
Implementirati funkciju za površinu poligona ako on
pripada proizvoljnoj ravni – koristeći koordinatni sistem relativan datoj
ravni.
4.
Uporediti poslednja dva rezultata i nacrtati slike