Labb 4

Deadline för labb 4 är fredag 8 december, kl 12.00

Läs igenom labbinstruktionerna innan ni börjar.

Tips: I speciellt C++ men även Java är det ganska praktiskt att använda iteratorer för att representera vektorer/mängder/etc. För mer detaljer se Labb 1.

För alla uppgifter gäller att lösningen måste vara effektiv i fråga om tid och minne. I de fall uppgiften är att implementera en specifik algoritm går det bra att implementera en annan algoritm så länge den har samma eller bättre komplexitet.

Observera att API-förslagen nedan är att betrakta som pseudo-kod. Ni måste översätta dem till ert favoritspråk på det sätt ni tycker verkar bäst.

4.1 Punktklass

För den här labben behöver du implementera en klass för att hantera 2-dimensionella punkter (vektorer). Klassen bör innehålla vanliga operationer på vektorer, t.ex.

punktvis addition/subtraktion
multiplikation/division med skalär
skalärprodukt
kryssprodukt
avstånd
vinklar

Det kan antagligen också vara praktiskt att tillåta olika datatyper för koordinaterna (speciellt möjlighet att kunna välja mellan int och double) m.h.a. templates eller generics. Observera dock att man för vissa saker, t.ex. vinklar, vill ha ut doubles oavsett vilken typ koordinaterna har.

4.2 Polygoner

Uppgift 4.2.1: beräkna arean av en enkel polygon(1p)

Skriv en metod för att beräkna arean av en (enkel) polygon.

Förslag till API:
double polygon_area(point[])

Rekommenderad tidskomplexitet: O(n).

Problem-id hos Kattis: polygonarea.

Uppgift 4.2.2: Punkt inuti polygon (1p)

Skriv en metod för att avgöra om en punkt ligger inuti en (enkel) polygon.

Förslag till API:
int inside_poly(point p, point[] poly)
där funktionen skulle returnera -1, 0, eller 1 beroende på om punkten låg utanför, på randen, eller innanför polygonen.

Rekommenderad tidskomplexitet: O(n).

Problem-id hos Kattis: pointinpolygon.

4.3 Linjer och linjesegment

Uppgift 4.3.1: Skärningspunkt för linjesegment (1p)

Skriv en metod som kan hitta skärningspunkten mellan två linjesegment. Metoden ska kunna identifiera om skärningen saknas, om skärningen är en punkt, eller om skärningen är ett helt linjesegment (d.v.s. om de två segmentet är parallella och överlappar).

Förslag till API:
point[] intersect(pair<point, point>, pair<point, point>)
där den returnerade vektorn skulle ha 0, 1 eller 2 element beroende på om resultatet saknas, är en punkt, eller ett linjesegment.

Problem-id hos Kattis: segmentintersection.

Uppgift 4.3.2: Avstånd mellan linjesegment (1p)

Skriv en metod för att beräkna avståndet mellan två linjesegment (d.v.s. det kortaste avståndet mellan någon punkt i det ena segmentet och någon punkt i det andra segmentet)

Förslag till API:
double line_seg_dist(pair<point, point>, pair<point, point>)

Problem-id hos Kattis: segmentdistance.

4.4 Punktmängder

Uppgift 4.4.1: närmsta par av punkter - effektiv algoritm i genomsnitt (1p)

Skriv en metod för att hitta ett par av punkter som ligger närmast varandra i en punktmängd. Metoden ska ha förväntad körtid O(n log n) under antagandet att indatapunkterna är likformigt fördelade i en delkvadrat av R². Ni behöver inte kunna bevisa att er algoritm har den förväntade körtiden.

Förslag till API:
int[2] closest_pair(point[])
Där metoden returnerar indexen för ett par av punkter som ligger på minimalt avstånd från varandra.

Problem-id hos Kattis: closestpair1.

Uppgift 4.4.2: närmsta par av punkter - effektiv algoritm i värsta fall(1p)

Skriv en metod för samma problem med värsta falls-körtid O(n log n).

Problem-id hos Kattis: closestpair2.

Uppgift 4.4.3: beräkna konvexa höljet (1p)

Skriv en metod för att beräkna det konvexa höljet av en punktmängd. Metoden ska kunna hantera degenererade punktmängder (t.ex. att alla punkter ligger längs en linje). Metoden ska ha komplexitet O(n log n).

Förslag till API:
point[] convex_hull(point[])
där den returnerade arrayen innehåller punkterna på höljets rand i ordning (medsols eller motsols). Det kan ibland vara mer praktiskt att returnera en int[] som innehåller indexen för punkterna som ingår i höljet.

Problem-id hos Kattis: convexhull.

Uppgift 4.4.4: beräkna antal kolinjära punkter (1p)

Skriv en metod som givet en punktmängd hittar en maximal mängd kolinjära punkter (d.v.s. en mängd punkter som alla ligger längs samma räta linje). Det räcker att du hittar det maximala möjliga antalet punkter i en sådan mängd. Din metod bör ha väsentligt bättre komplexitet än Ω(n³).

Förslag till API:
int number_of_colinear(point[])

Problem-id hos Kattis: maxcolinear.

Uppgift 4.5: Catalantal

Uppgift 4.5.1: Implementera beräkning av Catalantal (1p)

Problem-id hos Kattis: catalan.