Crtanje poligona


Uvod

Poligon se sastoji od geografskih i topoloških padataka. Geografski podaci su koordinate vrhova Vi(xi yi hi). gdje je i=1,...,n. Topološke podatke predstavljaju popis vrhova poligona L(Vi), gdje je i=1,...,n. Redoslijed vrhova u popisu L može biti u smjeru kazaljke na satu ili suprotan smjeru kazaljke na satu. Jednadžba pravca na kome leži brid bi poligona L, ili kraće jednadžba brida bi, određena je vektorskim produktom početnog i završnog vrha brida:

bi = Vi x Vi+1, i = 1 .. n-1,
bn = Vn x V1, i = n.

Poligone dijelimo na konveksne i konkavne. Poligon je konkavan ako ima jedan ili više konkavnih vrhova. Vrh Vi je konkavan ako leži na konkavnom dijelu poligona, tj. Vi: bi-l Vi+1 > 0. Poligon je konveksan ako nije konkavan, tj. ako svi vrhovi Vi leže na konveksnom dijelu poligona. Pri tome vrijedi: Vi: bi-l Vi+1 < 0 za sve i=1,...,n.

Implementacija vježbe

Sama implementacija vježbe sastoji se od JAVA appleta za crtanje konveksnih i konkavnih polinoma sa mogućnosti određivanja odnosa polinoma i proizvoljne točke i  bojanje polinoma.
Klikom na lijevi gumb miša odabire se vrh polinoma (u slučaju unosa više od dva vrha na istom vodoravnom pravcu pamti se samo prvi i zadnji vrh), a desnom potvrđuje unos vrhova te iscrtavanje samog polinoma. Vrhovi se unose u dinamičku listu (class java.util.Vector) točaka (class java.awt.Point). Popis vrhova čini dinamička lista (class java.util.Vector) brojeva (class java.lang.Integer) u koju se spremaju indeksi vrhova (1,2,3,...,n-1,1).
Nakon unosa svih vrhova radi se slijedeće:
  1. Kao zadnji vrh dodamo prvi vrh u listu vrhova
  2. Pronađe se x koordinata najlijevijeg vrha (Xmin), x koordinata najdesnijeg vrha (Xmax), y koordinata najgornjeg vrha (Ymin) i y koordinata najdonjeg vrha (Ymax).
  3. Izračunaju se koeficijenti (a,b,c) jednadžbi bridova polinoma prema već ranije navedenoj formuli, tj. :  
ZA i=0, n-1
bi = VL(i) x VL(i+1) 
  1. Uredi se orijentacija vrhova tako da bude uvjek u smjeru kazaljke na satu. Redoslijed vrhova je u smjeru kazaljke na satu ako postoji barem jedan brid za koji vrijedi da su svi vrhovi poligona ispod toga brida, odnosno ako postoji i tako da za svaki j vrijedi : biVj < 0, gdje je  i = 0,..., n-1, j=0,...,n-1.
Konkretno (u opisima se koristi slijedeća notacija: x(VL(j)) je x koordinata vrha VL(j), y(VL(j)) je y koordinata vrha VL(j), a(bi) je koeficijent a brida bi, b(bi) je koeficijent b brida bi i c(bi) je koeficijent c brida bi):

ZA i=0, n-1
    ZA j=0, n-1 RADI
        AKO x(VL(j)) a(bi) + y(VL(j)) b(bi) +c(bi) > 0 ONDA PRISILNI IZLAZ IZ UNUTRAŠNJE PETLJE
    KRAJ UNUTRAŠNJE PETLJE
    AKO JE j JEDNAK n-1 ONDA PRISILNI IZLAZ IZ VANJSKE PETLJE
KRAJ VANJSKE PETLJE
AKO JE i < n-1ONDA KRAJ, jer je smjer dobar
SUPROTNO
    ZA i=0,j=n-2, i<n-1  RADI
        Li=j
        j=j-1
 KRAJ PETLJE
PONOVO IZRAČUNAJ KOEFICIJENTE BRIDOVA
  1. Provijeriti da li je polinom konkavan ili konveksan prema navedenom kriteriju.
AKO  x(VL(1)) a(bn-2) + y(VL(1)) b(bn-2) + c(bn-2) > 0 ONDA POLINOM JE KONKAVAN
ZA i=1, i<n-1RADI
    AKO   x(VL(i+1)) a(bi-1) + y(VL(i+1)) b(bi-1) + c(bi-1) > 0 ONDA POLINOM JE KONKAVAN
KRAJ PETLJE
POLIGON JE KONVEKSAN

