URG: 2. kolokvij [Update: rešitve]
Zaradi praznikov (in enkratne odsotnosti profesorja) smo imeli pred tem kolokvijem predavanja le 2-krat.
Tako so prišle v upoštev naslednja poglavja (kot so zapisana v knjigi Borut Žalik: Algoritmi računalniške geometrije):
- Ravninska triangulacija (zadnji del):
- Inkrementalni konstrukcijski algoritem Delanauyeve triangulacije z iskanjem najbližje točke
- Algoritem DT s preiskovalno premico in napredujočo fronto
- Voronoiev diagram:
- Definicija Voronoievih diagramov
- Lastnosti VD
- Uporaba VD
- Algoritmi za konstrukcijo Voronoievih diagramov (presek polravnin, inkrementakna metoda,metoda deli in vladaj, metoda s preiskovalno premico)
- Posplošeni Voronoievi diagrami
URG: 2.vaja: Vsebnostni test
Navodilo:
Implementirajte vsebnostni algoritem točka-mnogokotnik z računanjem kotov.
Vhod predstavljata mnogokotnik, ki ne vsebuje lukenj, in točka p, za katero preverjamo vsebnost.
Izhod algoritma nam pove:
- ali točka leži v notranjosti mnogokotnika,
- ali točka leži zunaj mnogokotnika,
- ali pa točka leži na mnogokotniku (bodisi na robu bodisi na oglišču).
Algoritem poteka tako, da potegnemo poltrak od p do vsakega oglišča mnogokotnika. Nato izračunamo kote med vsakim parom poltrakov, kote pa seštevamo. Če je vsota vseh kotov enaka 2pi , je točka v notranjosti. Če je vsota kotov enaka 0, leži točka zunaj mnogokotnika. Za preverjanje enakosti uporabite toleranco epsilon.
Robni primeri:
- točka p leži na točki mnogokotnika,
- točka p leži na robu mnogokotnika.
Več o algoritmu najdete v knjigi Algoritmi računalniške geometrije (Žalik).
Naloga je vredna 4 točke.
APS: 9. vaja – Iskanje v širino
Navodilo:
V skladu z navodili implementirajte iskanje v širino na enakem grafu, kot ste ga imeli pri prejšnji nalogi, s tem, da ceno povezav zanemarite, oziroma jo postavite na vrednost 1.
Naloga je vredna 3 točke.
APS: 8. vaja – Minimalno vpeto drevo – Kruskalov algoritem
Navodilo:
V skladu z navodili implementirajte algoritem za iskanje minimalnega vpetega drevesa – Kruskalov ogoritem. Vhodni graf preberite iz vhodne datoteke graf.txt.
Vrednost naloge: 4 točke.
APS: 6. vaja – Hitro uredi na dvojno povezanem seznamu
Navodilo:
V skladu z navodili implementirajte algoritem Hitro uredi na dvojno povezanem seznamu.
Vrednost naloge je 2 točki.
APS: 5. vaja – Hitro uredi
Navodila:
V skladu z navodili implementirajte algoritem hitro uredi.
Vaja je vredna 4 točke.
