29 KB
Lab2.zip

ZADATAK VJEŽBE

Izraditi algoritme za iscrtavanje i bojanje konveksnog poligona, te za ispitivanje odnosa točke i danog poligona. Poligon je određen nizom zadanih točaka.

KONCEPTUALNO RJEŠENJE

Definiramo dogovorno da je redoslijed točaka u poligonu zadan u smjeru kazaljke na satu. To nam omogućava da pouzdano odredimo odnos točke i poligona ispitivanjem skalarnog produkta točke i pojedinih vektora bridova. Kada je izračunati skalarni produkt manji od nule za sve bridove, smatramo da je točka unutar poligona, a u suprotnom smatramo da je izvan njega.

Bojanje linije ostvarujemo tako da poligon dijelimo na horizontalne ispitne linije, za svaku liniju pronađemo točke lijevog i desnog ruba i tada osvijetlimo sve točke između njih. Lijeve i desne rubove tražimo tako da među sjecištima ispitne linije i bridova biramo najdesniju točku na lijevim bridovima i najljeviju točku na desnim bridovima.

Bridove dijelimo na lijeve i desne ispitivanjem visine njihovih početnih točaka (x_i, y_i) i završnih točaka (x_j, y_j), po pravilu:

• ako je y_j < x_i, brid je lijevi,
• ako je y_j > x_i, brid je desni.

PROGRAMSKO OSTVARENJE

Poligon čini skup točaka. Njihov broj vodimo u globalnoj varijabli:

int broj_vrhova;

a koordinate u poljima:

int vrh_x[];
int vrh_y[];

Točke su u tim poljima pohranjene strogim redom, tako da su u smjeru kazaljke na satu. Tim redom one formiraju bridove, za koje izračunavamo koeficijente A, B i C. Njih pohranjujemo također u zasebna polja:

float a[], b[], c[];

Koristimo još i globalne varijable y_min i y_max, u kojima čuvamo maksimalnu i minimalnu y-koordinatu koje se javljaju među točkama poligona.

int y_min, y_max;

Algoritam kojim određujemo prostor kojeg treba osvijetliti i time iscrtavamo oblik poligona je sljedeći:

Za sve linije y, počevši od vrijednosti y_min do vrijednosti y_max:
    Neka je L = -1000000.
    Neka je D = 1000000.
    Za sve bridove poligona:
        Ako brid nije horizontalan:
            Nađi sjecište brida s ispitnom linijom i pripadnu koordinatu x.
            Ako je brid "lijevi", a x manji od dotad najmanjeg, tada:
                Zapisati to u varijablu L.
            Inače, ako je brid "desni", a x veći od dotad najvećeg, tada:
                Zapisati to u varijablu D.
    Ako je L < D, tada:
        Iscrtati liniju od točke (L, y) do točke (D, y).

Nakon što popunimo unutrašnjost poligona, iscrtamo mu i bridove, da bi dobio što jasniji oblik.

UPUTE ZA KORIŠTENJE

Program se pokreće bez parametara:

Lab2.exe

Nakon pokretanja, traži se od korisnika da definira poligon za iscrtavanje. Najprije je potrebno zadati broj vrhova željenog poligona i zatim koordinate svakog pojedinog vrha (mogu se odrediti i klikom miša):

Kad su svi vrhovi određeni, poligon se iscrtava i popunjava. Zatim se unose koordinate ispitne točke.

Program ispituje u kojem je odnosu točka prema poligonu (unutar ili izvan njega) i daje informaciju korisniku:

Zadavanje novih točaka za ispitivanje može se nastaviti po želji.