Nakon ova inicijalna četiri koraka omogućuje se korisniku da klikne na proizvoljno mjesto appleta radi provjere da li je točka unutar polinoma ili ne. Algoritam je slijedeći:
AKO JE Poligon konkavan ONDA
    ODREDITI KOEFICIJENTE PRAVCA (ZRAKE KROZ ODABRANU TOČKU), tj. a=0, b=1,c=-y
    POSTAVITI x0=x I y0=y
    IZVESTI POSTUPAK V31(Z,x0,y0)
    AKO JE BROJ x KOORDINATA SJECIŠTA KOJI VRATI V31 PARAN ONDA
        TOČKA JE IZVAN POLIGONA
    INAČE JE TOČKA U POLIGONU
INAČE AKO JE Poligon konveksan ONDA
    ZA i=0, i<n-1
        AKO x a(bi) + y b(bi) + c(bi) > 0 TOČKA JE IZVAN POLIGONA
TOČKA JE U POLIGONU

Ako se uspostavi da je točka u poligonu poligon se boji na slijedeći način:
AKO JE Poligon konkavan ONDA
    ZA y0=Ymin, Ymax RADITI
    x0=Xmin-1;
    KOEFICIJENTE ISPITNE ZRAKE POSTAVITI NA a=0, b=1, c=-y0
    IZVESTI POSTUPAK V31(Z,x0,y0)
    AKO JE BROJ x KOORDINATA SJECIŠTA "S" KOJI VRATI V31 >=2 ONDA
        POSORTIRATI VRAĆENE x KOORDINATE SJECIŠTA Si UZLAZNO
        ZA y1=0,  S-1 , korak  = 2
            NACRTATI  LINIJU  OD TOČKE (Sy,y0) DO TOČKE (Sy1+1,y0)

INAČE AKO JE Poligon konveksan ONDA
    ZA y0=Ymin, Ymax RADITI
        L=Xmin; D=Xmax;
        ZA i=0, n-1 RADITI
            AKO a(bi) !=0 ONDA
                 x1=-(b(bi)*y0+ c(bi)) / a(bi)
                AKO  y(VLi)  < y(VLi+1) I AKO x1>L
                    ONDA   L=x1
                    AKO  y(VLi)  >= y(VLi+1) I AKO x1<D
                    ONDA   D=x1
        KRAJ UNUTRAŠNJE PETLJE
        AKO L<D ONDA NACRTATI  LINIJU  OD TOČKE (L, y0) DO TOČKE (D, y0)
    KRAJ VANJSKE PETLJE
KRAJ


Opis postupka V31:
SKUP x KOORDINATA SJECIŠTA JE PRAZAN SKUP
ZA i=0 n-1 RADITI
    RAČUNAMO SJECIŠTE i-TOG BRIDA I PRAVCA Z
        x3= b(bi) c(Z) - c(bi) b(Z)
        y3= -a(bi) c(Z) + c(bi) a(Z)
        w3= a(bi) b(Z) - b(bi) a(Z)
    AKO JE w3=0 ONDA
        BRID b i PRAVAC Z SU PARALELNI  TE TREBA NASTAVITI TRAŽITI DALJE PO BRIDOVIMA
    PRETVORIMO KOORDINATE U NEHOMOGENE   x3 = x3 / w3  i  y3 = y3 / w3
    AKO x3<x0 ONDA
        SJECIŠTE JE S LIJEVE STRANE TOČKE TE TREBA NASTAVITI TRAŽITI DALJE PO
        BRIDOVIMA
    POSTAVITI
    x1=x(VLi)
    y1=y(VLi)
    x2=x(VLi+1)
    y2=y(VLi+1)
    AKO SJECIŠTE NIJE NA BRIDU TJ. :
        (y3>=y1 I y3>y2) ILI (y3<=y1 I y3<y2) NASTAVITI TRAŽITI DALJE PO BRIDOVIMA
    AKO JE SJECIŠTE U VRHU (x2,y2) ONDA
        Ako su susjedni bridovi sa suprotnih strana ispitne linije sjeciste je "pravo"
        POSTAVI x2=x(VLi+2) i y2=y(VLi+2)
         RAČUNATI
        d1=a(Z) x1 + b(Z) y1 + c(Z)
        d2=a(Z) x2 + b(Z) y2 + c(Z)
        AKO TOCKA x2 LEŽI NA ZRACI Z ONDA
            POSTAVI x3=x2; y3=y2;
            POSTAVI x2=x(VLi+3) i y2=y(VLi+3)
             RAČUNATI
                d2=Z.getA()*x2 + Z.getB()*y2 + Z.getC();
        KRAJ
    AKO (d1>0 I d2>0) ILI (d1<0 I d2<0) ONDA
        NASTAVITI TRAŽITI DALJE PO BRIDOVIMA
    U SKUP SKUP x KOORDINATA SJECIŠTA S DODATI x3
KRAJ PETLJE
VRATI S

Demonstracija:




Napisao Andro Galinović