Toepassingen van Meetkunde in de Informatica

Fout bij het aanmaken van de miniatuurafbeelding: Bestand is zoek

oefeningen

oefening uit laatste oefenzitting

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

Fout bij het aanmaken van de miniatuurafbeelding: Bestand is zoek

bepalen van alle snijpunten in een willekeurige verzameling lijnstukken (klik voor groter)

Gegeven: een willekeurige verzameling lijnstukken
Gevraagd: vind een algoritme dat ALLE snijpunten vindt
Oplossing: iemand?

Misschien is dit een oplossing. Gebruik het algoritme uit de cursus dat true of false teruggeeft als er twee of meerdere lijnstukken in een set snijden. Maak van return false een commando dat het gevonden snijpunt opslaagt in een output vector. Er is volgens mij wel nog een probleem: Wanneer er meerdere snijpunten vallen tussen 2 begin of eindpunten. Waarschijnlijk moet je ook op intersecties testen bij eindpunten (maar wel geen dubbels toevoegen aan de output) Het zou kunnen dat dat genoeg is. Heb het nog niet nagekeken voor alle gevallen. Anders is nog een andere oplossing: elk snijpunt dat je vindt toevoegen als een locatie waar de doorlooplijn moet geevalueerd worden, snijpunt 2x toevoegen aan T (voor elk van de betrokken lijnstukken) waarbij je zorgt dat het lijnstuk dat bovenaan stond nu beneden staat (op dit moment snijden ze de doorlooplijn op hetzelfde punt, maar hierachter wisselen ze van plaats) en beginpunten van de 2 betrokken rechten verwijderen.

Idee: zoals bovenstaande persoon zei: neem doorlooplijnalgoritme, ipv. return true hou je de koppels lijnstukken bij, en controleer achteraf op dubbels. Haal deze eruit, et voilla.

Oefeningen links

De pagina met de opgaven van de oefenzittingen en van het practicum, alsook links naar extra informatie.

Bevat ook alle links die in de cursus vermeld worden. http://www.cs.kuleuven.be/~krisd/TMI/

Examen

Informatie

Het examen is gesloten boek, behalve het deel over padplanning. Je mag dus Hoofdstuk 8 van O'Rourke gebruiken op het examen (deze blz. mogen enkel informatie over padplanning bevatten !). Je mag ook het formularium over Deel I. Curven en oppervlakken (zie achteraan de Nederlandstalige cursusnota's) gebruiken op het examen.

denk ook nooit dat iets te simpel is, om gevraagd te worden:
Roose durft ALLES te vragen

Roose is gesteld op ordelijkheid. Lelijk geschrift, doorgeschrapte zaken of onnauwkeurigheden kunnen hem irriteren. Vergeet geen potlood en lat mee te nemen om zaken te kunnen verduidelijken. Een passer is ook wel handig voor de oefeningen over robotarmen (komt vaak voor).

Theorie

Bézier curven

• Bespreek $C^2$ continuiteit.
• hoe bekomt men $C^2$ continuiteit bij samengestelde bézier curven
• geef het algoritme van de Casteljau
• variatieverminderingseigenschap algemeen + wat betekent ze specifiek voor béziercurven
• bespreek subdivisie + methode
• bespreek graadverhoging + bewijs formule + nut
• waarom gebruikt men samengestelde béziercurven + 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 genormaliseerde B-splines dwz voor $u\in [u_n,u_m)$
• hoe kan men bij splines punten laten interpoleren door het samennemen van controlepunten? hoeveel moeten er samenvallen?
• Hoe kan men bij splines punten laten interpoleren door het samennemen van knooppunten?
• 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

gegeven punten op cirkel. Vind de driehoek met het grootste oppervlak.
(opl mbv tegenvoetparen)

vraag5

bespreek of 2 eenvoudige veelhoeken geheel of gedeeltelijk overlappen (uitleg + hoog niveau algo)
in O((N + M) log (N + M)) bewerkingen

vraag6

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)

vraag7

