V tem gradivu vam bom predstavil nekaj o daljicah in premicah. Cilj zastavljene naloge je sicer napisati program, ki nam vrne verjetnost, da se dve naključno generirani daljici sekata, vendar pa pri tem ne moremo mimo premic in določanja presečišča med njimi.

Na tem mestu še poudarim, da je v splošnem vseeno, kakšno območje vzamemo za dovoljeno, saj je verjetnost, da bomo izbrali točko na levi polovici kvadrata 1X1 enaka verjetnosti, da bomo izbrali točko na levi polovici kvadrata 1000000X1000000. Določeno velikost je potrebno izbrati zgolj zaradi zapisa števil v pomnilniku računalnika. Zaradi tega sem izbral območje [-1000,1000]x[-1000,1000].

Daljico moramo nekako predstaviti, in najbolj očitna izbira je z začetno in končno točko. Lahko bi tudi naprimer podali začetno točko, dolžino daljice in pa kot, vendar je uporabniku prvi način gotovo bolj razumljiv.

To sedaj pomeni, da moramo samo še generirati 4 naključne točke, po dve za vsako daljico. Teoretično bi se lahko zgodilo, da za isto daljico vzamemo isti točki, vendar je možnost tako zelo majhna, da jo zanemarimo. Zato niti nisem vključil kakšnega varovalnega bloka za tak primer. Dve isti točki bi lahko vpisal tudi uporabnik, vendar bi moral za to spremeniti kodo, da bi omogočala vnos podatkov, ali pa v sami kodi določiti točke. Sam program je simulacija, zato sem precej prepričan, da do takega primera ne bo prišlo.

Sedaj, ko vemo, kako bomo predstavili naše daljice, pa nas zanima glavni problem; kako določiti morebitno presečišče.

Najlažje bo, če najprej določimo premici, na katerih ležita daljici, in nato iščemo presečišče teh. Premici (v našem primeru v ravnini) podamo z enačbo y=kx+n. Pri tem k predstavlja naklon premice, n pa začetno vrednost (za koliko je premica premaknjena v y smeri). Koeficient naklona izračunamo z dvema točkama iz enačbe k=(y2-y1)/(x2-x1), pri čemer primer, ko je x2 enak x1, obravnavamo posebej (v tem primeru je koeficient premice neskončen). Začetno vrednost dobimo, če v prvo enačbo vstavimo konkretno točko, ki je ena od podanih. Za program moramo dobljene rezultate na nek način predstaviti.

Za začetno vrednost je očitno, da bo lahko tipa double, pri koeficientu pa bi lahko imeli problem. Lahko sicer spet rečemo, da je praktično nemogoče, da dobimo za obe točki daljice isto x koordinato. lahko pa se odločimo, da bomo koeficient predstavili kot niz. Niz bo v primeru, da je koeficient neskončno, enak "INF", sicer pa bo kar vrednost (double), pretvorjena v niz. Tako lahko preverimo: če sta koeficienta obeh premic enaka, vrnemo false (premici sta vzporedni, torej nimata presečišč). V nasprotnem primeru določimo presečišče.

Posebej obravnavamo primer, ko ima ena od premic koeficient naklona enak neskončno. Če ga imata obe, smo že prej določili, da se ne sekata. V nasprotnem primeru pa presečišče dobimo tako, da v enačbo druge premice vstavimo x koordinato ene izmed točk daljice z naklonom neskončno. Tako dobimo še koordinato y presečišča.

Če nobeden od koeficientov ni enak neskončnosti, imamo dve enačbi premice, y=k1*x+n1 in y=k2*x+n2. Iz tega lahko najprej določimo vrednost x:

k1*x+n1=k2*x+n2

x=(n2-n1)/(k1-k2)

Sedaj vrednost x vstavimo v eno od obeh enačb in dobimo še koordinato y. Tako dobimo presečišče premic, na katerih ležita daljici.

Seveda še ni nujno, da se sekata tudi daljici sami, zatao moramo najprej preveriti še, če točka leži an obeh daljicah.

Za to bo dovolj, če preverimo, da x koordinata leži med x koordinatami vsake daljice in y koordinata leži med y koordinatama vsake daljice. Če to drži, točka namreč gotovo leži na vsaki od daljic. Ko to preverimo, in če dobimo pritrdilen rezultat, lahkorečemo, da se daljici sekata. Celotna koda za presečišče dveh daljic, podanih s tabelo [x0,y0,x1,y1,x2,y2,x3,y3] v jeziku C#, se nahaja na naslednji prosojnici.

Presek dveh daljic v C#:

Sedaj, ko imamo metodo, ki nam preveri, če se dani daljici sekata, pa bi radi še določili približno verjetnost, da se dve naključni daljici sekata.

Za to izvedemo 10000 preverjanj s po dvema naključnima daljicama v kvadratu 2000X2000, v 10 sklopih po 1000. Preštejemo število presečišč za vsak sklop, in ga delimo s 1000. Te rezultate si shranjujemo v neko tabelo/seznam. Končen rezultat je nato vsota elementov te tabele, deljena z 10. Izračunamo lahko tudi standardni odklon rezultatov, in sicer s formulo s=sqrt(((p-x1)^2+(p-x2)^2+...+(p-xn)^2)/n), pri čemer je p povprečna vrednost, xn je vsaka izmed vmesnih vrednosti, n pa število vmesnih vrednosti (v našem primeru 10).

Sam sem za povprečje večinoma dobival vrednosti med 0.17 in 0.18, za standardni odklon pa 0.01 do 0.04.

Za kvadriranje in korenjenje pri standardnem odklonu sem uporabil knjižnico Math (Math.Pow in Math.Sqrt za kvadriranje in korenjenje).

Najprej sem še napisal metodo Meritev, ki nam izračuna verjetnost preseka za 1000 naključnih daljic, da je metoda main bolj pregledna.

Metoda main nato vsebuje še izračun povprečja vseh verjetnosti in pa izračun standardnega odklona.