Vprašanja ki si jih zastavimo ko se spopadamo s svojo nalogo:

• Kako določiti ali je točka v notranjosti konveksnem mnogokotnika, ter ob enem izračunati še njegovo ploščino?
• Kako izrisati poligon?
• Kakšna je osnovna ideja algoritma?
• Kako jo implementiramo v Matlabu?
• Kakšne so omejitve in možno izboljšave?

(opomba,konveksni poligon ima vse notranje kote manjše od oz. tak, čigar diagonale nikoli ne sekajo stranic)

Nalogo lahko ločimo v tri dele (pri predpostavki da so vsi vhodni podatki podani v pravilni obliki):

• Izračun ploščine poligona
• Ugotavljanje ali je podana točka v poligonu
• Izris postavitve

Želimo si, da bi lahko vse tri točke izvedli kar najpreprosteje in z čim manj ponavljanja korakov.

• Ogljišči vsake stranice mnogkotnika povežemo z podano točko in tako generiramo n trikotnikov, kjer je n število stranic mnogokotnika

• Izračunamo orientirano ploščino vsakega posamičnega trikotnika po formuli:
• Seštejemo vsota vseh orientiranih ploščin delnih trikotnikov. Absolutna vrednost te vsote je ploščina poligona.

• Preverimo predznake orinetiranih ploščin trikotnikov, če so:

  • vsi enaki in noben ni 0, potem je točka v poligonu
  • vsi enaki a je kak enak 0, potem je točka na robu
  • različni predznaki, točka je izven poligona
• Način računanja ploščone deluje za poljuben poligon, določanje pozicije točke pa z tem algoritmom deluje le za konveksne poligone.

V začetku preverimo če se podani podatki po obliki skladajo z zahtevami. Če je X res točka podana z dvema kordinatama in če je P res matrika z dvema stolpcema in vsaj tremi vrsticami. Podatke o velikosti tudi shrannimo v primerne spremenljivke. Tu bi lahko dodali še druge preverbe, npr. če so vsi podatki veljavnega numeričnega tipa.

Xv=repmat(X,vel,1); Podatke za X raztegnemo v matriko z enakim številom vrstic kot jih ima matrika P, to storimo tako da v vsako vrstico prekopiramo vrednosti za X.

Pn=P-Xv; Poligon centriramo okoli točke X (oz. točko X prestavimo v (0,0)) z odštevanjem.

Rn=circshift(Pn,1); Vsaki točki v poligonu določimo sosdenjo točko, tako da vse vrstice zamaknemo za eno mesto in zadnjo zamenjamo s prvo.

Rn=Rn*[0 -1; 1 0]; z zvito uporabo matričnega množenja, zamenjamo x in y koordinate zamaknjenih točk in pri tem še originalne y koordinate pomnožimo z -1. S tem imamo vse pripravljano za uporabo enačbe

trikotniki=sum(Pn.*Rn,2); po elementih zmnožimo obe matriki skupaj (trenutna in naslednja točka) ter nato seštejemo rezultata v obeh stolpcih. Po končanem postopku dobimo vektor, katerega elementi so ploščine posamičnih trikotnikov, ki sestavljajo poligon (pomnožene s faktorjem 2).

A= 0.5*abs(sum(trikotniki)); vsota vseh trikotniških ploščin (množenje z 0.5 opravimo naknadno, tako da množimo le eno število namesto celega vektorja) je po naši osnovni enačbi kar ploščina poligona

predznaki=sign(trikotniki); pogledamo še predznake posamičnih trikotnikov.

absvsota=abs(sum(predznaki));

vsotaabs=sum(abs(predznaki));
odg = (absvsota==vsotaabs); primerjamo vsoto absolutnih vrednosti predznakov in absolutno vrednost vsote predznakov, če sta ti dve enaki. so enaki tudi vsi predznaki (ali pozitivni ali negativni).

if(vsotaabs~=vel)
   odg= -odg;
end z to kratko preverbo pa se prepričamo, če je morda točka točno na robu. Po vsem tem imamo v spremenljivki odg vrednost ki je: +1 za točko v poligonu, 0 za točko zunaj in -1 za točko na robu poligona.

Zadnji del kode je namenjen izrisu. clf; izbriše trnutno izrisane stvari, hold on; omogoči da se več stvari izriše ena preko druge, fill(P(:,1),P(:,2),'g'); iziriše podani poligon z zeleno barvo, plot(X(1),X(2),'r*'); nariše še podano točko X z rdečo zvezdico, hold off; pa povrne nastavitve risalnega področja v začetno stanj.

Poleg osnovne implementacije, sem razmislil še o parih drugih možnostih.

• Vektroski produkt

Namesto matričnega in elementarnega množenja, lahko uporabimo tudi vektorsko množenje, vendar moramo pred tem podatke postaviti v tridimenzionalni prostor. To storimo z vrstico Pn=[Pn,zeros(vel,1)]; , ki vekotrju Pn doda še stolpec ničel. Sedaj lahko ploščino trikotnikov direktno izračunamo kot trikotniki=sqrt(sum(abs(cross(Pn,Rn,2)).^2,2)); . Vendar pa ta metoda ne prinese nobene dodatne pedagoške ali izvedbene vrednosti k rešitvi

• Preštevanje presečišč

V Matlabu se da brez prevelikih težav tudi implementirati naprednejšo metdod za določanje točke v poligonu, npr. to

Koda sicer deluje primerljivo hitro kot primer ostali metodi, ter deluje tudi za konkavne in celo samo presekajoče poligone (v tem primeru vrne vrednost večjo od 1). Vendar pa je pedagoško težko razložljiva in tudi ne izkoristi dejstva da smo že izračunali predznake trikotnikov. V splošnem pa je zaradi svojega razširjenega področja uporabnosti verjetno bolj primerna.

• Vgrajeni metodi

Za konec velja morda omeniti še rahlo strojniški prstop z uporabo vgrajenih funkcij. Matlab pozna funkciji polyarea in inpolygon , ki opravita natačno zahtevano nalogo. Vendar poleg tega, da ti funkciji nimata nobene pedagoške vrednosti, tudi tečeta zelo počasi. Uporabni sta kvečemu zaradi svoje priročnosti.

Hitrost izvajanja posamezne metode v sekundah