Toepassingen van Meetkunde in de Informatica: verschil tussen versies
| Regel 29: | Regel 29: | ||
==theorie== | ==theorie== | ||
===Bezier curven=== | ===Bezier curven=== | ||
Bespreek C? continuiteit. | Bespreek C? continuiteit. | ||
---- | ---- | ||
hoe bekomt men C? continuiteit bij samengestelde bezier curven | hoe bekomt men C? continuiteit bij samengestelde bezier curven | ||
---- | ---- | ||
geef het algoritme van de Casteljau | geef het algoritme van de Casteljau | ||
---- | ---- | ||
| Regel 49: | Regel 49: | ||
bespreek constructie van samengestelde b?ziercurven + voor/nadelen | bespreek constructie van samengestelde b?ziercurven + voor/nadelen | ||
---- | ---- | ||
tensor-product | tensor-product Bezier-veeltermen hoe? | ||
Afgeleide Dxy(x0,y0) in hoekpunten parameteropp. afleiden + grafisch weergeven. | Afgeleide Dxy(x0,y0) in hoekpunten parameteropp. afleiden + grafisch weergeven. | ||
---- | |||
bespreek de constructie van tensor bezier product en leidt D(uv) af + grafische interpretatie | |||
---- | |||
===B-spline curven=== | ===B-spline curven=== | ||
| Regel 67: | Regel 72: | ||
---- | ---- | ||
hoe spline interpoleren met meervoudige knooppunten. | hoe spline interpoleren met meervoudige knooppunten. | ||
===algemeen=== | ===algemeen=== | ||
wat is bounding box quick rejection test uit algo om te bepalen of 2 rechten elkaar snijden | wat is bounding box quick rejection test uit algo om te bepalen of 2 rechten elkaar snijden | ||
| Regel 84: | Regel 93: | ||
wanneer is de inpakmethode (jarvis march) efficienter dan de methode van graham | wanneer is de inpakmethode (jarvis march) efficienter dan de methode van graham | ||
+(graham scan) | +(graham scan) | ||
===Voronoi diagrammen=== | ===Voronoi diagrammen=== | ||
bewijs: een voronoi diagramma van een vz S heft maximaal 2N - 5 voronoipunten en 3N - 6 voronoi zijden | bewijs: een voronoi diagramma van een vz S heft maximaal 2N - 5 voronoipunten en 3N - 6 voronoi zijden | ||
| Regel 98: | Regel 110: | ||
---- | ---- | ||
p(i) behoort tot de inwendige van V(i) asa V(i) is begrensd | p(i) behoort tot de inwendige van V(i) asa V(i) is begrensd | ||
===nabijheidsproblemen=== | ===nabijheidsproblemen=== | ||
wat betekent volgende uitspraak: probleem A is ?(N) transformeerbaar tot probleem B? | wat betekent volgende uitspraak: probleem A is ?(N) transformeerbaar tot probleem B? | ||
| Regel 105: | Regel 121: | ||
---- | ---- | ||
bespreek beknopt hoe een EMDB van een vz punten kan berkend worden in O(nlogn) bewerkingen | bespreek beknopt hoe een EMDB van een vz punten kan berkend worden in O(nlogn) bewerkingen | ||
===Fortune=== | ===Fortune=== | ||
bespreek de overganspunten bij fortune-algoritme | bespreek de overganspunten bij fortune-algoritme | ||
| Regel 114: | Regel 134: | ||
---- | ---- | ||
minkovski-som gebruiken en zeggen welke het is | minkovski-som gebruiken en zeggen welke het is | ||
==oefeningen== | ==oefeningen== | ||
===vraag1=== | |||
Gegeven een 3 link probleem L1 = 150 L2 = 75 L3 = 40 Los op voor een punt P dat op 180 cm van de schouder ligt. | |||
===vraag2=== | |||
Maak een hoog-niveau algoritme voor alle snijdingen van een verzameling cirkels. | |||
===vraag3=== | |||
een minkowski-som tekenen | |||
===vraag4=== | |||
Hoe kan je in O(n) bepalen of een lijnstuk Pi Pi+2 een diagonaal is van een eenvoudige veelhoek P1 P2...Pn<br> | |||
geef grote lijnen + hoge orde algoritme | geef grote lijnen + hoge orde algoritme | ||
===vraag5=== | |||
gegeven punten op cirkel. Vind de driehoek met het grootste oppervlak.<br> | |||
(opl mbv tegenvoetparen) | (opl mbv tegenvoetparen) | ||
===vraag6=== | |||
bespreek of 2 eenvoudige veelhoeken geheel of gedeeltelijk overlappen (uitleg + hoog niveau algo)<br> | |||
bespreek of 2 eenvoudige veelhoeken geheel of gedeeltelijk overlappen (uitleg | |||
+hoog niveau algo) | |||
in O((N + M) log (N + M)) bewerkingen | in O((N + M) log (N + M)) bewerkingen | ||
===vraag7=== | |||
1 punt gegeven en | 1 punt gegeven en allemaal lijnstukken (niet snijdende) rond dat punt<br> | ||
schrijf algo om te controleren of je een rechte kunt tekenen vanuit het gegeven | schrijf algo om te controleren of je een rechte kunt tekenen vanuit het gegeven punt tot al die rechten<br> | ||
(maw: welke rechten zijn zichtbaar voor dat punt) | (maw: welke rechten zijn zichtbaar voor dat punt) | ||
===vraag8=== | |||
gegeven een veelhoek | gegeven een veelhoek<br> | ||
bepaal of pi, pi+2 een diagonaal is van die veelhoek in O(n) | bepaal of pi, pi+2 een diagonaal is van die veelhoek in O(n) | ||
===vraag9=== | |||
n cirkels, elk bepaald door middelpunt pi en straal ri | n cirkels, elk bepaald door middelpunt pi en straal ri<br> | ||
bedenk een strategie om na te gaan of er cirkels snijden + algo | bedenk een strategie om na te gaan of er cirkels snijden + algo | ||
===vraag10=== | |||
stel p1, p2, ... pn putnen op de omtrek van eenzelfde cirkel | stel p1, p2, ... pn putnen op de omtrek van eenzelfde cirkel<br> | ||
geef een algo dat de grootste driehoek bepaald door 3 van deze punten in O( | geef een algo dat de grootste driehoek bepaald door 3 van deze punten in O(nlog n) | ||
===vraag11=== | |||
algoritme om na te gaan of pi,pi+1 diagonaal in eenvoudige veelhoek<br> | |||
is in O(n) | is in O(n) | ||
Versie van 1 jun 2006 19:42
De afbeelding(en) op deze pagina zijn storend groot.
Overleg hierover op Overleg:ExamenWikiExpansionPack/Stijl. |
(neem deze template weg als het gefixed is)
| http://www.cs.kuleuven.ac.be/~dirkr/foto.jpg |
oefeningen
oefening uit laatste oefenzitting
| http://static.flickr.com/70/152994638_00c7b383d1_m.jpg | http://static.flickr.com/74/152994136_19ebb442d2_m.jpg | http://static.flickr.com/52/152993572_347a6fb5af_m.jpg |
oefening op bepalen van het aantal snijpunten
| http://student.kuleuven.be/~s0105937/Fotos/pijlen.JPG |
Gegeven: een willekeurige verzameling lijnstukken
gevraagd: vind ALLE snijpunten
opl: iemand?
examen
theorie
Bezier curven
Bespreek C? continuiteit.
hoe bekomt men C? continuiteit bij samengestelde bezier curven
geef het algoritme van de Casteljau
variatieverminderingseigenschap algemeen + wat betekent ze specifiek voor beziercurven
bespreek subdivisie + methode
bespreek graadverhoging + bewijs formule + nut
waarom gebruikt men samengestelde beziercurven + wat voor problemen treden erbij op?
bespreek constructie van samengestelde b?ziercurven + voor/nadelen
tensor-product Bezier-veeltermen hoe? Afgeleide Dxy(x0,y0) in hoekpunten parameteropp. afleiden + grafisch weergeven.
bespreek de constructie van tensor bezier product en leidt D(uv) af + grafische interpretatie
B-spline curven
bewijs dat de sommatie tot een eigenschap geldt voor de genormaliseerdeB-splines dwz voor u ? [un, um)
hoe kan men bij splines punten laten interpoleren door het samennemen van controlepunten? hoeveel moeten er samenvallen?
variatieverminderingseigenschap algemeen + wat betekent ze specifiek voor splines
algoritme van de boor + nauwkeurige tekening en bewijs van correctheid
hoe kan je ervoor zorgen dat een deel van een spline curve een recht lijnstuk is? waarom?
hoe spline interpoleren met meervoudige knooppunten.
algemeen
wat is bounding box quick rejection test uit algo om te bepalen of 2 rechten elkaar snijden geef de 2 toepassingen in het algo + implementatie
bespreek het algoritme voor het bepalen van de onderbrug en bovenbrug waarom is de kleinste y-coordinaat een slechte schatting voor het bepalen van de onderbrug?
geef een algoritme dat in O(N log N) bewerkingen nagaat of in een vz van N lijnstukken er snijdende lijnstukken in voorkomen Bewijs correctheid van dit algoritme geef beknopt hoe dit algoritme en de gegevensstrukturen moeten aangepast worden om alle snijdingen te vinden
geef een algoritme voor de berekening van het VPP van een vz van N punten in O(nlog n) bewerkingen verantwoord de rekencomplexiteit
bespreek graham scan + correctheidsbewijs + toon aan dat dit O(nlogn)bewerkingen gebeurt
wanneer is de inpakmethode (jarvis march) efficienter dan de methode van graham +(graham scan)
Voronoi diagrammen
bewijs: een voronoi diagramma van een vz S heft maximaal 2N - 5 voronoipunten en 3N - 6 voronoi zijden
een voronoiveelhoek van een punt pi is begrensd <=> pi element van inw(CH(S)) + nut + waar hebben we dit gebruikt?
bewijs dat minimale doorloopboom deelverzameling is van de Delaunay triangulatie wat is het nut van deze eigenschap?
2 dichtste buren hebben een gemeenschappelijke voronoizijde: bewijs
geef strategie + hoog-niveau algoritme voor het vinden van de maximale lege cirkel binnen de COV van een verzameling punten.
p(i) behoort tot de inwendige van V(i) asa V(i) is begrensd
nabijheidsproblemen
wat betekent volgende uitspraak: probleem A is ?(N) transformeerbaar tot probleem B? waarvoor kan een dergelijke uitspraak nuttig gebruikt worden + vb
wat is een EMDB van een vz punten + verband met Voronoi diagramma van een vz punten?
bespreek beknopt hoe een EMDB van een vz punten kan berkend worden in O(nlogn) bewerkingen
Fortune
bespreek de overganspunten bij fortune-algoritme
Bespreek de events in het algoritme van Fortune Welke acties moeten ondernomen worden?
hoe bepaal je het gebied dat kan bereikt worden door een robotarm met 3 links is de volgorde van de stukken belangrijk?
minkovski-som gebruiken en zeggen welke het is
oefeningen
vraag1
Gegeven een 3 link probleem L1 = 150 L2 = 75 L3 = 40 Los op voor een punt P dat op 180 cm van de schouder ligt.
vraag2
Maak een hoog-niveau algoritme voor alle snijdingen van een verzameling cirkels.
vraag3
een minkowski-som tekenen
vraag4
Hoe kan je in O(n) bepalen of een lijnstuk Pi Pi+2 een diagonaal is van een eenvoudige veelhoek P1 P2...Pn
geef grote lijnen + hoge orde algoritme
vraag5
gegeven punten op cirkel. Vind de driehoek met het grootste oppervlak.
(opl mbv tegenvoetparen)
vraag6
bespreek of 2 eenvoudige veelhoeken geheel of gedeeltelijk overlappen (uitleg + hoog niveau algo)
in O((N + M) log (N + M)) bewerkingen
vraag7
1 punt gegeven en allemaal lijnstukken (niet snijdende) rond dat punt
schrijf algo om te controleren of je een rechte kunt tekenen vanuit het gegeven punt tot al die rechten
(maw: welke rechten zijn zichtbaar voor dat punt)
vraag8
gegeven een veelhoek
bepaal of pi, pi+2 een diagonaal is van die veelhoek in O(n)
vraag9
n cirkels, elk bepaald door middelpunt pi en straal ri
bedenk een strategie om na te gaan of er cirkels snijden + algo
vraag10
stel p1, p2, ... pn putnen op de omtrek van eenzelfde cirkel
geef een algo dat de grootste driehoek bepaald door 3 van deze punten in O(nlog n)
vraag11
algoritme om na te gaan of pi,pi+1 diagonaal in eenvoudige veelhoek
is in O(n)