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.
Rešitev:
URG:Naloga2:Vsebnostni_Test - Naložil: Narmotur
Oglejte si še:
Komentarji
Te kaj tišči?
