ZADATAK VJEŽBE

Osmisliti algoritam za ispitivanje odnosa točke i konkavnog poligona, kao i za njegovo bojanje.

KONCEPTUALNO RJEŠENJE

Za određivanje položaja točke u odnosu na poligon nije dovoljno ispitati odnos zadane točke i bridova poligona, jer kod konkavnog poligona oni mogu biti u bilo kojem odnosu. Potrebno je povući zraku iz točke i vidjeti koliko puta ona siječe bridove poligona, te ako je broj sjecišta neparan, zaključak je da je točka unutar poligona; u suprotnom, slijedi zaključak da je izvan njega.

Kod bojanja takvog poligona, ako se ono izvodi tako da se poligon podijeli na horizontalne linije koje se zatim zasebno razmatraju, nužno je svaku od tih ispitnih linija razdijeliti na segmente koji su naizmjenično izvan i unutar poligona, i ispunjavati samo parne segmente, tj. one koji su u poligonu. To ćemo moći tako da svakoj ispitnoj liniji pronađemo x-koordinate sjecištâ i presložimo ih u rastućem poretku.

PROGRAMSKO OSTVARENJE

Algoritam koji traži broj sjecišta desno od točke i ukupan broj sjecišta na ispitnoj liniji ispod te točke je sljedeći:

Postaviti brojač n0 na nulu.
Za sve bridove poligona:
    Ako brid siječe ispitnu liniju:
        Naći sjecište, tj. njegovu x-koordinatu.
        Ako je sjecište desno od točke (na zraci):
            Povećati brojač n0.
        Zabilježiti sjecište u niz sjecišta s[].
    Inače, ako početni vrh brida sjedi točno na ispitnoj liniji:
        Pronaći vrh koji dolazi neposredno prije tog vrha; nazovimo ga "prethodnim vrhom".
        Pronaći prvi vrh koji dolazi poslije, a nalazi se iznad ili ispod ispitne linije; njega
        nazovimo "slijedećim vrhom".
        Ako su i "prethodni vrh" i "slijedeći vrh" obojica iznad ispitne linije ili ispod nje:
            Ispitna linija je tangenta, i zato pronađeno sjecište više ne smatramo sjecištem.
        Inače:
            Sjecište je potvrđeno, i zato ga zabilježimo u niz sjecišta s[].
            Ako je sjecište desno od točke (na zraci):
                Povećati brojač n0.
Sortirati niz sjecišta s[] po rastućem poretku.
Ako je brojač n0 neparan, točka je unutar poligona; inače je izvan njega.

UPUTE ZA KORIŠTENJE

Program se pokreće bez parametara:

Lab3.exe

Nakon pokretanja, program traži od korisnika da unese broj vrhova poligona i zatim njihove koordinate. Vrhovi se mogu zadati i mišem:

Kad su određeni svi vrhovi, poligon se iscrtava, te program zatim omogućava korisniku da zadaje ispitne točke. Za svaku ispitnu točku ispisuje se da li je ona unutar poligona ili izvan njega:

Desni klik miša pokreće program ispočetka, čime se prelazi na novi poligon.