gegeven een eenvoudige veelhoek
bepaal of pi, pi+2 een diagonaal is van die veelhoek in O(n)

vraag8

n cirkels, elk bepaald door middelpunt pi en straal ri
bedenk een strategie om na te gaan of er cirkels snijden + algo

vraag9

algoritme om na te gaan of pi,pi+1 diagonaal in eenvoudige veelhoek
is in O(n)
Klopt dit wel: een diagonaal is een lijnsegment tussen twee vertices (hoekpunten) die niet aangrenzend zijn, terwijl pi en pi+1 wel aangrenzend zijn.

vraag10

Gegeven, p cirkels die elkaar niet overlappen, met gegeven middelpunten m en stralen r.
Ook gegeven: n punten p. Elk punt ligt in 1 cirkel.
Bedenk een algoritme dat in O(np lg(np)) kan bepalen welke punten in welke cirkels liggen.
Je moet geen rekening houden met randgevallen, om het algoritme iets simpeler te houden.
Tip: bv doorlooplijnalgoritme

Recente examens

08/06/2009 namiddag

1. Bespreek C² continuïteit bij samengestelde béziercurven
2. EMDB uitleggen
3. Robotarmoefening met 3 stukken
4. Bespreking van het verslag.
5. Gegeven een verzameling van N aantal niet-snijdende lijnstukken en een punt p. Hoe bereken je welke lijnstukken zichtbaar zijn voor p? (Doorlooplijn = roterende rechte door p).

08/06/2009 (Bart) - Voormiddag

1. Hoe kan je een spline curve laten interpoleren in een punt door controlepunten te laten samenvallen? Hoeveel en welke controlepunten moeten er samenvallen? Hoe kan je een spline curve laten interpoleren in een punt door knooppunten te laten samenvallen? Hoeveel en welke knooppunten moeten er samenvallen?
2. De Voronoi-veelhoek behorende bij een punt Pi element van S is begrensd als en slechts als Pi element van inw(CH(S)).
3. Minkowski-som (zie oefenzitting 9)
4. Bespreking van het verslag.
5. Hoe kan je in O(n) bewerkingen testen of een lijnstuk PiPi+2 een diagonaal is in een eenvoudige veelhoek V = P1 P2...Pn? Een diagonaal is een lijnstuk PiPj dat, op de eindpunten na, volledig in inw(V) ligt. (PiPj snijdt de veelhoek enkel in de punten Pi en Pj). De hoekpunten van V zijn in tegenwijzersin genummerd. Leg eerst de algemene strategie uit, en geef dan een 'hoog niveau' pseudo-code beschrijving van het algoritme. Je hoeft geen rekening te houden met speciale (rand) gevallen.

01/09/2008

1. Illustruur het algoritme van de Boor, voor n=3, toon correctheid aan. Meetkundige continuïteit is genoeg.
2. Bewijs: Bij een Voronoi diagramma geldt: Het veelvlak dat hoort bij het gebied rond een site-punt p is begrensd als en slechts als p behoort tot de inwendige van de convex hull rond alle punten p element van S van het Voronoi diagramma.
3. Minkowski-som en bijhorend sterdiagram tekenen voor een gegeven figuur en robot.
4. Gegeven een verzameling punten p1...pn. Een verzameling cirkels met middelpunten m1...mk en stralen r1...rk. De cirkels snijden/overlappen elkaar niet. Elk punt ligt in 1 cirkel. Zoek een algoritme dat in O((n+k).log(n+k)) voor elk punt bepaalt tot welke cirkel het behoort. Strategie uitleggen en pseudo-code schrijven.

01/02/2008

1. Hoe kan men bij splines punten laten interpoleren door het samennemen van controlepunten? Hoeveel en welke controlepunten moeten er samenvallen?
2. Uitleggen hoe je het verste puntenpaar van een puntenverzameling kan bepalen in O(n.log(n)). Hoog niveau beschrijving, niet zo gedetailleerd als in de cursus. Verklaar de rekencomplexiteit.
3. Minkowski-som en bijhorend sterdiagram tekenen voor een gegeven figuur en robot.
4. Bespreking van het practicum.
5. Gegeven een verzameling punten p1...pn. Een verzameling cirkels met middelpunten m1...mk en stralen r1...rk. De cirkels snijden/overlappen elkaar niet. Elk punt ligt in 1 cirkel. Zoek een algoritme dat in O((n+k).log(n+k)) voor elk punt bepaalt tot welke cirkel het behoort. Strategie uitleggen en pseudo-code schrijven.

