| Title: | APROKSIMACIJA SREDNJE OSI ENOSTAVNIH MNOGOKOTNIKOV |
|---|
| Authors: | ID Smogavec, Gregor (Author)
ID Žalik, Borut (Mentor) More about this mentor... 
ID Podgorelec, David (Comentor) |
|---|
| Files: |  UNI_Smogavec_Gregor_2010.pdf (2,93 MB)
MD5: 2A2A8F079F5F6287780A3DA08BA76C45
PID: 20.500.12556/dkum/8041389f-bc31-49f0-997d-d7e1504e5e96
|
|---|
| Language: | Slovenian |
|---|
| Work type: | Undergraduate thesis |
|---|
| Organization: | FERI - Faculty of Electrical Engineering and Computer Science
|
|---|
| Abstract: | Srednja 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. |
|---|
| Keywords: | algoritem, računalniška geometrija, srednja os, triangulacija, središča maksimalnih krožnic |
|---|
| Place of publishing: | Maribor |
|---|
| Publisher: | [G. Smogavec] |
|---|
| Year of publishing: | 2009 |
|---|
| PID: | 20.500.12556/DKUM-12792 |
|---|
| UDC: | 004.94(043.2) |
|---|
| COBISS.SI-ID: | 13786390 |
|---|
| NUK URN: | URN:SI:UM:DK:HXH5U2LS |
|---|
| Publication date in DKUM: | 06.01.2010 |
|---|
| Views: | 1999 |
|---|
| Downloads: | 150 |
|---|
| Metadata: |    |
|---|
| Categories: | KTFMB - FERI
|
|---|
|
:
|
Copy citation |
|---|
| | | | Average score: | (0 votes) |
|---|
| Your score: | Voting is allowed only for logged in users. |
|---|
| Share: |  |
|---|
Hover the mouse pointer over a document title to show the abstract or click
on the title to get all document metadata. |
