APROKSIMACIJA SREDNJE OSI ENOSTAVNIH MNOGOKOTNIKOVSmogavec, Gregor (Avtor) Žalik, Borut (Mentor) Podgorelec, David (Komentor) algoritemračunalniška geometrijasrednja ostriangulacijasredišča maksimalnih krožnicSrednja os mnogokotnika je množica središč maksimalnih notranjih krožnic v mnogokotniku. Uporablja se kot nepogrešljiv del pri reševanju različnih problemov, kot so razpoznavanje znakov, GIS, zaznavanje trkov, obdelava in analiza slik. Po definiciji dobimo eksaktno rešitev srednje osi, če v mnogokotnik vstavljamo krožnice, ki se stikajo z mejami mnogokotnika na vsaj dveh mestih, in povežemo sosednja središča le teh. Omenjeni pristop pa za posledico, razen eksaktne rešitve, potegne za sabo veliko časovno zahtevnost. To je glavni razlog, zakaj ima ta pristop omejeno uporabnost pri zgoraj omenjenih nalogah, če potrebujemo rešitev v realnem času. V diplomski nalogi predlagamo nov algoritem, ki se bo uspešno kosal s tem problemom. Algoritem deluje v štirih korakih. Najprej se zgradi omejena Delaunayeva triangulacija nad mnogokotnikom. Nato iz triangulacije izločimo odvečne trikotnike. Preostalo triangulacijo popravimo z dodajanjem Steinerjevih točk in nazadnje povežemo središča sosednjih si trikotnikov, da dobimo aproksimacijo srednje osi mnogokotnika. Meritve kažejo, da dobimo z našim algoritmom aproksimacijo srednje osi zelo hitro, kar nam daje možnost, da uporabimo algoritem v realno časovnih aplikacijah, kot na primer v robotizaciji.[G. Smogavec]20092009-12-23 12:45:14Diplomsko delo12792UDK: 004.94(043.2)COBISS_ID: 13786390NUK URN: URN:SI:UM:DK:HXH5U2LSsl