18/01/2008 (1)

1. Bespreek hoe men C²-continuïteit kan bekomen bij samengestelde Bézier-curven
2. Hoe kan je de Euclidische Minimale Opspannende Boom van een puntenverzameling in O(n lg n) berekenen? Geef daarbij duidelijk aan op basis van welke eigenschappen je dit doet.
3. Robotarm met L1=70cm, L2=20cm, L3=30cm en het punt p op 25cm van de schouder van het arm.
4. Bespreking van het practicum
5. Gegeven een verzameling van n niet-snijdende lijnstukken en een punt P die niet op één van de lijnstukken ligt, bepaal in O(n lg n) alle lijnstukken die zichtbaar zijn vanuit P.

18/01/2008 (2)

1. Hoe kan men interpolatie bekomen bij splines door middel van samennemen van knooppunten
2. Voronoi doorlooplijnalgoritme met fortune: wat zijn overgangspunten en bespreek welke acties er moeten ondernomen worden.
3. robotarm met L1=45, L2=25 en L3=30
4. bespreking practicum
5. gegeven een aantal cirkels: geef een efficiente berekening (n log2(n) ) voor het bepalen of er snijdende cirkels zijn.

--> HINT: Gebruik niet de middelpunten bij een doorlooplijn, maar de uiterste linkse waarden (x+r) en de uiterste rechtse waarden (x-r) van de cirkel bij een doorlooplijn van links naar rechts

04/09/2007

1. bespreek subdivisie + methode + continuiteit vwd + nut van subdivisie
2. geef een algoritme voor de berekening van het VPP van een vz van N punten in O(nlog n) bewerkingen verantwoord de rekencomplexiteit
3. minowski som tekenen op figuur met bijhorende sterdiagram + extra uitleegt hoe aan de oplossing bekomen bent.
4. bespreking practicum
5. gegeven een aantal vierhoeken met zijn linkeronder-hoekpunt en zijn rechteboven-hoekpunt nagaan of ze geheel of gedeeltelijk overlappen (uitleg + hoog niveau algo)in O(nlog (n)) bewerkingen.

21/08/2007

1. Bespreek $C^2$ continuiteit.
2. Voronoi doorlooplijnalgoritme: bespreek de overgangspunten, hoe je weet waar ze zijn, en welke acties je moet ondernemen als je een tegenkomt. (vergeet niet het bijvoegen en verwijderen van cirkelevents als er een boog bijkomt of verdwijnt)
3. minowski som tekenen op figuur met bijhorende sterdiagram
4. bespreking practicum
5. oefening:gegeven: een aantal cirkels met gegeven middelpunt en straal. Zoek of er cirkels zijn die snijden, maar cirkels die volledig in een andere cirkel zit snijdt niet. Bespreek eerst hoe je het gaat doen, en geef dan een ruw algoritme in pseudocode. Er bestaat een doorlooplijnalgoritme van O(nlogn). (oplossing: denk aan snijdende lijnenalgoritme, en om de complexiteit goed te krijgen hou je een gesorteerde boom bij met al de onderste van de cirkels, en een met alle bovenste, en zo vergelijk je met boven en onder).

15/06/2007

1. hoe kan men bij splines punten laten interpoleren door het samennemen van controlepunten? hoeveel controlepunten moeten er samenvallen?
2. verste puntenpaar algoritme
3. minowski som tekenen op figuur met bijhorende sterdiagram
4. bespreking practicum
5. algoritme om te bepalen welke punten $P_1$...$P_n$ in welke cirkel $C_1$...$C_k$ met stralen $R_1$...$R_k$ zit waarbij geen punten uit de cirkels zitten en in O(n+k $lo{g}_2$ n+k) opgelost moet worden

