Problemi i zadaci

Svaki zadatak obilježen  s (*) je preuzet, pa možete birati od preostalih zadataka. Četiri riješena zadatka ekvivalent su usmenom ispitu, i bit će odgovarajuće ocjenjena; konačna ocjena može se popraviti izlaskom na usmeni ispit po dogovoru. Za izlazak na usmeni ispit potrebno je riješiti minimalno 2 zadatka. Zadatke rezervirate mailom po principu "tko se prvi javi", s tim da ću paziti na podjednaku zastupljenost raznih poglavlja koje pokriva kolegij.

1. Napišite program za crtanje implicitno zadane funkcije (u programskom jeziku tipa C, Delphi,  F90)  (*)
2. Napišite interaktivni program zasnovan na  konstruktivnom algoritmu za crtanje složene konične krivulje (*)
3. Napišite program za nodalnu interpolaciju Bezierovom krivuljom n-tog stupnja. Ako je krivulja zadana u eksplicitnoj formulaciji, nacrtajte funkciju, kontrolni poligon i Lagrangeov interpolacijski polinom. Ulazni podatak je stupanj n, a test funkcije odabrati po volji. (*)
4. Za t->f(t)  (funkcija u  eksplicitnoj formulaciji), t ε [0,1],  napišite program za računanje i crtanje f(t), kubične Bezierove aproksimacije za f ako su zadani f(i/3) i=0,...3n, te kubičnog interpolacijskog splajna za f(i/n), i=0,...n. Testirajte na primjeru funkcije Runge: t->1/(1+t²). (*)
5. Napišite interaktivni program zasnovan na  konstruktivnom algoritmu za dizanje stupnja Bezierove krivulje. (*)
6. Napišite program za crtanje B-splajn krivulje (u programskom jeziku tipa C, Delphi,  F90) . Zadani su stupanj i vrhovi kontrolnog poligona, koje treba moći mijenjati interaktvno. Pretpostavlja se da je vektor čvorova uniforman, s čvorovima maksimalnog multipliciteta na oba kraja vektora čvorova, ili da korisnik učitava vektor čvorova iz datoteke. Broj točaka kontrolnog poligona i duljina vektora čvorova pri tom moraju biti usklađeni. (*)
7. Za regularnu krivulju α(t) evoluta je definirana kao α^*(t)=α(t)+(1/κ(t)) N(t) gdje je N vektor jedinične normale. Koje je geometrijsko značenje α^*? Za točke u ravnini, neka je A(x,y) =  (-y,x). Pokažite da je za planarnu krivulju α^*=α+(α',α')/(α'',A(α')) A(α'). Ako je α(t) = (a cos(t/c), a sin(t/c), bt/c), pri čemu je c²=a²+b², koja je evoluta of α? Koja je evoluta njezine evolute? (*)
8. Napišite program koji ilustrira uniformno profinjavanje paraboličke B-splajn krivulje (u programskom jeziku po izboru). Dokažite pripadne rezultate za ubacivanje čvorova.(*)
9. Napišite program koji ilustrira uniformno profinjavanje kubične B-splajn krivulje (u programskom jeziku po izboru). Dokažite pripadne rezultate za ubacivanje čvorova.(*)
10. Napišite program koji ilustrira dodavanje novog čvora Boehm-ovim algoritmom u B-splajn krivulju zadanog stupnja. Mora se dozvoliti ponovno dodavanje novog čvora u profinjenu krivulju, s tim da se isti čvor može ponoviti onoliko puta koliki je stupanj B-splajn krivulje.(*)
11. Napišite heuristički algoritam i pripadni program u programskom  jeziku po izboru koji glatko spaja dvije plivajuće  B-splajn krivulje. Ulazni parametri su kontrolni poligoni za obje krivulje, i pripadni vektori čvorova.(*)
12. Napišite program za kompletnu kubičnu interpolaciju, tj. neka je n=s+2, tražimo spl(u) := ∑₀ⁿ P_iB_i³ tako da vrijedi P_j=spl(u_j), j=0,..s, i P'_j=spl'(u_j) za j=0 i j=s. Za testiranje odaberete P_j,  P'_j uzorkovanjem neke poznate krivulje, a možete pretpostaviti da su podaci zadani u ravnini. Možete koristiti bilo koji programski jezik, uz obavezno korištenje vrpčaste strukture matrice sustava. Testirajte program s uniformnom parametrizacijom i prametrizacijom duljinom krivuljnog luka.(*)
13. Napišite program za nodalnu interpolaciju otvorenom kubičnom  B-splajn krivuljom. Podaci mogu biti iz R³, za potrebe testiranja uzorkovani spiralom ili nekom drugom po volji odabranom krivuljom. Pretpostavljamo da je vektor čvorova takav, da su svi unutranji čvorovi multipliciteta jedan. Nacrtajte krivulju, interpolant i grešku.(*)
14. Napišite program koji ilustrira kako za zadani poligon promjena vektora čvorova utiče na oblik otvorene B-splajn krivulje. Učitava se stupanj krivulje i kontrolni poligon (može se unositi i grafičkim ulazom), a vektor čvorova bi trebalo interaktivno mijenjati.(*)
15. Proučiti dizanje stupnja B-splajn krivulje, pripadni algoritam,  ilustrirati upotrebu u free-form dizajnu. Zadatak zahtijeva izlaganje na seminaru za num. matematiku i računarstvo ili tokom kolegija. Pripadnu literaturu pogledati na webu kolegija.(*)
16. Napišite program za računanje skalarnih produkata B-splajnova u programskom jeziku F90/F95 ili C, po nekoj od metoda koje su predložene. Pripadnu literaturu pogledati na webu kolegija. Komparacija raznih metoda uz izlaganje na seminaru vrednovati će se kao dva riješena zadatka.(*)
17. Napišite program za direktnu manipulaciju B-splajn krivuljom γ, tj. nađite novu B-splajn krivulju β takvu da je za neku poznatu vrijednost parametra s i točku Q ispunjeno β (s)=Q i da je u smislu diskretne L₂ norme  β(s) najbliže krivulji γ(s).(*)
18. Izvedite algoritam za uniformno profinjenje kubične B-splajn krivulje iz općeg Oslo algoritma. (*)
19. Proučite brzu varijantu Oslo algoritma, tj modifikaciju Oslo algoritma  koju su izveli Lyche i  Mørken, i napišite program (C, C++ ili F90) koji ilustrira algoritam grafički. Koristite literaturu na webu kolegija. Vrijedi kao dva riješena zadatka uz izlaganje na seminaru za num. matematiku i računarstvo. (*)
20. Napišite algoritam i program SplineCurveSplit s grafičkim izlazom, koji otvorenu B-splajn  krivulju  γ stupnja κ definiranu kontrolnim poligonom {P₀,...P_n} podijeli na dvije otvorene krivulje istog stupnja, u sredini svoje parametarske domene. (*)
21. Napišite algoritam i program BezierCurveSplit s grafičkim izlazom, koji za dani kontrolni poligon P={P₀,...P_n} Bezierove krivulje θ_n[P;a,b] dijeli krivulju u točki c, a<c<b i nađite kontrolne poligone Q={Q₀,...Q_n}, R={R₀,...R_n} tako da je θ_n[P;a,b]=θ_n[Q;a,b]= θ_n[R;a,b]. (*)
22. Totalno pozitivni linearni sustavi, metode eliminacije i primjena na interpolaciju B-spline krivulja , v. literaturu na webu. Uz izlaganje na seminaru za num. matematiku i računarstvo vrednovati će se kao dva riješena zadatka. (*)
23. Izvod Oslo i deCasteljau algoritma preko principa cvjetanja  (blossoming), uz izlaganje na kolegiju ili seminaru od cca 45 min.  ili prilog u pisanoj formi za web kolegija, vrednovati će se kao dva riješena zadatka..(*).
24. Napišite program koji grafički ilustrira deRahm - Chaikinov algoritam subdivizije.(*)
25. Konstrukcija hermitskih Coons-ovih jednostavnih ploha pomoću Boole-ovih suma operatora (*)
26. Koristeći paket za manipulaciju napetim eksponencijalnim B-splajn funkcijama klase C² (vidi http://www.math.hr/~tinab) napišite program koji za dane vrhove kontrolnog poligona i parametara napetosti p_i prikazuje napetu otvorenu B-splajn krivulju, i proučite utjecaj parametara napetosti  na oblik krivulje i bliskosti s kontrolnim poligonom. Kolekcija potprograma za napete B-splajnove napisana je u programskom jeziku F90, pa se preporuča napisati i glavni program u F90, ali je dozvoljeno korištenje nekog drugog (mixed language programming). (*)
27. Odaberite krivulju u R³ kojoj možete analitički izračunati zakrivljenost i torziju (npr. neku s predavanja), i  izračunajte potpuni kubični interpolant uz pretpostavku da su pozicija i tangencijalni vektor krivulje poznati. Izračunajte numerički torziju i zakrivljenost interpolanta, i  nacrtajte greške. Pretpostavlja se uniformna parametrizacija.(*)
28. Linearne kombinacije funkcija {1,x, sin(x), cos(x)}, tzv. cikloidne funkcije,  egzaktno reproduciraju kružnice i spirale. Pokažite da je na intervalim duljine manje od π moguće riješiti problem Lagrangeove interpolacije 4 točke. Konstruirajte analogon Berstein-Bezierove baze i odredite tangencijalne vektore cikloidne Bezierove krivulje.(*)
29. Zadajte zatvorenu kubičnu B-splajn krivulju u R² kontrolnim poligonom i vektorom čvorova. Pertubirajte kontrolne točke slučajnom perturbacijom pomoću nekog generatora slučajnih brojeva, a amplituda perturbacije neka bude jedan od ulaznih  podataka. Interpolacijom odredite novu B-splajn krivulju koja je određena perturbiranim podacima i nacrtajte nove i stare kontrolne točke i krivulje.(*)
30. Metodom najmanjih kvadrata odredite kontrolni poligon kubične B-splajn krivulje koja koja se dobije uzorkovanjem funkcije x -> sin(x) na [0, 4π]. Pretpostavlja se da broj točaka u uzorku znatno veći od broja točka kontrolnog poligona (experimentirati). Ponovite test na jediničnoj kružnici, primjenjujući metodu najmanjih kvadrata na svaku komponentu (x(t), y(t)) posebno. Rezultate treba prikazati grafički, ali nije potrebno interaktivno grafičko programiranje. Zadatak zahtijeva nešto znanja numeričke analize, i vrijedi kao dva rješena zadatka. U realizaciji metode najmanjih kvadrata možete upotrijebiti QR ili SVD tehniku po izboru, v. skriptu iz numeričke analize na webu i literaturu na webu kolegija. (*)
31. Koristeći Floater-ov članak ilustrirajte utjecaj CLP, centripetalne i uniformne parametrizacije na oblik kubične splajn krivulje. Uz izlaganje na seminaru za numeričku analizu s opisom pripadne teorije, zadatak će se vrednovati kao dva riješena zadatka. Software za vizualizaciju možete odabrati po volji (C, F90, Matlab, Mathematica..) (*)
32. Konstruirajte Bernstein-Bezier-ovu bazu za linearne kombinacije funkcija {1,x, sh(px), ch(px)}, gdje je p parametar veći od nule. Promotrite slučajeve kada p teži 0 i ∞. Ilustrirajte utjecaj parametra p na oblik pripadne splajn krivulje, i dokažite da za p->∞ krivulja konvergira prema svojem kontrolnom poligonu. Odredite tangencijalne vektore pripadne krivulje na rubovima,  nacrtajte hodograf i promotrite regularnost.
33. Napišite program u jeziku po vlastitom izboru, koji evaluira splajn funkcije reda 6 (kvintik splajn), koristeći algoritam u prilogu. Numerički testirajte redove konvergencije koji su navedeni u Teoremu 3.1 u pripadnom članku.