Muzafer H. Snrncrvvc METOPE ZM RESMVMZVE PRONLEMM TRUMZSULMOUVE POLUSOZM U ZVUTOVM UMPLEMEZTMOUVM - Doktorska disertacija - Mentor: Pror: pr Prqprms S: Stnnvmvrovvc Zus, 20=3: Imvm poszwnu )xvst i zvyovoljstvo yv sz zvhvvlim mzntoru yr erzyrvgu htvnimirovi(xuA rzyovnom profzsoru eriroynoBmvtzmvti)xkog fvkultztv u ci)suA nv nzszwi)xnoj pomo(xi i wrojnim korisnim svvztimv kojimv jz yoprinzo woljzm kvvlitztu ovz yiszrtvxijzC kzliku zvhvvlnost yugujzm kolzgi hzvyu bv)sovi(xu nv iskrznoj poyr)sxiA yowrim iyzjvmv i svvztimvC ovhvvljujzm sz svim profzsorimv eb[Bv nv korzktnoj svrvynji u toku yoktorskih stuyijv v poszwno yr erzyrvgu Krtolixi i yr bilvnu ivsi(xu nv izrvyi zvjzyni)xkih nvu)xnih rvyovvC ovhvvljujzm sz yr Dvnijzli bilo)szvi(xA vvnrzynom profzsoru [vkultztv tzhni)xkih nvukv u )Xv)xku jnivzrzitztv u KrvgujzvxuA nv nzszwi)xnoj pomo(xi u toku mvstzr i yoktorskih stuyijvC ovhvvljujzm sz yr Donvlyu izjloruA vvnrzynom profzsoru [vkultztv zv mvtzmvtiku i stvtistiku jnivzrzitztv u hiynzjuA nv stru)xnim svvztimv koji sz oynosz nv progrvmirvnjz i implzmzntvxijz mztoyvC Iskrznu zvhvvlnost izrv)zvvvm kolzgvmv i profzsorimv Dzpvrtmvnv zv tzhni)xkz nvukz jnivzrzitztv u covom evzvruC eoszwno sz zvhvvljujzm )xlvnovimv mojz poroyixz nv poyr)sxiA rvzumzvvnju i ohrvwrznjimvA koji su wili glvvni rvzlog mog istrvjvnjv u rvyuC i gudr(zuj dredgovor vi E ivodnu ruzmutrunju E 1.1 Pojam Katalanovih brojeva . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.2 Pojam triangulacije poligona . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.3 Jedan algoritam za triangulaciju konveksnih poligona . . . . . . . . . . . . . 6 F Implementuciju ulgoritumu ru(cunurske geometrije u Jmvu M 2.1 Prednosti objektno-orijentisanog programiranja i modeliranja . . . . . . . . . 9 2.2 Jvvv biblioteke za GUI i racˇunarsku geometriju . . . . . . . . . . . . . . . . 11 2.2.1 Vli i hfiing paketi . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.2.2 Otvorena biblioteka Jvvv dpznGa . . . . . . . . . . . . . . . . . . . . 12 2.2.3 Klase i paketi za triangulaciju poligona . . . . . . . . . . . . . . . . . 12 2.3 Prednosti Jvvz u implementaciji algoritma za triangulaciju konveksnog poligona 14 2.3.1 Implementacija ]urtvyoBcoy algoritma . . . . . . . . . . . . . . . . . 15 2.3.2 Komparativna analiza implementacija (JvvvA X++A eython) . . . . . 19 G aetode zu generisunje triunguluciju konveksnih poligonu FF 3.1 Metod dekompozicije Katalanovih brojeva . . . . . . . . . . . . . . . . . . . 22 3.1.1 Tezˇinsko stablo triangulacija i dekompozicija Katalanovog broja . . . 23 3.1.2 Triangulacija konveksnog poligona bazirana na dekompoziciji Kata- lanovog broja . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 3.1.3 Kompleksnost algoritma . . . . . . . . . . . . . . . . . . . . . . . . . 32 3.1.4 Komparativna analiza i eksperimentalni rezultati . . . . . . . . . . . 33 3.1.5 Detalji implementacije u Jvvi . . . . . . . . . . . . . . . . . . . . . . 35 3.2 Blok metod za generisanje triangulacija poligona . . . . . . . . . . . . . . . . 37 3.2.1 Uvodne napomene i osnovne postavke . . . . . . . . . . . . . . . . . . 37 3.2.2 Algoritam za blok metod . . . . . . . . . . . . . . . . . . . . . . . . . 38 3.2.3 Komparativna analiza i eksperimentalni rezultati . . . . . . . . . . . 42 3.2.4 Detalji implementacije i rad sa bazama podataka u Jvvi . . . . . . . 44 iv SADRZˇAJ H aetode zu notuciju i skludi(stenje triunguluciju poligonu HL 4.1 Ballot notacija za triangulaciju poligona . . . . . . . . . . . . . . . . . . . . 48 4.1.1 Uvodne napomene i osnovne postavke . . . . . . . . . . . . . . . . . . 48 4.1.2 Ballot problem i triangulacija poligona . . . . . . . . . . . . . . . . . 50 4.1.3 Primena steka za skladiˇstenje triangulacija . . . . . . . . . . . . . . . 54 4.1.4 Komparativna analiza i eksperimentalni rezultati . . . . . . . . . . . 56 4.1.5 Detalji implementacije u Jvvi . . . . . . . . . . . . . . . . . . . . . . 59 4.2 Alfanumericˇka notacija . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 4.2.1 Uvodne napomene i osnovne postavke . . . . . . . . . . . . . . . . . . 62 4.2.2 Transformacija iz BP u AN zapis . . . . . . . . . . . . . . . . . . . . 63 4.2.3 Obrnuta transformacija iz AN u BP zapis . . . . . . . . . . . . . . . 67 4.2.4 Eksperimentalni rezultati . . . . . . . . . . . . . . . . . . . . . . . . . 68 4.2.5 Detalji implementacije u Jvvi . . . . . . . . . . . . . . . . . . . . . . 70 I drimenu ovjektnoAorijentisune unulize i dizujnu nu provlem triungulucije poligonu KG 5.1 Direktna analiza za algoritam triangulacije poligona ([orfivry znginzzring) . 74 5.1.1 Modeliranje u jbaBu: staticˇni, dinamicˇki i fizicˇki model . . . . . . . 75 5.1.2 Generisanje Jvvv izvornog koda iz jba modela . . . . . . . . . . . . 81 5.2 Povratna analiza i sinhronizacija (gzvzrszDgounyBtrip znginzzring) . . . . . 82 5.2.1 Dobijeni rezultati u unapred¯enju implementacija . . . . . . . . . . . . 84 J nuklju(cnu ruzmutrunju LK drilozi ME I) Podaci o preuzimanju izvesˇtaja za klase i implementacije metoda . . . . . . . . 91 II) Jvvv izvorni koˆd . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93 A) Klasa: irivngulvtion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93 B) Klasa: Gznzrvtzirivngulvtions . . . . . . . . . . . . . . . . . . . . . . . . 94 C) Klasa: cotzirivngulvtion . . . . . . . . . . . . . . . . . . . . . . . . . . . 95 D) Klase: coyzA azvfcoyzA eoint . . . . . . . . . . . . . . . . . . . . . . . . 97 E) Klasa: Dvtvwvsz . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98 F) Klasa za kreiranje izlazne datoteke . . . . . . . . . . . . . . . . . . . . . . 99 gpisuk ulgoritumu, tuvelu i sliku EDD Literuturu EDG Viogru ju uutoru EED v dredgovor Tema doktorske disertacije pripada oblasti algoritama racˇunarske geometrije u kombinaciji sa objektno-orijentisanim programiranjem i modeliranjem. Po bhXGEFE klasifikuje se u KMjEJO =xomputzr grvphixsP xomputvtionvl gzomztry)A KJDFMO =xomputzr grvphixsA imvgz vnvlysisA vny xomputvtionvl gzomztry), kao i KMcFJO =progrvmming lvnguvgzs). U disertaciji su predstavljene nove metode za generisanje i notaciju triangulacija poli- gona. Sve metode su implementirane u programskom jeziku Jvvv, koji je u poslednjih neko- liko godina najaktuelniji objektno-orijentisani programski jezik. Pored toga, u disertaciji je razmatran i novi pristup analizi i resˇavanju problema triangulacije poligona primenom metodologije objektno-orijentisane analize i dizajna. Disertacija je podeljena u sˇest poglavlja. Sledi kratak opis svakog poglavlja. 1. drvo pogluvlje sadrzˇi osnovne podatke o metodolosˇkom okviru istrazˇivanja (pro- blemu, predmetu, ciljevima i tehnikama istrazˇivanja). Zatim, dat je osvrt na po- jam Katalanovih brojeva i pojam triangulacije konveksnih poligona. Analiziran je jedan postojec´i algoritam za konstrukciju triangulacija poligona (]urtvyoBcoy) koji je posluzˇio za komparativnu analizu sa novim metodama koje predstavljaju rezultat ove disertacije. 2. i drugom pogluvlju su navedene prednosti objektno-orijentisanog programiranja i modeliranja kroz primenjene jezike Jvvv i jba. Izucˇavane su moguc´nosti program- skog jezika Jvvv u implementaciji algoritama racˇunarske geometrije, kroz primenu postojec´ih biblioteka i programskih interfejsa (Jvvv GDA HDA dpzn GaA GzomztryInfoA irivngulvtor). Analizirani su postojec´i Jvvv paketi koji su koriˇsc´eni za implementaciju novih metoda za triangulaciju poligona. Razvijene Jvvv aplikacije za implementaciju metoda uvedenih u disertaciji karakteriˇse graficˇki korisnicˇki interfejs (GUI), a to je postignuto koriˇsc´enjem Jvvv klasa iz Vli i hfiing paketa. Urad¯ena je uporedna analiza implementacija u programskim jezicima JvvvA eython i X++ za ]urtvyoBcoy algoritam, gde su analizirane moguc´nosti navedenih jezika u implementaciji algoritama racˇunarske geometrije. Objavljeni naucˇni radovi autora disertacije na kojima se bazira drugo poglavlje su [53, 54, 48]. vi 3. hrece pogluvlje sadrzˇi nove metode za generisanje triangulacija konveksnog poli- gona. Prva tehnika generisanja triangulacija se bazira na dekompoziciji Katalanovog broja u formi suma termova (2+ i). Dobijeni izrazi dekompozicije predstavljaju kljucˇ u postupku generisanja skupa triangulacija Tn na osnovu skupa Tn−1. Na osnovu ove ideje je uspostavljeno tezˇinsko stablo triangulacija. Druga tehnika generisanja triangulacija je nazvana wlok mztoyv. Ova metoda se zasniva na odnosu broja triangulacija dva uzastopna poligona, koji je izrazˇen kao in = 2in−1 + rzstgn. Generalna strategija primene ove metode je da se glavni pro- blem razlazˇe na manje potprobleme koji su med¯usobno zavisni. U cilju izbegavanja ponavljanja generisanja prethodnih triangulacija iz skupa Tn−1 koriˇsc´ena je rekurzija sa memoizacijom. U ovoj metodi je stavljen akcenat na moguc´nosti rada sa bazama podataka u Jvvv cztWzvns okruzˇenju (JDWX ). Za obe nove metode urad¯ena je kom- parativna analiza sa ]urtvyoBcoy algoritmom, gde je ukazano na prednosti novih predlozˇenih metoda. Za potrebe dobijanja eksperimentalnih rezultata za svaku od pomenutih metoda je isprogramirana posebna Jvvv aplikacija. Objavljeni naucˇni radovi autora na kojima se bazira trec´e poglavlje su [65, 67]. 4. (Cetvrto pogluvlje obrad¯uje triangulacije sa aspekta zapisivanja (pridruzˇivanja odgo- varajuc´e notacije triangulacijama) i njihovog skladiˇstenja. Date su nove metode sa ciljem usˇtede memorijskog prostora. Napravljena je veza izmed¯u problema triangu- lacije poligona i kombinatornih problema kao sˇto su wvllot problem i problem puteva u mrezˇi (lvttixz pvth). Prva tehnika zapisivanja je nazvana wvllot notvxijv, i nju cˇine dva inverzna algoritma (iz wvllot zapisa u graficˇki prikaz triangulacije i obrnuto). Navedena je moguc´nost primene steka u obradi wvllot zapisa, a sve u cilju dobijanja boljih rezultata kada su u pitanju dva vazˇna resursa: vreme i memorija. Rezultati implementiranih metoda ukazuju na poboljˇsanje u konstrukciji i notaciji triangulacija u odnosu na postojec´i algoritam. Druga metoda, predstavljena u ovom poglavlju, nazvana je vlfvnumzri)xkv notvxijv =Vc). Napravljena je komparativna analiza sa postojec´om notacijom koja je bazi- rana na upvrznim zvgrvyvmv =We B wvlvnxzy pvrznthzszs). Data su dva algoritma koja realizuju dve transformacije (iz BP zapisa u AN i obrnuto). Dobijeni eksperi- mentalni rezultati pokazuju znatnu usˇtedu memorije primenom AN metode u procesu skladiˇstenja. Naucˇni radovi autora na kojima se bazira cˇetvrto poglavlje su [49, 55]. 5. deto pogluvlje se odnosi na objektno-orijentisanu analizu i dizajn algoritama za tri- angulaciju poligona. Problem triangulacije poligona je analiziran sa tri aspekta: pri- stupa direktnog razvoja (forfivry znginzzring), sa aspekta povratne analize (rzvzrsz znginzzring) i sinhronizacije oba pristupa (rounyBtrip znginzzring). Prvi pristup je re- alizovan jba tehnikom kroz staticˇke, dinamicˇke i fizicˇke modele. Date su moguc´nosti vii generisanja Jvvv izvornog koda na osnovu razvijenih jbamodela. U drugom pristupu analize problema stavljen je akcenat na obrnuti (reverzni) inzˇenjering koji se odnosi na tumacˇenje i vizuelizaciju izvornog koda primenom naprednih razvojnih okruzˇenja (kisuvl evrvyigm for jbaA cztWzvnsjba). Trec´i pristup se odnosi na sinhronizaciju Jvvv izvornog koda i jba modela. Peto poglavlje se bazira na objavljenim naucˇni radovima [56, 66]. Pored navedenih radova koji se u potpunosti ukljucˇuju, neki delovi i rezultati iz radova [57, 69] se delimicˇno navode u ovoj disertaciji. 6. U poslednjem poglavlju su data zakljucˇna razmatranja i kratak pregled rezultata izlozˇenih poglavlja, kao i buduc´i pravci istrazˇivanja. Prakticˇni deo ove disertacije se sastoji od osam aplikacija: sˇest u Jvvi, jedna u eython- u i jedna u X++-u. Razvijen je autorski set aplikacija za resˇavanje problema trian- gulacije poligona preko novih metoda za generisanje, zapisivanje i skladiˇstenje. Neki kljucˇni delovi izvornih kodova ovih aplikacija su dati u prilogu disertacije, a kompletne aplikacije u vidu izvrsˇnih programa se mogu preuzeti sa web adrese: httpODDmuzvfzrsCuninpCzyuCrsDtrivngulvxijvChtml Na kraju disertacije su navedeni spiskovi svih algoritama, tabela i slika. viii dogluvlje E ivodnu ruzmutrunju Racˇunarska geometrija je sastavni deo matematike i bavi se algoritamskim resˇavanjem geo- metrijskih problema. Ova oblast se smatra i granom racˇunarskih nauka. Nastala je u ranim sedamdesetim godinama prosˇlog veka kao rezultat resˇavanja geometrijskih problema pomoc´u racˇunara. Od samog pocˇetka, racˇunarska geometrija je povezivala razlicˇite oblasti nauke i tehnike, kao sˇto su teorija algoritama, kombinatorna i Euklidova geometrija, ali je ukljucˇivala i strukture podataka i optimizaciju. Danas, racˇunarska geometrija ima veliku primenu u racˇunarskoj grafici, vizuelizaciji, 3D modelovanju itd. Geometrija zauzima vazˇnu ulogu u oblasti racˇunarske grafike. Mozˇe se rec´i da se racˇunarska grafika razvila do ogromnog stepena zahvaljujuc´i njoj. Racˇunarska grafika se mozˇe smatrati granicˇnom oblasˇc´u racˇunarstva i geometrije. Ona se bavi vernim prikazi- vanjem geometrijskih objekata, uzimajuc´i u obzir ogranicˇenja izlaznih ured¯aja racˇunara. Nezamislivo je danas baviti se grafikom bez geometrije. U pozadini nekog prikaza (slike, ani- macije) kriju se slozˇeni proracˇuni i teorije iz oblasti geometrije koje su vec´ odavno potvrd¯ene i razvijene, ali koje su sa aspekta primene u savremenim informacionim tehnologijama josˇ na pocˇetku. Jedan od vazˇnijih problema racˇunarske geometrije je triangulacija poligona. Primenjuje se u postupku dobijanja trodimenzionalnih prikaza objekata iz skupa tacˇaka. Jedan od problema izucˇavanja u ovom postupku je brzina pronalazˇenja triangulacija poligona u svim moguc´im varijantama, jer se sa povec´anjem broja temena poligona drasticˇno povec´ava i broj razlicˇitih triangulacija. Pored toga, sa aspekta skladiˇstenja, potrebno je obezbediti jedin- stven sistem zapisivanja svih triangulacija koji omoguc´ava usˇtedu memorijskog prostora. Predmet istrazˇivanja u ovoj disertaciji je analiza i testiranje metoda za resˇavanje pro- blema triangulacije konveksnog poligona, sa aspekta konstrukcije (generisanja u graficˇkom obliku) i skladiˇstenja (predstavljanja u obliku zapisa odnosno odred¯ene notacije). Ova doktorska disertacija daje nove metode i tehnike u resˇavanju problema triangulacije poligona, koje su implementirane primenom aktuelnih razvojnih okruzˇenja i programskih jezika koji su danas najkoriˇsc´eniji u svetu. O aktuelnosti oblasti koja je obrad¯ena u ovoj disertaciji govori veliki broj naucˇnih i strucˇnih radova koji su prezentovani na med¯unarodnim 1 jvoynv rvzmvtrvnjv i domac´im konferencijama i objavljeni u naucˇnim cˇasopisima. U disertaciji su analizirani postojec´i algoritmi iz oblasti racˇunarske geometrije [9, 10, 23, 29, 30] ali su predstavljene i nove metode i algoritmi za generisanje triangulacija konveksnog poligona [65, 67] i nove metode za notaciju triangulacija poligona [49, 55]. Tema disertacije je multidisciplinarna jer doticˇe oblasti racˇunarske grafike, geometrije, programiranja i objektno-orijentisane analize i dizajna (OOAD) algoritama. Cilj je da se na osnovu teorijskih razmatranja novih metoda i njihove prakticˇne primene ukazˇe na znacˇajne moguc´nosti unapred¯enja postojec´eg stanja iz ove oblasti, primenom objektno-orijentisanog programiranja i modeliranja. Napredna razvojna okruzˇenja koja se primenjuju u implementacijama (Jvvv cztWzvns IDZA ke for jba) predstavljaju alate koji omoguc´avaju realizaciju metoda u cilju dobi- janja njihovih eksperimentalnih rezultata. Jvvv predstavlja kombinaciju najboljih eleme- nata uspesˇnih programskih jezika koji su joj prethodili, kombinovanih s novim konceptima u cilju postizanja efikasnijeg programiranja. Pored programiranja u Jvvi, problem triangu- lacije je u ovoj disertaciji povezan sa modernom tehnologijom objektno-orijentisanog soft- verskog inzˇenjerstva, na nivou na kome se ona u svetu primenjuje u poslednjih nekoliko godina. Na osnovu postavljenih ciljeva, definisani su sledec´i zadaci istrazˇivanja: 1. Najpre je potrebno utvrditi kakve su moguc´nosti Jvvz (kao alata koji c´emo koristiti u implementaciji metoda) kada je u pitanju posedovanje gotovih paketa i klasa za rad sa racˇunarskom geometrijom. Zatim, potrebno je utvrditi koje su prednosti ovog jezika u pored¯enju sa drugim objektno-orijentisanim programskim jezicima sa aspekta brzine generisanja i moguc´nosti efikasnog skladiˇstenja. 2. Napraviti komparativnu analizu datih novih metoda za generisanje sa postojec´im tehnikama i algoritmima, i uporediti dobijene rezultate. Takod¯e, utvrditi procenat usˇtede memorije u primeni novih metoda za notaciju i skladiˇstenje triangulacija u odnosu na druge postojec´e tehnike zapisivanja. 3. Ispitati efekat primene objektno-orijentisane metodologije u analizi dobijenih imple- mentacija i utvrditi prednosti i nedostatke pristupa sinhronizacije direktnog i obrnutog inzˇenjeringa u cilju poboljˇsanja softverskih resˇenja za date nove metode. Da bi se realizovali ciljevi i zadaci istrazˇivanja, koriˇsc´ene su sledec´e naucˇne metode i postupci: - Metodom teorijske analize su ispitivana dosadasˇnja teorijska znanja o problemu trian- gulisanja poligona i analizirani su postojec´i algoritmi i tehnike. - Komparativnom metodom su upored¯ivani rezultati postojec´ih metoda i novih predlozˇe- nih metoda resˇavanja problema. - Eksperimentalnom primenom smo dobili rezultate koji pokazuju efikasnost novih meto- da (u brzini generisanja triangulacija ili usˇtedi memorijskog prostora pri skladiˇstenju). 2 jvoynv rvzmvtrvnjv - Metoda generalizacije je primenjena u analizi odred¯enog broja slucˇajeva a na osnovu matematicˇkih metoda gde se dolazi do uopsˇtene tvrdnje koja vazˇi za sve slucˇajeve. Metodom specijalizacije su predstavljeni odred¯eni slucˇajevi u obliku konkretnog primera koji prati korake algoritma. - Metode dedukcije i indukcije su koriˇsc´ene u toku eksperimentalnog ispitivanja, gde se nakon dobijenih rezultata formirao zakljucˇak o novim tehnikama i o moguc´nostima njihove primene. Disertacija se bazira na autorskim naucˇnim radovima [48, 49, 53, 54, 55, 56, 65, 66, 67] koji su objavljeni (ili su u proceduri) u med¯unarodnim naucˇnim cˇasopisima. Rezultati disertacije se mogu svrstati u tri kategorije. Prvu kategoriju cˇine rezultati koji se odnose na nove metode koje se primenjuju u generisanju triangulacija konveksnog poligona. Drugu kategoriju cˇine rezultati koji se odnose na nove metode za notaciju triangulacija. Trec´u kategoriju cˇine rezultati koji se odnose na novu ddVD metodologiju, gde se primenom naprednih okruzˇenja daje model za analizu i dizajn algoritama u racˇunarskoj geometriji. EBE dojum Kutulunovih vrojevu Katalanovi brojevi (Cn) predstavljaju niz brojeva koji se prvenstveno koriste u geometriji, ali se ovaj niz pojavljuje i kao resˇenje velikog broja kombinatornih problema. Prvi put ih je otkrio Leonard Ojler (azonhvry Zulzr, 1707-1783) trazˇec´i opsˇte resˇenje za broj razlicˇitih nacˇina na koji se jedan mnogougao mozˇe podeliti na trouglove. Pritom je trebalo voditi racˇuna da se ne koriste dijagonale mnogougla koje se med¯usobno seku. Med¯utim, ovi brojevi su ipak dobili ime po belgijskom matematicˇaru Ezˇen Sˇarl Katalanu (Zugznz Xhvrlzs Xvtvlvn, 1814–1894) koji je otkrio vezu izmed¯u ovih brojeva i problema korektnih nizova n parova zagrada. Katalanovi brojevi se izracˇunavaju po sledec´oj formuli [39]: Cn = (2n)! (n+ 1)!n! = 1 n+ 1 ( 2n n ) P n ≥ 0 (1.1) gde vazˇi da je n broj trouglova na koje se mozˇe podeliti dati poligon. Cˇesto se koristi i sledec´i alternativni izraz za definiciju Katalanovih brojeva:( 2n n ) − ( 2n n+ 1 ) = (2n)! (n!)2 − (2n)! (n− 1)!(n+ 1)! = (2n)! n!(n+ 1)! = Cn (1.2) 3 jvoynv rvzmvtrvnjv Katalanovi brojevi se josˇ mogu izraziti i Segnerovom rekurzivnom formulom [40] kao i Bertrandovom wvllot teoremom [22]. Tabela 1.1 sadrzˇi Katalanove brojeve za vrednosti n ∈ {1P 2P :::P 30}, koji se izracˇunavaju po formuli (1.1) ili (1.2). Tabela 1.1: Vrednosti prvih 30 Katalanovih brojeva n Cn n Cn n Cn E 1 EE 58,786 FE 24,466,267,020 F 2 EF 208,012 FF 91,482,563,640 G 5 EG 742,900 FG 343,059,613,650 H 14 EH 2,674,440 FH 1,289,904,147,324 I 42 EI 9,694,845 FI 4,861,946,401,452 J 132 EJ 35,357,670 FJ 18,367,353,072,152 K 429 EK 129,644,790 FK 69,533,550,916,004 L 1,430 EL 477,638,700 FL 263,747,951,750,360 M 4,862 EM 1,767,263,190 FM 1,002,242,216,651,360 ED 16,796 FD 6,564,120,420 GD 3,814,986,502,092,300 Katalanovi brojevi su veoma znacˇajni u kombinatorici, pa se mnogi kombinatorni pro- blemi zasnivaju na tom nizu (kao npr. wvllot problem, problem puteva u mrezˇi, problem uparenih zagrada itd.). U radovima [8, 17, 19, 28, 38, 63] su navedene konkretne primene ovih brojeva u resˇavanju nekih kombinatornih problema i problema u racˇunarskoj geometriji. Knjiga [68] sadrzˇi skup zadataka koji opisuju preko 60 razlicˇitih interpretacija Katalanovih brojeva. Takod¯e, [39] daje osnovna svojstva, kao i konkretne primene i probleme koji se zasnivaju na ovim brojevima. EBF dojum triungulucije poligonu Triangulacija poligona je istorijski veoma star problem koji je doveo do otkric´a Katalanovih brojeva. Pri odred¯ivanju svih triangulacija poligona mora biti razmotren i oblik poligona. Ovo cˇini problem izracˇunavanja veoma tesˇkim. Problem mozˇe biti smanjen tako sˇto se ogranicˇavamo na proracˇune vezane za konveksne poligone. Za konveksne poligone sve di- jagonale su unutrasˇnje dijagonale. U ovom slucˇaju broj triangulacija konveksnog poligona je nezavisan od oblika i mozˇe biti jedinstveno okarakterisan brojem temena n. Pod triangulacijom konveksnog poligona podrazumevamo razlaganje unutrasˇnjosti poli- gona na trouglove, med¯usobno nepresecajuc´im unutrasˇnjim dijagonalama. Kod ovog pro- blema se zapravo razmatra broj triangulacija, gde je moguc´a maksimalna podela konveksnog poligona na n − 2 trougla. U radovima [23, 45, 46] su predstavljeni neki nacˇini resˇavanja ovog problema. 4 jvoynv rvzmvtrvnjv Triangulacija poligona sa n temena zahteva podelu na trouglove sa n − 3 unutrasˇnjih dijagonala koje se ne ukrsˇtaju (Slika 1.1). Slika 1.1: Triangulacija konveksnog poligona za n ∈ {3P :::P 6} Konveksni poligon sa n temena c´emo oznacˇiti sa en. On je opisan nizom temena v1;v2P :::P vn. Unutrasˇnja dijagonala koja povezuje temena vi i vj je oznacˇena sa p;q. Takod¯e, i stranice poligona se smatraju dijagonalama pa tako i;i+1 predstavlja ivicu vivi+1. Skup tri- angulacija poligona en je obelezˇen sa Tn a sa n oznacˇic´emo odred¯enu triangulaciju iz skupa Tn. Koristic´emo oznaku deg(i) za stepen temena i u triangulaciji. Sa ii c´emo oznacˇiti ukupan broj triangulacija u skupu Tn. Sada c´emo uspostaviti relaciju izmed¯u triangulacija poligona i Katalanovih brojeva. Po Ojlerovoj postavci problema triangulacije poligona [39] vazˇi sledec´a jednakost: in = Cn−2P n ≥ 3 (1.3) gde je, u ovom slucˇaju, n broj temena poligona. Na primer, broj triangulacija petougla (i5) odred¯uje vrednost Katalanovog broja C3 = 5, za sˇestougao (i+) vazˇi C4 = 14 itd. (videti Tabelu 1.1). Dakle, vrednost Katalanovog broja Cn−2 odred¯uje broj triangulacija koji odgovara poligo- nu en. Na osnovu formule za dobijanje vrednosti Katalanovih brojeva (1.1) mozˇemo defi- nisati vrednost in, za n ≥ 3: in = 1 n− 1 ( 2n− 4 n− 2 ) = (2n− 4)! (n− 1)!(n− 2)! (1.4) 5 jvoynv rvzmvtrvnjv Sledi da vrednost in+2 mozˇemo izraziti kao: in+2 = 2 n+ 1 ( 2n− 1 n ) = 1 n+ 1 ( 2n n ) = Cn (1.5) sˇto je ekvivalentno sa (1.3). Triangulacija konveksnih poligona je aktuelan problem koji se javlja u dvodimenzio- nalnoj racˇunarskoj geometriji. Tehnika triangulacije u racˇunarskoj geometriji je najcˇesˇc´a metoda panelizacije. Najlaksˇi nacˇin segmentacije i ravnanja dvostruko zakrivljene povrsˇi je putem mrezˇe trouglova. Prednost trougla kao geometrijskog tela je sˇto je povrsˇina izmed¯u tri tacˇke uvek ravna. Prednosti ovakve primene su: mala odstupanja od izvornog oblika, dobra strukturalna svojstva i moguc´nost oblaganja slozˇenih slobodnih formi. Triangulacija poligona nalazi svoju primenu i u geoinformacionim sistemima, kao i u procesu digitalnog modeliranja terena [32]. Triangulacija poligona ima mnogo primena u racˇunarskoj grafici i koristi se u pretpro- cesnoj fazi broja netrivijalnih operacija prostog poligona. Ona omoguc´ava da se iz skupa tacˇaka dobije trodimenzionalni prikaz objekata i omoguc´ava mehanizam za tzv. glv)xvnjz troyimznzionvlnih gurv. Pa tako, triangulacija poligona ima sˇiroku primenu pri modelo- vanju 3D objekata. Ovaj postupak je veoma bitan za brzinu, kvalitet i rezoluciju prikaza objekata. EBG Jedun ulgoritum zu triunguluciju konveksnih poliA gonu Triangulacija poligona spada u grupu poznatih problema koji su karakteristicˇni za tehniku dinamicˇkog programiranja. Ovom tehnikom drasticˇno mozˇemo smanjiti slozˇenost algo- ritma, sa glavnom idejom da izbegnemo izracˇunavanje iste stvari dva puta, pa se ubrzanje racˇunanja postizˇe memorisanjem odred¯enih med¯urezultata. Kasnije se ti isti rezultati ne moraju ponovo izracˇunavati, vec´ se isti samo koriste za nova izracˇunavanja. Dakle, tehnika resˇavanja jednog problema dinamicˇkim programiranjem se svodi na rekurzivno resˇavanje tih nezavisnih potproblema. Algoritam koji su dali autori Hurtado i Noj u [29] (u daljem tekstu ]urtvyoBcoy algori- tam) se zasniva na generisanju triangulacija konveksnog poligona en na osnovu triangulacija poligona en−1. Njihova procedura se sastoji od tzv. ”cepanja” dijagonala poligona (kako unutrasˇnjih dijagonala tako i spoljasˇnjih ivica poligona) sve do najvec´eg oznacˇenog temena (n − 1 za en−1). Ako se izvrsˇi cepanje dijagonala i;n−1P i ∈ {1P 2P : : : P n − 2} u rastuc´em redosledu od i, dobic´emo ured¯ene triangulacije za en. 6 jvoynv rvzmvtrvnjv Postupak ”cepanja” dijagonale poligona je prikazan na Slici 1.2. Slika 1.2: Prostupak ”cepanja” dijagonale i konstrukcija potomka Autori su definisali stablo triangulacija gde su sve triangulacije poligona en iz skupa Tn ured¯ene na n-tom nivou stabla triangulacija. Svaka triangulacija na n-tom nivou ima ”roditelja” u skupu Tn−1 i dva ili viˇse ”potomaka” u skupu Tn+1. Potomci istog roditelja se tretiraju kao ”brac´a” i oni su ured¯eni u odred¯enom redosledu. Na osnovu toga je definisano ured¯enje koje se odnosi na sve triangulacije u skupu Tn. Uzmimo triangulaciju n−1 ∈ Tn−1 zadovoljavajuc´i deg(n− 1) = l za  ln−1. Pret- postavimo da su incidentne dijagonale sa temenom n − 1 sortirane, pocˇevsˇi od 1;n−1, po principu suprotno kretanju kazaljke na satu. Oznacˇimo k-tu dijagonalu u ovom redosledu sa ik;n−1, gde k uzima vrednost iz skupa k ∈ {1P : : : P l}. Sledi da je broj incidentnih dijagonala sa n− 1 koje prethode ik;n−1 jednak k − 1. Potomci za  ln−1 se izvode tako sˇto se ”cepaju” incidentne dijagonale sa temenom n− 1 ik;n−1P k = 1P : : : P lP ik ∈ {1P : : : P n− 2}P 1 = i1 < i2 < · · · < il = n− 2: Ako podelimo dijagonalu ik;n−1 onda dobijamo potomka S ik( ln−1). Tada sledi da su potomci triangulacije  ln−1 Si1( ln−1)P S i2( ln−1)P : : : P S il( ln−1): Cepanje dijagonale ik;n−1 proizvodi potomka S ik( ln−1) sa deg(n) = 2 + k − 1. Slika 1.3: Primer generisanja dva potomka: S1( ln−1) i S n−1( ln−1) 7 jvoynv rvzmvtrvnjv Na Slici 1.4 je prikazana hijerarhija na stablu triangulacija od n = 3 do n = 6. 2 2 2 2 2 2 2 2 2 2 2 2 2 2 44444444444444 3 3 3 3 3 3 3 3 3 3 3 3 3 3 555555555555551 1 1 1 1 1 1 1 1 1 1 1 1 1 66666666666666 2 2 2 2 3333 4 4 4 4 4 32 11111 5 5 5 5 5 2 2 44 1 1 33 21 3 Slika 1.4: ]urtvyoBcoy hijerarhija Sada c´emo definisati algoritam koji realizuje opisanu proceduru iz rada [29], a naveden je u nasˇem radu [67]. Algoritam 1.3.1 na ulazu zahteva prirodan broj n i skup triangulacija iz prethodnog nivoa Tn−1. Svaka triangulacija je opisana kao struktura koja sadrzˇi 2n − 5 parova temena koji predstavljaju dijagonale poligona en−1 (gde se pod dijagonalama podrazumevaju unutrasˇnje dijagonale i spoljasˇnje ivice poligona). Ulgoritum EBGBE ]urtvyoBcoy algoritam iluzN Pozitivni ceo broj n i skup triangulacija Tn−1 poligona en−1. =F Proverava strukturu koja sadrzˇi 2n − 5 parova temena koje odgovaraju odred¯enoj tri- angulaciji n−1, gde se trazˇe parovi (ikP n− 1), ik∈{1P 2P : : : P n−2} (gornja granica za k je izmed¯u 2 i n− 2), tj. dijagonale koje su incidentne sa temenom n− 1. 2F Za svako ik generiˇse potomka S ik(n−1) tako sˇto se vrsˇi transformacija il;n−1 → il;n, il < ikP 0 ≤ l ≤ n− 3, i uvodi novi par temena ik;n i n−1;n. 3F Uzima sledec´i ik, ako postoji, i ide na Korak 2. 4F Nastavlja gore navedenu proceduru za sledec´u triangulaciju poligona en−1 (tj. strukturu sa 2n− 5 parova temena), ako postoji. U suprotnom se zavrsˇava. U narednom poglavlju disertacije su predstavljene implementacije za ]urtvyoBcoy vlB goritvm u tri programska jezika (JvvvA X++ i eython) i urad¯ena je njihova komparativna analiza. 8 dogluvlje F Implementuciju ulgoritumu ru(cunurske geometrije u Jmvu U ovom poglavlju su navedene prednosti objektno-orijentisanog programiranja i modeli- ranja kroz primenjene jezike: Jvvv i jba. Ispitane su moguc´nosti programskog jezika Jvvv za implementaciju algoritama racˇunarske geometrije, kroz primenu postojec´ih biblioteka i programskih interfejsa (Jvvv GDA HDA dpzn GaA GzomztryInfoA irivngulvtor). Analizirani su postojec´i Jvvv paketi koji su koriˇsc´eni za implementaciju novih metoda za triangulaciju poligona. Data je uporedna analiza implementacija u programskim jezicima JvvvA eython i X++ za ]urtvyoBcoy algoritam, gde su analizirane moguc´nosti navedenih jezika u implementaciji algoritama racˇunarske geometrije. Objavljeni naucˇni radovi autora na kojima se bazira ovo poglavlje su [53, 54, 48]. FBE drednosti ovjektnoAorijentisunog progrumirunju i modelirunju Objektno-orijentisano programiranje ukljucˇuje sposobnost jednostavnog koriˇsc´enja delova izvornog koyv u razlicˇitim programima, sˇtedec´i vreme u analizi, dizajnu, razvoju i testiranju. Objektno-orijentisani koncepti pruzˇaju moguc´nost za kreiranje fleksibilnih i modularnih pro- grama, kroz primenu glavnih svojstava i elemenata, kao sˇto su: objekti, klase, nasled¯ivanje, polimorfizam itd. Jvvv je objektno-orijentisani programski jezik koji je razvila kompanija hun bixroB systzms pocˇetkom devedesetih godina. Mnogi koncepti Jvvz su bazirani na jeziku dwzron. Izbacˇen je koncept modula i uveden koncept klasa iz objektno-orijentisane paradigme. Kao i vec´ina objektno-orijentisanih jezika, Jvvv ukljucˇuje biblioteke klasa koje obezbed¯uju rad sa osnovnim tipovima podataka, ulazom i izlazom, osnovnim Internet protokolima, kontrolama za kreiranje korisnicˇkog interfejsa itd. 9 erzynosti owjzktnoBorijzntisvnog progrvmirvnjv i moyzlirvnjv Po statistikama portala iIdWZ erogrvmming Xommunity Inyzx 1 u kategoriji popu- larnosti objektno-orijentisanih programskih jezika u poslednjoj deceniji, prvo mesto zauzima programski jezik Jvvv (Tabela 2.1). Tabela 2.1: Statistika popularnosti programskih jezika (OOP jezici, 2007-2013) cvjektnoAorijentisuni doziciju progrumski jezici JulAEG FDEF FDEE FDDK Juvu E E E E Objektni-C 2 2 5 - C++ 3 3 2 2 C# 5 4 3 5 (Visual) Basic 6 5 6 3 PHP 4 6 4 4 Python 7 7 7 6 Ruby 11 8 9 8 JavaScript 10 9 8 - Delphi/Object Pascal 18 10 10 - Po statistikama istog portala, u kategoriji svih tipova programskih jezika (objektno- orijentisani, proceduralni, funkcionalni i logicˇki) Jvvv se u poslednjih 15 godina opet nalazi na vrhu liste (Tabela 2.2). Tabela 2.2: Statistika popularnosti programskih jezika (svi prog. jezici, 1998-2013) drogrumski doziciju jezici JulAEG FDEF FDEE FDDL EMML C 1 1 2 2 1 Juvu F F E E G Objektni-C 3 3 6 42 - C++ 4 4 3 3 2 C# 6 5 4 7 - Bitna prednost Jvvz se ogleda u nezavisnosti od platforme. To znacˇi da se programi pisani u njoj lako prenose sa jednog racˇunara ili ured¯aja na drugi, bez obzira na razlicˇito radno okruzˇenje. Jedini preduslov je da je na ured¯aju na kome se program izvrsˇava instali- ran interpretator za Jvvu, nazvan Jvvv virtuelna masˇina (JVM - Jvvv kirtuvl bvxhinz). Josˇ jedna prednost ovog programskog jezika je i jednostavnija sintaksa. Jvvv sintaksa se oslanja na programske jezike X i X++, ali ona je daleko jednostavnija od njihove. U Javi nema pokazivacˇa, nizovi su realni objekti, a upravljanje memorijom je automatsko. 1http F ==www:tiobe:com=index:php=content=paperinfo=tpci=index:html 10 Implzmzntvxijv vlgoritvmv rv)xunvrskz gzomztrijz u Javi Bitna karakteristika ovog programskog jezika je i pogodnost za rad u mrezˇnom okruzˇenju. Podrzˇava konkurentno programiranje pomoc´u niti (thrzvys), sˇto znacˇi da Jvvv programi mogu izvrsˇavati viˇse zahteva istovremeno [35, 48]. Da bi implementacije metoda bile kompletne, primenjena je OOAD metodologija (obje- ktno-orijentisana analiza i dizajn). Ova metodologija sluzˇi za specifikaciju, vizuelizaciju, konstrukciju i dokumentaciju razvoja sistema. Koriˇsc´en je jba (jni zy boyzling avnB guvgz), univerzalni jezik namenjen za objektno-orijentisano modeliranje. Prednost jba-a se ogleda u tome sˇto on predstavlja eksplicitnu vezu izmed¯u objektno-orijentisanih koncepata i izvrsˇnog koda. jba standard se primenjuje kod OO pristupa i predvid¯a odgovarajuc´e poglede na sistem (opis sistema sa staticˇkog/strukturnog, dinamicˇkog i fizicˇkog aspekta). Ovaj jezik se koristi za analizu i vizuelizaciju algoritma triangulacije poligona u viˇse dimen- zija i nivoa detalja (navedeno u petom poglavlju disertacije). Ovakav nacˇin analize se mozˇe primeniti na mnoge algoritme i probleme [60, 61, 66]. FBF Jmvm vivlioteke zu GiI i ru(cunursku geometriju Algoritmi racˇunarske geometrije krec´u se od prostih ispitivanja kolinearnosti tacˇaka, njihove med¯usobne pozicije, pa sve do vrlo slozˇenih pronalazˇenja najmanjeg konveksnog omotacˇa skupa tacˇaka, generisanja Voronojevih dijagrama, triangulacija poligona itd. Neki od radova koji se bave algoritmima racˇunarske grafike su [4, 62, 27]. Da bi ti algoritmi radili efikasno, potrebne su pogodne strukture podataka za reprezentaciju tacˇaka, segmenata, skupa tacˇaka i ostalih geometrijskih objekata. FBFBE McT i Swuzs puketi Aplikacije u Jvvi razvijene u okviru disertacije imaju graficˇki korisnicˇki interfejs (GUI) gde su koriˇsc´eni paketi iz Vli i hfiing biblioteke. Osnovni elementi koji su potrebni za kreiranje GUI-ja se nalaze u dva paketa: hata,aur i hatav,qugle. Jvvv programski jezik u svojoj pocˇetnoj verziji je posedovao biblioteku komponenata za izgradnju graficˇkog korisnicˇkog interfejsa (GUI) zvanu Vwstrvxt linyofi ioolkit =Vli). U pitanju je biblioteka koja se zasniva na koriˇsc´enju komponenata korisnicˇkog interfejsa koje su dostupne na platformi na kojoj se program pokrec´e. To znacˇi da je implementacija Vli komponenata razlicˇita za svaki operativni sistem (npr. u Windows distribuciji Jvvv virtuelne masˇine koriste vfitCyll datoteku)[76]. Vazˇan Jvvv paket za rad sa geometrijskim oblicima je ecmk (hata,aur,ecmk,(). On omoguc´ava definisanje i izvod¯enje operacija nad objektima koji se odnose na rad sa dvodi- menzionalnom geometrijom. Paket ecmk iz biblioteke Vli je koriˇsc´en u realizaciji klasa za implementaciju metoda za generisanje triangulacija (predstavljene u trec´em poglavlju di- sertacije). Kao prosˇirena verzija Vli -a, nastala je biblioteka komponenata za GUI nazvana hfiing i to ime se zadrzˇalo i kasnije. Paket ctclr iz hlIcG biblioteke je koriˇsc´en u realizaciji regulisanja akcije koja pokrec´e proceduru generisanja triangulacija (hatav,qugle,ctclr,(). 11 Java wiwliotzkz zv GjI i rv)xunvrsku gzomztriju Vec´ina klasa paketa hatav,qugle koje definiˇsu GUI elemente, tzv. hfiing komponente, obezbed¯uju unapred¯ene alternative za komponente definisane klasama iz hata,aur paketa. hfiing klase su fleksibilnije od odgovarajuc´ih klasa iz paketa Vli posˇto su u potpunosti implementirane u Javi [24]. Prakticˇni deo ove disertacije se sastoji od osam aplikacija: sˇest u Jvvi, jedna u eython-u i jedna u X++Bu. Razvijen je autorski set aplikacija za resˇavanje problema triangulacija preko novih metoda za generisanje ali i zapisivanje i skladiˇstenje istih. Za izradu svih Jvvv aplikacija za realizaciju metoda predstavljenih u ovoj disertaciji koriˇsc´eno je okruzˇenje Jvvv cztWzvns IDZ (Intzgrvtzy Dzvzlopmznt Znvironmznt). Ovo okruzˇenje je pogodno, izmed¯u ostalog, i za implementaciju algoritama racˇunarske geometrije u formi Jvvv vplztv ili aplikacija [59]. U okviru cztWzvns platforme nalaze se komponente za pravljenje GUI- ja. Te komponente su unapred¯ene Jvvv hfiing komponente. Platforma nudi mehanizam za ukljucˇivanje korisnicˇkih modula radi prosˇirivanja funkcionalnosti celokupne platforme [31, 15]. FBFBF ctvorenu vivlioteku Jmvm OpezSL Jvvv otvorena biblioteka za grafiku (JOGL - Jvvv dpzn Grvphixs aiwrvry ili JdpznGa) je biblioteka za rad sa geometrijskim oblicima i sadrzˇi pakete i klase koji su vazˇni za programi- ranje u racˇunarskoj geometriji i grafici. JdpznGa je Jvvv veza za dpznGa HD graficˇki VeI (Vpplixvtion progrvmming intzrfvxz)[16] a podrzˇava i integraciju sa hfiing komponentama. Jvvv 2D sistem podrzˇava dva nezavisna koordinatna prostora i to korisnicˇki prostor za specifikaciju graficˇkih primitiva i prostor za konkretni izlaz. Korisnicˇki prostor se koristi za tumacˇenje koordinata svih primitiva koje do sistema dod¯u putem Jvvv 2D API-ja [36]. Jvvv 3D je VeI vrlo visokog nivoa, namenjen pisanju Jvvv vpplzt-a i aplikacija koje omoguc´avaju rad sa 3D interaktivnim sadrzˇajem. Jvvv HD omoguc´ava potpuno objektno- orijentisan pristup 3D grafici na visokom nivou. Bitno je naglasiti da Jvvv HD nije integrisani deo, vec´ standardno prosˇirenje Jvvv platforme. Paket ecmkcrpw se odnosi na Jvvv 3D API (Naaiaec amk,qsl,h1b,srgjq,ecmkcrpw). Implementacija Jvvv HD verzije 1.6 se sastoji od tri paketa: dpznGa, Dirzxtm i JdpznGa [11, 12, 64]. JdpznGa zadrzˇava fokus na 3D prikaz sa pomoc´nim bibliotekama koje olaksˇavaju kreiranje geometrijskih primitiva. FBFBG Kluse i puketi zu triunguluciju poligonu U ovoj sekciji je ispitano kakve su moguc´nosti Jvvz kada je u pitanju posedovanje gotovih paketa i klasa za rad sa racˇunarskom geometrijom, konkretnije u postupku triangulacije poligona. Dva paketa za ovaj algoritam racˇunarske geometrije iz Jvvv 3D su: amk,qsl,h1b,srgjq,ecmkcrpw (GzomztryInfoA irivngulvtor) i mpe,h1b,ecmk (irivngulvtionjtilisA hziyzlirivngulvtor)C 12 Implzmzntvxijv vlgoritvmv rv)xunvrskz gzomztrijz u Javi Klase EcmkcrpwGldm i Rpgalesjarmp su iz paketa ecmkcrpw. Klasa EcmkcrpwGldm sadrzˇi operacije za rad sa nizovima temena za geometrijske objekte: - TRIANGLE ARRAY uzima skup od tri temena koji formira trougao, - GL TRIANGLES kreira niz trouglova koji formiraju triangulaciju poligona, - POLYGON ARRAY kreira niz temena za nekonveksni i konveksni poligon, - GL POLYGON kreira poligon od datog niza sa ulaza, - QUAD ARRAY uzima skup od cˇetiri temena koji formira cˇetvorougao, - GL QUADS kreira niz kvadrata koji formiraju kvadragulaciju poligona, - TRIANGLE FAN ARRAY daje skup temena triangulacije u obliku lepeze, - GL TRIANGLE FAN kreira triangulaciju od niza trouglova oko zajednicˇkog temena, - TRIANGLE STRIP ARRAY daje skup temena triangulacije u obliku trake, - GL TRIANGLE STRIP kreira triangulaciju od niza vezanih trouglova. Slika 2.1: Neke operacije klase GzomztryInfo Bitno je naglasiti da klasa EcmkcrpwGldm ima moguc´nost da iscrtava samo odred¯en tip triangulacije (na primer, kreiranje triangulacije od niza vezanih trouglova – higIe triangulacija ili kreiranje triangulacije od niza trouglova oko zajednicˇkog temena – [Vc triangulacija). Zato se javila potreba za implementacijom novih tehnika i metoda koje omoguc´avaju efikasno generisanje svih moguc´ih triangulacija nekog konveksnog poligona. Druga klasa iz paketa Ecmkcrpw je Rpgalesjarmp. Ovu klasu poziva EcmkcrpwGldm i nikad se ne koristi posebno. Klasa RpgalesjargmlSrgjq je iz paketa mpe,h1b,ecmk i na- menjena je za rad sa poligonima sa malim brojem temena, jer koristi jednostavniji ali sporiji algoritam. Klasa ScgbcjRpgalesjarmp je iz istog paketa i predstavlja prosˇirenje prethodne klase. Licencirana je na verziji Gcj aGea vGCF. Posˇto klasa RpgalesjargmlSrgjq nije efikasna za poligone sa vec´im brojem temena, ona se koristi u kombinaciji sa klasom za implementaciju tzv. ovjyzlovog algoritma (Raimund Seidel)[51]. 13 erzynosti Jave u implzmzntvxiji vlgoritmv zv trivngulvxiju konvzksnog poligonv Slika 2.2: Sadrzˇaj paketa Ecmk: irivngulvtionjtilis i hziyzlirivngulvtor FBG drednosti Jmve u implementuciji ulgoritmu zu triA unguluciju konveksnog poligonu U prethodnoj sekciji smo predstavili moguc´nosti programskog jezika Jvvv u oblasti racˇunar- ske geometrije, a u ovoj sekciji je ispitano na konkretnom primeru kakav je programski jezik Jvvv u odnosu na svoju konkurenciju. Za potrebe komparativne analize odrad¯ene su tri implementacije ]urtvyoBcoy algoritma: u JvviA X++-u i eython-u [53]. Razlog za biranje druga dva programska jezika je sˇto su i oni, pored Jvvz, dva trenutno aktuelna objektno- orijentisana programska jezika (sˇto se mozˇe videti iz Tabele 2.1). Pre komparativne analize implementacija u navedenim programskim jezicima, ispitano je da li je rad¯eno neko slicˇno istrazˇivanje za ova tri programska jezika, odnosno kakva su iskustva sa pomenutim programskim jezicima u implementaciji nekog srodnog problema u racˇunarskoj geometriji. Na portalu ihz Xomputzr avnguvgz Wznxhmvrks2 postoje testiranja za mnoge pro- gramske jezike u implementaciji jednostavnijih problema u geometriji. Izmed¯u ostalog, navedena je analiza rezultata za Jvvu, eython i X++ za implementaciju algoritma za bi- narna stabla (Winvryirzzs vlgorithm). Izabrana je analiza ovog algoritma zato sˇto je na neki nacˇin srodan sa triangulacijama konveksnog poligona jer i on mozˇe interpretirati Katalanove brojeve [39]. Ispitivanje na ovom portalu je sprovedeno na procesoru Intzl fKKEE quvyBxorz. Kada je recˇ o CPU opterec´enju, na najzahtevnijem slucˇaju za n=20, najviˇse opterec´enje je zabelezˇeno kod eython-u (93% , 92% , 98%, 93%). Navedene vrednosti u zagradama se odnose na cˇetiri jezgra procesora. U slucˇaju kod X++-a opterec´enje je znatno manje (27%, 98%, 25%, 24%), kao i kod Jvvz (55%, 27%, 76%, 57%). Glavni razlog za ovakve rezultate je dinamicˇko alociranje memorije koje je brzˇe kod Jvvz i X++Ba, a i njihov I/O (inputBoutput) je brzˇi u odnosu na eython standardne biblioteke. 2http F ==shootout:alioth:debian:org= 14 Implzmzntvxijv vlgoritvmv rv)xunvrskz gzomztrijz u Javi Na grafikonu (Slika 2.3) su prikazani rezultati testiranja za tri navedena programska jezika. Uzete su prosecˇne vrednosti (u sekundama) za n ∈ {12P 16P 20}. Slika 2.3: Merenje performansi za Winvryirzzs algoritam u JvviA eython-u i X++-u FBGBE Implementuciju Turtmpo9Noy ulgoritmu Programska okruzˇenja koja su koriˇsc´ena za implementaciju ]urtvyoBcoy algoritma su: Jvvv (NetBeans IDE 6.9.1), eython (Wing IDE Professional 4.0.4) i X++ (NetBeans IDE C++ 7.0). Implementacija je odrad¯ena kroz 6 klasa (sa istom strukturom u sva tri jezika). Vazˇniji segmenti ovih klasa su navedeni u prilogu disertacije (Prilog II). Tabela 2.3: Klase za implementaciju ]urtvyoBcoy algoritma KLUgE aEhcDE Triangulation ajcap()* amnwDpmk() Bpau()* BpauAjj() GenerateTriangulations Tcarmp:Lmbc Turtmpo 4 u z t x uy u t 5{ bqotor t I zqw bqotor45 G t : mpp 4zqw bqotor 4 5 5 G t : sqt 4 0 5 : mpp 4zqw XqmrZopq 4 5 5 G r o r 4 u z t zI0G z < x uy u t G z++5{ bqotor x q v q x I zqw bqotor 4 5 G r o r 4 u z t q I 0 G q < t : sqt 4z 5 : s u z q 4 5 G q++5 { Zopq t I 4Zopq 5t : sqt 4z 5 : sqt 4 q 5 G Zopq s I zqw Zopq 4zqw XqmrZopq 4 5 , t : oopy 4 5 5 G x q v q x : mpp 4 s 5 G r o r 4 u z t w I 0 G w t I mpp : Turtmpo 4z−25G Tr umzsu xm t u oz uz s t mzo qTr u mzsu x m t u oz I zqw Tr umzsu xm t u oz 4z , wr u t q r 5 G u z s t mzo qTr u mzsu x m t u oz : PrmwMxx 4 turt 5 G R u x qcr u t q r r s t rqmy I zqw Ru x qcr u t q r 4p+.−poxysozs : ps . 5 G Nur rqrqpcrutqr out I zqw Nur rqrqpcrutqr 4 r s t rqmy 5 G PostSor uptcru tq r wr u t q r I zqw PostSor uptcru tq r 4 out 5 G Kao rezultat, daje se prikaz u ps formatu preko primerka klase NmqrSapgnrUpgrcp. Da bi se triangulacije graficˇki prikazale, u klasi NmqrSapgnrUpgrcp postoji metoda bpauLglc zaduzˇena da u saradnji sa metodom Bpau() prikazˇe sve generisane triangulacije (Prilog II-F). Kod programskog jezika eython, ovaj je postupak urad¯en preko metode qcrMnrgmlNapqcp(). Na Slici 2.4 je dat GUI aplikacije i izlaz za n ∈ {3P 4P 5P 6} po ]urtvyoBcoy hijerarhiji. Slika 2.4: Generisanje triangulacija po ]urtvyoBcoy hijerarhiji za n ∈ {3P :::P 6} 17 erzynosti Jave u implzmzntvxiji vlgoritmv zv trivngulvxiju konvzksnog poligonv Aplikacija sadrzˇi komponente koje omoguc´avaju manipulaciju nad generisanim trian- gulacijama. Na ovaj nacˇin, promenom standardnih parametara, mozˇemo omoguc´iti trian- gulisanje i nepravilnih konveksnih poligona. Sada c´emo navesti neke primere manipulacije u generisanju triangulacija, kroz odgo- varajuc´e izmene parametara: 1. Linija koˆda za iscrtavanje konveksnih poligona: 4 4 m∗w+o5+qpsqs 5∗Ymtt : PU ;4n∗ qpsqs 5 gde se promenljive v i w koriste za formiranje oblika poligona, dok se promenljiva x koristi za rotaciju poligona. U slucˇaju da je v ̸= 1 i w ̸= 1 dobic´emo nepravilne konveksne poligone: 2. Linija koˆda za skaliranje poligona: t t u s : sS uzq : mpp 4x∗Ymtt : s u z 4p 5 5 G t t u s : sOos uzq : mpp 4y∗Ymtt : oos 4p 5 G 5 U slucˇaju kad je x ̸= y, generiˇsu se sledec´i oblici konveksnog poligona: 3. Metoda Bpau() obezbed¯uje eliminaciju spoljasˇnjih ivica poligona a da se pritom generiˇsu samo unutrasˇnje dijagonale. To se postizˇe modifikacijom odgovarajuc´ih vre- dnosti za s i f : r o r 4 u z t u I s G u orqmtqQxpr 4 u z t w 5 ttrows U[Qxoqptuoz { bqotor qxpr I zqw bqotor45 G qxpr : mpp 4zqw bqotor 4 5 5 G qxpr : sqt 4 0 5 : mpp 4zqw XqmrZopq 4 5 5 G Korak 2: k-iteracije r o r 4 u z t zI0G z qxprSuy I zqw bqotor 4 5 G Korak 2.2: kreiranje izraza za naredne nivoe r o r 4 u z t v I 0 G v < qxpr : sqt 4z 5 : s u z q 4 5 G v++5 { Zopq t I 4Zopq 5 qxpr : sqt 4z 5 : sqt 4 v 5 G Zopq s I zqw Zopq 4zqw XqmrZopq 4 5 , t : oopy 4 5 5 G qxprSuy : mpp 4 s 5 G r o r 4 u z t q I 0 G q < t : x q r tNrmzot 4 5 G q++5 { s I t : oopy 4 5 G Zopq r I s G r o r 4 u z t u I0G u Nxoow 4 u z t OmtZuy5 ttrows U[Qxoqptuoz { ;; stqp = bqotor nx I zqw bqotor45 G t t u s : opqzRu x q 4. nmzq ; gT.+4OmtZuy+=5+. NMfMi : vpn . 5 G n x : mpp 4zqw bqotor 4 5 5 G n x : sqt 4 0 5 : mpp 4zqw XqmrZopq 4 5 5 G ;; s tqp 2 u z t x uyI2G x uyIOmtZuyG r o r 4 u z t zI0G z X I zqw bqotor 4 5 G n x : mpp 4X 5 G r o r 4 u z t row I 0 G row < nx : sqt 4z 5 : s u z q 4 5 G row++5 { St r uzs msI.row.+./.+4row+=5G u r 4zIIxuy 5 Systqy : out : p r u z t x z 4. row .+4row+=55 G Zopq t I 4Zopq 5 n x : sqt 4z 5 : sqt 4 row 5 G Zopq s I zqw Zopq 4zqw XqmrZopq 4 5 , t : oopy 4 5 5 G X : mpp 4 s 5 G ;; s tqp 3 44 bztoyz zv gznzrisvnjz trivngulvxijv konvzksnih poligonv u z t rqymuzuzsNrmzotI z−2∗z= G r o r 4 u z t w I 0 G w < t : rqymuzuzsNrmzot 4 5 G w++5 { s I t : oopy 4 5 G Zopq r I s G X : ooztm uz s 4 r 5 G bqotor R I zqw bqotor 4 5 G r : qqum x s 4R5 G ;; s tqp 4 r o r 4 u z t u I0G u < w G u++5{ ;; stqp 4 := s I s : s q tXq r t 4 5 G X : xmstQxqyqzt 4 5 G s : s q tXms t 4zqw Zopq 4zqw XqmrZopq 4 5 , s : s q tXq r t 4 5 5 5 G ;; s tqp 4 :2 X : ooztm uz s 4 r 5 G X : mpp 4 r 5 G } } } rq turz n x : sqt 4OmtZuy5 G } Jvvv izvorni koˆd za metodu amlraglq() koja odgovara Algoritmu 3.2.2: pun x u o u z t ooztm uz s 4 5 { u z t mItt u s : ooztm uz s 45− t t u s : x q r t : ooztm uz s 4 5 G u z t nItt u s : r u s t t : ooztm uz s 45−4 t t u s : ooztm uz s 45− t t u s : x q r t : ooztm uz s 4 5 5 G r o r 4 u I0G u 05{ rqySw I zuySw 1 =0 G zuySw I zuySw ; =0 G } u z t OqztPqoI Uz t qs q r : pm r s q Uz t 4 OqztrmxNuz , 2 5 G OqztrmxPqo I Uz t qs q r : t oS t r u zs 4OqztPqo 5 G Prikazani rezultati u uporednoj analizi su omoguc´eni primenom metode za skladiˇstenje oba tipa zapisa triangulacija u Jvvv aplikaciji. U nastavku sledi deo Jvvv koˆda koji omoguc´ava uporedni pregled izlaznih datoteka za obe notacije, a sve u cilju utvrd¯ivanja procenta usˇtede memorijskog prostora. Juvu primer HBFBEB Dzo glvvnz klvsz LmrcRpgalesjargmlqA koji jz zvyu)zzn zv snimvnjz nvvzyznih notvxijv u yvz izlvznz yvtotzkzA jz yvt u nvstvvkuO r o r 4 u I0G u po uz t s G pun x u o [nvqot p r u vm t q PostSor uptcru tq r wr u t q r G ∗∗∗ 81 eovrvtnv vnvlizv i sinhronizvxijv =Reverse/Round-trip engineering) ;; opq rm t u oz s pun x u o voup Prmw4 5 {∗} pun x u o voup PrmwMxx 4 bqotor t r q q s 5 4 5 {∗} pun x u o voup o x q m r 4 5 {∗} pun x u o voup oopyRroy4 [nvqot u z t m[r r sqt , [nvqot Zopq t 5 {∗} } pun x u o o x m s s SqzqrmtqTr umzsuxmt uoz uypxqyqzts Tr umzsu xm t u oz { ;; opq rm t u oz s pun x u o voup bqotor o r q m t qTr u mzsu x m t u oz s 4 [nvqot u z t x uy u t 5 {∗} pun x u o voup s t m t u o voup ymuz 4 [nvqot S t r uzs mrss g i 5 {∗} } Kompletna struktura izvornog koda (generisana iz jba modela) mozˇe se preuzeti sa: frrn:--ksxadcpq,slgln,cbs,pq-rpgalesjargml-EclcpajSrpsarspcFsprabm,pap IBF dovrutnu unulizu i sinhronizuciju (Reverse/Rouzp9 trup ezsuzeeruzs) U ovoj sekciji, navesˇc´emo analizu sledec´a dva pristupa na konkretnom primeru imple- mentacija za generisanje i notaciju triangulacija. 1. Obrnuti inzˇenjering i vizuelizacija izvornog koda omoguc´avaju bolje razumevanje pro- grama. Glavne prednosti ovog pristupa su: analiza uticaja uvod¯enja odgovarajuc´ih promena u implementaciji, upoznavanje nepoznatog koda, ponovno koriˇsc´enje, inte- gracija odred¯enih modula izvornog koda, odrzˇavanje softvera i sl. Ovaj pristup nalazi mnoge primene u identifikovanju objektno-orijentisanog izvornog koda [5, 72]. Na primeru implementacija za triangulaciju poligona, primenjen je ovaj postupak i to kroz dve faze: (i) Faza rasˇcˇlanjavanja kompletnog izvornog koda u formalne jedinice (klase), gde se najpre dobija staticˇki model (yijvgrvmi slu)xvjzvv kori)s(xznjv i yijvgrvmi klvsv); (ii) Na osnovu modelovanih atributa i operacija, njihovi se opisi dalje razlazˇu na dijagrame koji se odnose na dinamicˇki model (vktivnostiA stvnjvA intzrvkxijzA szkvznxz). 2. gounyBtrip inzˇenjering predstavlja sinhronizaciju direktne i povratne analize, sˇto se pokazalo kao najbolja praksa u testiranju i odrzˇavanju implementacija [6, 42]. Pre- dnosti ovakvog pristupa se ogledaju u direktnoj koordinaciji izmed¯u izvornog koda i odgovarajuc´ih modela. Takod¯e, i ovde se mogu istac´i bitne napredne moguc´nosti. Pre svega, mozˇe se ostvariti manipulisanje nad definisanim modelima ili postic´i odgo- varajuc´e promene u izvornom kodu koje su prouzrokovane modifikacijom odgovarajuc´ih modela. Na ovaj nacˇin se ostvaruje analiza uticaja uvod¯enja odgovarajuc´ih promena u implementaciji. 82 erimznv owjzktnoBorijzntisvnz vnvlizz i yizvjnv nv prowlzm trivngulvxijz poligonv drimer IBFBEB Dvt jz jzyvn primzr sinhronizovvnjv jba moyzlv sv Jvvv klvsvmv Eclc+ parcRpgalesjargmlq i RpgalesjargmlqC cztWzvnsjba moyul u postupku ovvkvz intzB grvxijz prijvvljujz nv stvnyvryni izlvz slzyz(xz poyvtkzO ",,,Glgrgaj pctcpqc cleglccpgle glrm a lcu npmhcar: Bcegl npmacqqgle Pctcpqc Cleglccpgle* Napqgle 34 cjckclrq* Alajwxgle arrpgbsrcq alb mncpargmlq dmp 50 qwkbmjq* Pcqmjtgle 32 arrpgbsrc rwncq* Glrcepargle 50 cjckclrq* Bsgjbgle rfc oscpw aaafc,,,", dvi izlvzni poyvxi pokvzujuO yv jz LG zlzmzntv moyzlv kori)s(xzno zv gznzrisvnjz yvtotzkv sv Jvvv izvornim koyom =sv tv)xnim wrojzm zlzmznvtv i vtriwutv koji su iyznti kovvni i klvsi kovvni)C ivwzlv JCG przystvvljv ispunjznost oyrzy+znih uslovv u ovom proxzsu sinhroB nizvxijzC Tabela 5.2: Zahtevi u rounyBtrip inzˇenjeringu za konkretne klase ovhtzvi irivngulvtion Gznzrvtzirivngulvtions 1 Navigacija na izvorni koˆd + + 2 Generisanje modela zavisnosti + + 3 Generisanje izvornog koda + + 4 Generisanje izvesˇtaja + + 5 Navigacija na elemente + + 6 Refaktorisanje + + 7 Pronalazˇenje i zamene u UML modelu + 8 Primena DP* i model cˇitljivosti koda + 9 Manipulacija sa A, O, I, R* + + * V B VtriwutiA d B dpzrvxijzA I B ImplzmzntvxijzA g B gzlvxijzDkzzzA De B Dizvjn )svwloniC U cztWzvnsjba modulu postoji moguc´nost automatskog identifikovanja izvornog koda samo ako je ispravno uspostavljena sinhronizacija izmed¯u jba i Jvvv cztWzvns projekta (Zahtevi 1,2,3 i 5 iz Tabele 5.2). Na taj nacˇin se smanjuje slozˇenost problema triangulacije, a programiranje i dodavanje novih funkcionalnosti je veoma olaksˇano. Za obrnuti i rounyBtrip inzˇenjering je vazˇno pomenuti moguc´nost generisanja izvesˇtaja modela za sve klase. Izvesˇtaj opisuje sve klase koje su definisane u implementaciji (kroz ana- lizu njihovih atributa, metoda, relacija sa drugim klasama i sl.). Pored analize klasa, izvesˇtaj sadrzˇi i koriˇsc´enje paketa i interfejsa u implementaciji (Zahtev 4). Podaci o preuzimanju ovih izvesˇtaja su dati na kraju disertacije (Prilog I). Glavne kategorije obrnutog inzˇenjeringa su automatsko restrukturiranje i automatska transformacija: (i) Prva kategorija se odnosi na refaktorisanje i remodularizaciju koji se primenjuje u cilju dobijanja boljeg izvornog koda: bolja struktura, modularnost, izbegavanje 83 eovrvtnv vnvlizv i sinhronizvxijv =Reverse/Round-trip engineering) ponovljenih slucˇajeva, izvlacˇenje metoda itd. (Zahtev 6 i 7); (ii) Druga kategorija se odnosi na primenu standarda u kodiranju (programiranju) koji se primenjuje u cilju dobijanja cˇitljivijeg izvornog koda (Zahtev 8). Refaktorisanje menja unutrasˇnju strukturu kako bi se laksˇe razumela i jednostavnije modifikovala implementacija kroz manipulaciju atributima, operacijama i relacijama izmed¯u njih (Zahtev 9). IBFBE Dovijeni rezultuti u unupredenju implementuciju Tabela 5.3 predstavlja rezultate unapred¯enja softverskog resˇenja za metode koje se koriste za generisanje triangulacija. Vrsˇena su ispitivanja i analize izvornog koda primenom sinhro- nizacije Jvvv programiranja i jba modeliranja, a sve sa ciljem da se dobije jednostavniji izvorni koˆd (bez ponovljenih slucˇajeva, sa sˇto vec´om modularizacijom, sa integracijom odred¯enih delova itd.). Zatim, cilj je bio i da se smanji obimnost implementacije i da se uticˇe na funkcionalnost i rad segmenata implementacije posebno. U analizi odnosa ”pre i posle” koriste se tri kriterijuma: broj linija izvornog koda (linz), velicˇina Jvvv datoteke (wytzs) i merenje vremena u sekundama (spzzy). Ova analiza je rad¯ena pojedinacˇno za svaki segment implementacije (za svaku klasu). Podaci dobijeni nakon poboljˇsanja su oznacˇeni sa ’*’. Tabela 5.3: Poboljˇsanje implementacija za generisanje triangulacija Klvsv linz linz* wytzs wytzs* spzzy spzzy* irivngulvtion 79 67 2275 1715 29.12 26.14 Gznzrvtzirivngulvtion 222 195 8544 7194 37.56 34.33 coyz 45 41 745 578 4.51 4.01 azvfcoyz 27 19 342 216 3.21 2.85 eoint 10 9 134 112 1.52 1.51 eosthxriptlritzr 56 55 1830 1791 2.74 2.62 awupzo HGM GLJ EGLKD EEJDJ KLBJJ KEBHJ Ponolvsmzve 415 EGBKG EMBIE EDBDL U procesu analize koda implementacija (xoyz rzvizfi), primenom modula cztWzvnsB 7jnnzxzssvry Xoyz Dztzxtor7, ostvareno je sledec´e poboljˇsanje: nzkori)s(xzn importDuvoz (4:09%)A nzpro)xitvnz lokvlnz vvrijvwlz (3:02%)A nzpro)xitvni pvrvmztri (3:18%)A nzpotrzwnv mztoyv ili konstruktor (4:23%)A nzpro)xitvnz mztoyz =privvtz)A konstruktori ili tipovi (5:87%) i nzpro)xitvni lokvlni ili privvtni )xlvnovi (6:57%)C 84 erimznv owjzktnoBorijzntisvnz vnvlizz i yizvjnv nv prowlzm trivngulvxijz poligonv Sledec´i grafikon (Slika 5.9) prikazuje poboljˇsanje izvornog koda za svaki segment imple- mentacije, za tri postavljena kriterijuma (wroj linijv koyvP vzli)xinv yvtotzkzP wrzinv). Slika 5.9: Poboljˇsanje (u %) primenom sihronizacije direktne i povratne analize Tabela 5.4 sadrzˇi uocˇene prednosti u toku ovih ispitivanja za sva tri pristupa. Tabela 5.4: Prednosti za sva tri tipa inzˇenjeringa Pristup Prednosti Dirzktni Multidimenzionalnost sistema i visok nivo apstrakcije Efikasna transparentnost strukture sistema Identifikovanje funkcionalnih celina Generisanje izvornog koda dwrnuti Analiza i interpretacija implementacije problema Logicˇki dizajn i bolja vidljivost izvornog koda ”Demontazˇa” Java koda Efikasnije odrzˇavanje softverskog resˇenja gounyBtrip Sinhronizovane promene od modela do izvornog koda ili obrnuto Generisanje izvesˇtaja koji opisuju klase (dijagrami ili tabelarno) Kombinovanje prednosti prva dva pristupa Prednosti primene sinhronizacije direktne i povratne analize za implementacije koje re- alizuju metode za generisanje triangulacija su: 1. huo)xvvvnjz sv komplzksno)s(xu prowlzmvO Bolje razumevanje definisanih klasa i njihovih metoda, identifikovanje med¯uzavisnosti, nacˇina komunikacije i protoka podataka. 2. Gznzrisvnjz vltzrnvtivnih poglzyv prowlzmvO Analiza izvornog koda sa viˇse aspekata i kroz nekoliko modela (uglavnom staticˇkih i dinamicˇkih) pruzˇa moguc´nost dopune izvornog koda, dodavanje novih metoda, simplifikacije i redefinisanje metoda, sinteze i analize metoda itd. 85 eovrvtnv vnvlizv i sinhronizvxijv =Reverse/Round-trip engineering) 3. dtkrivvnjz ponovljznih slu)xvjzvvO Nakon lociranja i uklanjanja izvornog koda ili mo- dula koji se ne koristi, smanjuje se slozˇenost problema i pojednostavljuje izvorni koˆd. Dakle, postizˇu se bolji rezultati koji se odnose na obimnost samih klasa kao i na njihovu funkcionalnost. Na osnovu datih analiza i ispitivanja mozˇe se zakljucˇiti da je najbolja praksa u primeni tehnike sinhronizacije. Dobijeni rezultati ukazuju na poboljˇsanje softverskih resˇenja kroz tri postavljena kriterijuma. Ova metodologija sa navedena tri pristupa se mozˇe primeniti kao nova tehnika u analizi i dizajnu algoritama za slicˇne probleme. Generalno, ovim je predlozˇen pristup koji je pogodan za analizu i dizajn implementacija nekih drugih algoritama racˇunarske geometrije. 86 dogluvlje J nuklju(cnu ruzmutrunju U disertaciji su analizirane nove metode i algoritmi za resˇavanje problema triangulacije poli- gona. Rezultati disertacije se mogu svrstati u tri kategorije. Prvu kategoriju cˇine predlozˇene nove tehnike i metode za generisanje triangulacija konveksnih poligona. Drugu kategoriju cˇine rezultati koji se odnose na nove metode za notaciju i skladiˇstenje triangulacija, dok trec´u kategoriju cˇine rezultati iz oblasti primene ddVD metodologije (sa tri tipa inzˇenjeringa) u cilju efikasne analize i dizajna algoritama za triangulaciju poligona. Sledi kratak pregled rezultata izlozˇenih poglavlja disertacije: 1. Data je analiza programskog jezika Jvvv sa aspekta moguc´nosti primene u racˇunarskoj geometriji kroz posedovanje gotovih klasa i biblioteka. Ispitano je, koliko je ovaj pro- gramski jezik pogodan za implementaciju algoritama racˇunarske geometrije. Urad¯ena je komparativna analiza implementacija za ]urtvyoBcoy algoritam, u tri objektno- orijentisana programska jezika (JvvvA X++A eython). Ova analiza je imala za cilj da ukazˇe na adekvatan izbor aktuelnog programskog jezika, kao efikasnog alata za implementaciju, a sve radi postizanja dobrih rezultata u realizaciji novih metoda za generisanje i notaciju triangulacija poligona. 2. Predstavljene su dve nove metode za generisanje triangulacija konveksnog poligona. U) Prva metoda se bazira na yzkompozixiji Kvtvlvnovog wrojv. Ovaj postupak proizvo- di izraze u obliku sume termova (2+i)P i ∈ {0P : : : P n−4}, sa ciljem primene u postupku generisanja triangulacija. Na osnovu ove ideje je uspostavljeno tezˇinsko stablo trian- gulacija. U cilju izbegavanja ponavljanja istih generisanja koriˇsc´ena je rekurzija sa memoizacijom. Ova tehnika resˇavanja problema se bazira na generisanju skupa tri- angulacija Tn koristec´i skup Tn−1. Kod mztoyz yzkompozixijz se iz prethodnog nivoa preuzima (n − 4) parova temena unutrasˇnjih dijagonala koje odred¯uju triangulaciju, a na osnovu izraza dekompozicije se preuzete triangulacije adekvatno dopunjuju. Do- bijen izraz iz postupka dekompozicije jasno pokazuje koliko se prenosi triangulacija iz Tn−1 u naredni nivo. Drugi sabirak u termu, oznacˇen sa i, pokazuje koliko se novih triangulacija generiˇse u skupu Tn. 87 ovklju)xnv rvzmvtrvnjv Kroz navedenu uporednu analizu ove metode sa ]urtvyoBcoy algoritmom, ukazano je na prednosti nove predlozˇene metode. Ovde je bitno istac´i dva aspekta koja su veoma vazˇna za implementaciju algoritama, a to su: (1) podaci koji se ocˇekuju na ulazu algoritma i (2) opterec´enost memorije. Na osnovu numericˇkih podataka koji su dobijeni eksperimentalnim ispitivanjem Jvvv aplikacija, mozˇe se utvrditi sledec´e: (1) Ukupno vreme (u sekundama) za svih 12 testiranja (za n ∈ {5P 6P :::P 16}), kod ]urtvyoBcoy algoritma je 1037.39 dok je kod mztoyz yzkompozixijz 936.22. Znacˇi, postignuto je prosecˇno ubrzanje za 1.108 odnosno poboljˇsanje u brzini generisanja za 10,8 %. (2) Prosecˇno vreme izvrsˇavanja po jednom nivou kod ]urtvyoBcoy algoritma je 94.31 dok je kod mztoyz yzkompozixijz 85.11. (3) Primenom mztoyz yzkompozixijz postignuto je povec´anje broja generisanih triangulacija u sekundi za 1.132 odnosno poboljˇsanje za 13,2 %. V) Generalna strategija wlok mztoyz je razlaganje problema na manje potprobleme koji su med¯usobno zavisni. Svaki potproblem se resˇava samo jednom a koristi se viˇse puta. Na taj nacˇin je izbegnuto nepotrebno ponavljanje istih generisanja, jer se adekvatno dopunjuju prethodno dobijeni rezultati. Metoda se zasniva na odnosu broja triangulacija dva uzastopna poligona. Jvvv sa svojim JDWX VeI -jem se pokazala kao efikasan alat za realizaciju ove metode. Navedene su moguc´nosti efikasnog skladiˇstenja i rad sa bazama podataka u Jvvv cztWzvns okruzˇenju. U komparativnoj analizi je zabelezˇeno prosecˇno vreme izvrsˇavanja po jednom nivou kod ]urtvyoBcoy algoritma 46.16 dok je kod wlok mztoyz 10.74. Takod¯e, i ovde se isticˇe prednost wlok mztoyz u odnosu na postojec´u, a to je da radi samo sa skupom temena unutrasˇnjih dijagonala. Kod ]urtvyoBcoy algoritma se na uzlazu ocˇekuje kompletna struktura, jer je svaka triangulacija iz prethodnog poligona en−1 opisana unutrasˇnjim dijagonalama i spoljasˇnjim ivicama. Ta obrada kompletne strukture znatno usporava rad njihove metode. Sve ovo bitno uticˇe i na opterec´enost memorije u toku izvrsˇavanja, pa i na brzinu generisanja triangulacija. 3. Date su nove metode za notaciju i skladiˇstenje triangulacija sa glavnim ciljem da se usˇtedi memorijski prostor i obezbedi jedinstven sistem zapisivanja (notacija) triangu- lacija. U) Prva metoda za notaciju se bazira na kombinatornim problemima: wvllot pro- blemu i problemu puteva u mrezˇi (lvttixz pvth). Metodu za wvllot notaciju cˇine dva inverzna algoritma (iz wvllot zapisa u graficˇki prikaz triangulacije i obrnuto). Uve- dena je primena steka koji znatno ubrzava proces skladiˇstenja triangulacija i koji daje znatno kompaktniji zapis u odnosu na postojec´e notacije (hkW izlazi). Eksperimen- talni rezultati implementirane metode ukazuju na poboljˇsanje u konstrukciji i notaciji triangulacija u odnosu na postojec´e algoritme. I ovde je rad¯ena komparativna ana- liza sa ]urtvyoBcoy algoritmom gde se primenom hkW izlaza mozˇe znatno uticati na usˇtedu memorije pri generisanju triangulacija poligona. 88 ovklju)xnv rvzmvtrvnjv Na osnovu numericˇkih podataka, mozˇe se videti da ]urtvyoBcoy algoritam daje bolje rezultate ako se uzme u obzir samo vreme generisanja triangulacija. Med¯utim, wvllot mztoy daje bolje rezultate ako se posmatra ukupno vreme gde je ukljucˇeno i gene- risanje i skladiˇstenje. Za ukupno vreme, za svih 11 testiranja (za v ∈ {5P 6P :::P 15}), postignuto je prosecˇno ubrzanje 1.09 odnosno smanjenje vremena za 9%. Primenom hkW izlaza, udeo vremena za skladiˇstenje je manji za wvllot mztoy (u opsegu od 8% do 12%, redom za svih 11 testiranja). Kod ]urtvyoBcoy algoritma, ta vrednost za ista testiranja se krec´e u opsegu od 16% pa sve do 63%. Ovo znacˇajno uticˇe na rezultate koji predstavljaju ukupno vreme izvrsˇavanja programa, tacˇnije za slucˇaj istovremenog generisanja i skladiˇstenja triangulacija. V) Predstavljena metoda za vlfvnumzri)xku notaciju mozˇe nac´i primenu ne samo u zapisivanju triangulacija konveksnog poligona vec´ i nekih drugih kombinatornih problema koji se baziraju na Katalanovim brojevima. Dati metod predstavlja nacˇin skrac´enja postojec´e BP notacije (notacija upvrznim zvgrvyvmv). Za ovaj metod su data dva algoritma koja realizuju dve transformacije (iz BP zapisa u AN i obrnuto). Na osnovu rezultata eksperimentalnih ispitivanja, uocˇene su prednosti primene AN notacije, a posebno se isticˇe razlika u broju znakova koja je evidentna za vrednosti n S 10. Za sve navedene rezultate testiranja (za vrednosti n ∈ {5P : : : P 14}) dobijamo prosecˇan koeficijent skrac´enja koji je priblizˇno jednak 2:69. Sa druge tacˇke glediˇsta, velicˇina izlazne datoteke naglo opada primenom AN notacije. Utvrd¯eno je da se pri- menom Vc notvxijz mozˇe usˇtedeti memorijski prostor za oko 65% za vrednosti n S 9 u odnosu na We notvxiju. Prednosti primene ove metode se mogu posmatrati kroz dva aspekta: (i) kroz usˇtedu memorijskog prostora u procesu trajnog snimanja tri- angulacija u vidu neke izlazne datoteke; (ii) i kroz usˇtedu radne memorije u procesu generisanja triangulacija. Ostvarivanjem ova dva cilja obezbed¯ujemo brzˇe generisanje i omoguc´avamo postupak obrade za poligone en, gde je n S 20. 4. Naveden je novi pristup kroz objektno-orijentisanu analizu i dizajn algoritama za triangulaciju poligona. Problem triangulisanja poligona je analiziran sa tri aspekta: pristupa direktnog razvoja (forfivry znginzzring), sa aspekta povratne analize (rzvzrsz znginzzring) i sinhronizacije prva dva pristupa (rounyBtrip znginzzring). U) Bolje razumevanje i detaljna analiza algoritma za triangulaciju se postizˇe primenom direktnog pristupa kroz kreiranje odgovarajuc´ih pogleda (modela) na sam problem. Na ovaj nacˇin smo dobili razvijenu strategiju planiranja implementacije problema koja je nezavisna od tehnologije i alata za implementaciju. Analiza problema triangulacije poligona je realizovana kroz jba modele, a dati su i primeri generisanja izvornog koda iz jba-a u programski jezik Jvvv. V) Uspostavljena je sinhronizacija programiranja u Jvvi i modeliranja u jba-u preko naprednih okruzˇenja. Ovim je omoguc´en uvid u analize uticaja uvod¯enja odgo- varajuc´ih promena, upoznavanje koda, ponovno koriˇsc´enje, integracija odred¯enih mo- 89 ovklju)xnv rvzmvtrvnjv dula izvornog koda i sl. Neke od uocˇenih prednosti uspostavljene sinhronizacije za date implementacije u disertaciji su: (i) Suocˇavanje sa kompleksnosˇc´u problema, bolje razumevanje definisanih klasa i njihovih metoda, identifikovanje med¯uzavisnosti, nacˇina komunikacije i protoka podataka; (ii) Generisanje alternativnih pogleda na pro- blem i analiza izvornog koda sa viˇse aspekata i kroz nekoliko modela; (iii) Otkrivanje ponovljenih slucˇajeva u izvornom kodu itd. Data su ispitivanja i analize izvornog koda implementacija, primenom sihronizacije programiranja i modeliranja, a sve sa ciljem da se dobije bolja struktura sa sˇto vec´om modularizacijom, bez ponovljenih slucˇajeva i sa integracijom odred¯enih delova. Nave- dene analize su imale za cilj i da se smanji obimnost i slozˇenost izvornog koda i da se uticˇe na funkcionalnost i rad segmenata implementacije zasebno. Dobijeni rezul- tati ukazuju na unapred¯enje softverskih resˇenja, gde je postignuto poboljˇsanje kroz tri postavljena kriterijuma: broj linija izvornog koda (13,13%), velicˇina izlazne datoteke (19,51 %) i brzina izvrsˇavanja (10,08 %). Otvaraju se nova pitanja za dalja istrazˇivanja u vezi ove oblasti, a odnose se na moguc´no- sti primene predstavljenih metoda. Buduc´i pravci razvoja datih metoda se odnose na ispiti- vanje i prilagod¯avanje za problem kvadragulacije poligona (podela poligona na kvadrate) u vidu novih softverskih resˇenja: Jvvv WloxkfuvyrA Jvvv Dzxompositionfuvyr (moguc´a pri- mena wlok mztoyz i/ili mztoyz yzkompozixijz za navedeni problem). Takod¯e, mogu biti ispitane moguc´nosti primene wvllot i vlfvnumzri)xkz notvxijz u zapisivanju i skladiˇstenju kvadragulacija poligona. U buduc´nosti se mozˇe razmatrati i o implementacijama novih metoda za pronalazˇenje i skladiˇstenje optimalnih triangulacija, kao i o problemu minimalne tezˇine triangulacija. Konacˇno, u cilju efikasne analize i dizajna novih algoritama za kvadragulaciju poligona i op- timalne triangulacije, po predlozˇenom modelu mozˇe biti upotrebljena objektno-orijentisana metodologija (sa tri tipa inzˇenjeringa). 90 drilozi I) doduci o preuzimunju uzvestmvm zm wlmse i impleA mentucije metodu Sve opisane metode po poglavljima su realizovane kroz konkretne aplikacije: 1. Tri Jvvv aplikacije za generisanje triangulacija konveksnih poligona (]urtvyoBcoyA mztoy yzkompozixijz i wlok mztoy); 2. Dve Jvvv aplikacije za notaciju triangulacija (vlfvnumzri)xkv i wvllot notvxijv); 3. jba dijagrami i kompletna dokumentacija u vidu opisa klasa i modela; 4. Implementacije ]urtvyoBcoy algoritma u eython-u i X++-u. Za sve klase koje su sastavni deo navedenih implementacija izgenerisan je izvesˇtaj u vidu detaljnih opisa kroz atribute, osnovne operacije, dijagrame, elemenate itd. Na httpODDmuzvfzrsCuninpCzyuCrsDrzportirivngulvtion, mozˇe se pristupiti kompletnom izve- sˇtaju klasa. Na Slici 6.1 je prikazan deo jednog izvesˇtaja za klasu Rpgalesjargml. Ovu praksu opisa standardnih klasa i paketa koristi Jvvv elvtform htvnyvry Zyition na svom zvanicˇnom sajtu: httpODDyoxsCorvxlzCxomDjvvvszDKDyoxsDvpiD. Slika 6.1: Izvz)stvj moyzlv iz cztWzvns jbaBv zv klvsu irivngulvtion 91 Na web strani httpODDmuzvfzrsCuninpCzyuCrsDtrivngulvxijvChtml mogu se preuzeti imple- mentacije za sve pomenute metode u disertaciji (Slika 6.2). Slika 6.2: lzw strvnv zv przuzimvnjz izvr)snih =zxz) vplikvxijv 92 II) Jmvm izvorni krod U ovom prilogu su navedeni neki delovi klasa za realizaciju novih tehnika i metoda koje su opisane u trec´em i cˇetvrtom poglavlju disertacije. Istaknuti su vazˇniji segmenti sledec´ih klasa: Rpgalesjargml* EclcparcRpgalesjargmlq* LmrcRpgalesjargml* Nmglr* Lmbc* LcadLmbc* Barabaqc g NmqrSapgnrUpgrcp. U) KlusuN Trumzsulmtuoz Klasa Rpgalesjargml je zaduzˇena za generisanje svih triangulacija u graficˇkom obliku. Glavne metode klase su Bpau i BpauAjj. - Metoda Bpau() iscrtava pojedinacˇne triangulacije konveksnih poligona. Pomoc´u metode bpauLglc() se vrsˇi spajanje temena, linijama po odgovarajuc´em rasporedu. Jedna kombi- nacija unutrasˇnjih dijagonala cˇini jednu triangulaciju poligona. - Metoda BpauAjj() poziva Bpau metodu. Broj izvrsˇavanja Bpau() metode u okviru petlje je jednak Katalanovom broju za dato n. Na taj nacˇin se iscrtavaju sve triangulacije poligona en. Metoda BpauAjj() povezuje sve triangulacije u jednu izlaznu datoteku (u razlicˇitim formatima). 1 uyport vmvm : u o : U[Qxoqptuoz G 2 uyport vmvm : u t u x : bqotor G 3 4 pun x u o o x m s s Tr umzsu xm t u oz { 5 ∗∗∗ 6 pr u vm t q u z t sOursord , sOursore G 7 pr u vm t q bqotor po uz t s G 8 pr u vm t q PostSor uptcru tq r wr u t q r G 9 pr u vm t q bqotor sS uzq G 10 pr u vm t q bqotor sOos uzq G 11 12 pun x u o Tr umzsu xm t u oz 4 u z t qpsqs , PostSor uptcru tq r wr u t q r 5 { 13 t t u s : sOursord I Tr umzsu xm t u oz :dXUYUT G 14 t t u s : sOursore I Tr umzsu xm t u oz :eXUYUT G 15 t t u s : po uz t s I zqw bqotor45 G 16 t t u s : w r u t q r I wr u t q r G 17 t t u s : sS uzq I zqw bqotor 4 5 G 18 t t u s : sOos uzq I zqw bqotor 4 5 G 19 20 r o r 4 u z t wI0G w < qpsqs G w++5 { 21 pounxq p I 44∗w+qpsqs 5 ∗Ymtt : PU ;42∗ qpsqs 5 G 22 t t u s : sS uzq : mpp 4x∗Ymtt : s u z 4p5 5 G 23 t t u s : sOos uzq : mpp 4y∗Ymtt : oos 4p5 5 G } 24 } 25 26 pun x u o voup o x q m r 4 5 { 27 t t u s : po uz t s : rqyovqMxxQxqyqzts 4 5 G } 93 28 29 pun x u o voup oopyRroy4 u z t m[r r sqt , Zopq t 5 { 30 u r 4 ! 4 t u z s t mz o q o r XqmrZopq 5 5 { 31 t t u s : oopyRroy4 m[r r sqt , t : s q tXq r t 4 5 5 G 32 t t u s : oopyRroy4 m[r r s q t+t : s q tXq r t 4 5 : x q m v q s 4 5 , t : sqtRustt 4 5 5 G } 33 t t u s : po uz t s : mpp 4zqw Pouzt 4 m[r r sqt , m[ r r s q t + t : x q mv q s 4 5 5 5 G 34 } 35 36 pun x u o voup Prmw4 5 ttrows U[Qxoqptuoz { 37 u r 4 Tr umzsu xm t u oz :dXUYUT t r q q s 5 ttrows U[Qxoqptuoz { 52 t t u s : w r u t q r : psTqmpqr 4 5 G 53 54 r o r 4 u z t u I 0 G u < t r q q s : s u z q 4 5 G u++5 { 55 Zopq t I t r q q s : sqt 4 u 5 G 56 t t u s : o x q m r 4 5 G 57 t t u s : oopyRroy 40 , t 5 G 58 t t u s : Prmw4 5 G 59 u r 4 u !I 0 22 u 1AA II 05 { 60 t t u s : sOursord I Tr umzsu xm t u oz :dXUYUT G 61 t t u s : sOursore I Tr umzsu xm t u oz :eXUYUT G 62 t t u s : w r u t q r : zqwPmsq 4 5 G } 63 } 64 t t u s : w r u t q r : T r m u x q r 4 5 G } 65 } V) KlusuN SezermteTrumzsulmtuozs Klasa EclcparcRpgalesjargmlq sadrzˇi glavnu izvrsˇnu metodu, kao i metodu za generisanje triangulacija. Za metode wlokA yzkompozixiju i ]urtvyo koristi se ista struktura ove klase, jedino se razlikuje metoda za odred¯en nacˇin generisanja triangulacija. U slucˇaju implementacije ]urtvyoBcoy algoritma to je metoda Fsprabm(), u slucˇaju yzkompozixijz Kvtvlvnovog wrojv to je ApcarcCvnp(), dok je Jvvv metoda Bjmai() u im- plementaciji opisane wlok mztoyz. 94 VBEB Klasa EclcparcRpgalesjargmlq sadrzˇi komponente za GjI aplikacije iz hlIcG i Vli paketa: 1 uyport vmvm : u o : ∗ G 2 uyport vmvm : u t u x : ∗ G 3 uyport vmvm : u o : Nur rqrqpcrutqr G 4 uyport vmvm : u o : R u x qcr u t q r G 5 uyport vmvm : u t u x : bqotor G 6 uyport vmvmx : swuzs : ∗ G 7 uyport vmvmx : swuzs : qvqzt : ∗ G 8 uyport vmvmx : swuzs : VTooxNmr G 9 uyport vmvmx : swuzs : norpqr : ∗ G 10 uyport vmvm : mwt : ∗ G 11 uyport vmvm : mwt : sqoy : ∗ G 12 uyport vmvm : mwt : qvqzt : ∗ G 13 uyport vmvm : mwt : Too xw u t G 14 15 pun x u o o x m s s SqzqrmtqTr umzsu xmt uozs qxtqzps VRrmyq uypxqyqzts Mot u ozX u s t qzq r { 16 s t m t u o u z t p G 17 VXmnqx zovq I zqw VXmnqx 4 .PMZQX fM aZ[S Z[bUT TRUMZSaXMOUVM. 5 G 18 VXmnqx prqs x qp I zqw VXmnqx 4 .PMZQX fM PRQSXQP SZUYXVQZUT TRUMZSaXMOUVM. 5 G 19 VXmnqx x mn q x m 2 I zqw VXmnqx 4 .azos nro vm tqyqzm po x u sozm zm s qz q r u s mz v q . 5 G 20 VTqxtRuq xp p o x v q I zqw VTqxtRuq xp 4305 G 21 VNuttoz pusyq I zqw VNuttoz 4 .Wrq u rmz v q Tr u mzsu x m o u v m . 5 G 22 VNuttoz pusyq2 I zqw VNuttoz 4 .[tvoru vqo w r q u r mz r m v x . 5 G 23 ∗∗∗ VBFB Metoda aargmlNcpdmpkcb() sluzˇi za dodeljivanje funkcionalnosti komponentama GjI aplikacije. U ovom slucˇaju je dodeljena funkcionalnost na dugme koje izvrsˇava BpauAjj metodu. Ova metoda omoguc´ava pregled vec´ snimljenih rezultata (graficˇki prikaz i notaciju). 1 pun x u o voup mot uozPqrroryqp 4 MotuozQvqzt qvt 5 { 2 u r 4 qvt : sqtSouroq 4 5I Ipusyq5 { 3 t ry { 4 p I Uz t qs q r : pm r s q Uz t 4 p o x v q : sqtTqxt 4 5 5 G 5 Ru x qcr u t q r r s t rqmy I zqw Ru x qcr u t q r 4p+.−poxysozs : ps. 5 G 6 Nur rqrqpcrutqr out I zqw Nur rqrqpcrutqr 4 r s t rqmy 5 G 7 PostSor uptcru tq r wr u t q r I zqw PostSor uptcru tq r 4 out 5 G 8 SqzqrmtqTr umzsu xmt uozs mpp I zqw SqzqrmtqTr umzsu xmt uozs 4 5 G 9 bqotor nt r q q s I mpp : Turtmpo 4p−25 G 10 Tr umzsu xm t u oz uz s t mzo qTr u mzsu x m t u oz I zqw Tr umzsu xm t u oz 4p , wr u t q r 5 G 11 u z s t mzo qTr u mzsu x m t u oz : PrmwMxx 4 n t r q q s 5 G 12 out : o x o s q 4 5 G } 13 omtot 4 Qxoqptuoz q 5 { q : pr uztStmowTrmoq 4 5 G} 14 t t u s : opqzRu x q 4 S t r uzs : vmxuq[r 4p5 +.−poxysozs : ps. 5 G } 15 } 95 C) KlusuN NoteTrumzsulmtuoz Klasa LmrcRpgalesjargml se koristi za dve metode zapisivanja (vlfvnumzri)xkv i wvllot no- tacija) koje su opisane u cˇetvrtom poglavlju. Obe metode koriste istu struktura ove klase, jedino se razlikuje metoda za odred¯enu notaciju triangulacija (ALlmrargml() ili BajjmrLmrargml()). CBEB Metoda apcarcRpgalesjargml() se koristi za formiranje triangulacije na osnovu dobijenog zapisa iz pomenutih metoda koje realizuju odred¯enu notaciju. 1 o x m s s ZotmtqTr umzsu xmt uozs qxtqzps bqotor uypxqyqzts PrmwTrumzsPox{ 2 ∗∗∗ 3 pun x u o voup o r qm t qTr u mzsu x m t u oz 4 5 { 4 Pro r u xX u s tNP I zqw bqotor g orpqr +=i G 5 r o r 4 u z t u I 0 G u < orpqr+= G u++ 5 6 Pro r u xX u s tNP g u i I zqw bqotor 4 5 G 7 Pro r u xX u s tNP g 0 i : mppQxqyqzt 4 zqw XZopqs 4 5 5 G 8 u z s t mzo qTr u mzsu x m t u oz I zqw ZotmtqTr umzsu xmt uozs 4 5 G 9 10 r o r 4 u z t w I 0 G w < orpqr+2 G w++ 5 { 11 pounxq p I 42∗ orpqr+2−4∗w 5 ∗Ymtt : PU ;42∗ orpqr+45 G 12 Rsuzus g w i I 4 u z t 5Ymtt : r x o o r 4B0∗Ymtt : s u z 4p5 5 G 13 Rwosuzus g w i I 4 u z t 5Ymtt : r x o o r 4B0∗Ymtt : oos 4p5 5 G 14 } 15 16 r o r 4 u z t z I = G z < orpqr+= G z++ 5 { 17 r o r 4 u z t u I 0 G u < z G u++ 5 { 18 r o r 4 u z t v I 0 G v < Pro r u xX u s tNP g u i : s u z q 4 5 G v++ 5 { 19 r o r 4 u z t w I 0 G w < Pro r u xX u s tNP g z−u −=i : s u z q 4 5 G w++ 5 { 20 Pro r u xX u s tNP g z i : mppQxqyqzt 4 21 zqw Zopqs 4 22 4 XustNP 5 Pro r u xX u s tNP g u i : qxqyqztMt 4 v 5 , 23 4 XustNP 5 Pro r u xX u s tNP g z−u −=i : qxqyqztMt 4w 5 5 5 G} 24 } 25 } 26 } 27 } CBFB Upotreba BsddcpcbUpgrcp iz hata,gm,BsddcpcbUpgrcp za snimanje rezultata u formi odred¯ene notacije je realizovana sledec´im segmentom izvornog koda u Jvvi : 1 zI=G 2 r o r 4 u I0G u