15/06/2007

1. hoe kan men bij splines punten laten interpoleren door het samennemen van controlepunten? hoeveel controlepunten moeten er samenvallen?
2. Voronoi doorlooplijnalgoritme: bespreek de overgangspunten, hoe je weet waar ze zijn, en welke acties je moet ondernemen als je een tegenkomt. (vergeet niet het bijvoegen en verwijderen van cirkelevents als er een boog bijkomt of verdwijnt)
3. een oefening met een robotarm met drie delen (L1:90cm, L2:50cm, L3:65 cm) en een punt op 35 cm van middelpunt (oplossing: deel 2 en deel 3 samennemen)
4. bespreking practicum
5. oefening:gegeven: een aantal cirkels met gegeven middelpunt en straal. Zoek of er cirkels zijn die snijden, maar cirkels die volledig in een andere cirkel zit snijdt niet. Bespreek eerst hoe je het gaat doen, en geef dan een ruw algoritme in pseudocode. Er bestaat een doorlooplijnalgoritme van O(nlogn). (oplossing: denk aan snijdende lijnenalgoritme, en om de complexiteit goed te krijgen hou je een gesorteerde boom bij met al de onderste van de cirkels, en een met alle bovenste, en zo vergelijk je met boven en onder).

19/06/2006 Voormiddag

1. Hoe verkrijgen we $C^2$ continuiteit bij bézier curven? Leg uit.
2. Welk soorten events zijn er bij het algoritme van Fortune. Welke acties moeten er gebeuren en hoe plannen we ze?
3. 3-link probleem oplossen voor drie gegeven armen en punt. $l_1$ = 90cm, $l_2$ = 50cm, $l_3$ = 65cm. Eindpunt ligt op 35 cm van schouder.
4. Practicum bespreking
5. Gegeven een verzameling cirkels. Ontwerp een algoritme om te bepalen of er cirkels snijden. Leg eerst je strategie uit en geef dan pseudo-code. Er bestaat een doorlooplijnalgoritme met O(n log n). (Allemaal gegeven)

Minder recente examens

07/06/2004, voormiddag

1. $C^2$ continuiteit bij bézier-curve. Wat? Hoe?
   • $C^0-C^1-C^2$
     
   • afleiden, invullen linkercurve t=1; rechtercurve t=0
   • nultermen schrappen... Gelijkstellen... de verhoudingen rollen eruit... $\mathrm{\Delta }{U}_i$ in de formule is trouwens de lengte van het interval waarvoor dat segement geldt...
2. Voronoi-doorlooplijn-algoritme (Fortune)
   Wat zijn de 'events'; hoe vind je ze, welke acties moeten er bij welke events gedaan worden? Exhaustief zijn, maar beknopt in de uitleg bij de acties.
   • site-events... circle-events toevoegen en verwijderen...
   • circle-events... circle-events toevoegen en verwijderen... you know the drill
3. Minkowski-som maken... zeer gelijkaardige figuur dan gelijk bij oefenzitting 9. Via sterdiagram.
4. N Punten op een cirkel. Zoek de grootste driehoek.
   • Strategie:
     • Doorloop driehoeken met basis 2 opeenvolgende punten; dan met 1 pt. ertussen; ... tot N/2.
     • Voor die voorwaarde op de basis, telkens rondlopen gelijkaardig aan de tegenvoetersparen van het verste-puntenpaar-probleem. => Je kan de tegenvoeter van de vorige gebruiken bij de volgende, ... voor dezelfde basis.
     • onthoud doorheen het algo de grootste driehoek.
   • Hoog-niveau-algoritme. -> triviaal
   • Complexiteit:
     • sorteer de punten naar stijgende poolhoek :Nlog(N)
     • buitenste lus N/2
     • binnenste lus N
     • allerbinnenste lus: O(1)
     • => totaal O(NlogN + N²) => O(N²)
5. Bespreking van het practicum.