VRSTA GRADIVA | analitična raven (sestavni del), tekstovno gradivo, tiskano, 1.03 - kratki znanstveni prispevek |
DRŽAVA IZIDA | Slovenija |
LETO IZIDA | 2002 |
JEZIK BESEDILA/IZVIRNIKA | angleški |
PISAVA | latinica |
AVTOR | Lamot, Marko - avtor |
ODGOVORNOST | Žalik, Borut - avtor |
NASLOV | ǂAn ǂefficient simple polygon triangulation algorithm based on a uniform plane subdivision |
V PUBLIKACIJI | Contributions to geometric modelling and multimedia. - ISSN 1580-5689. - ǂVol. ǂ2, ǂno. ǂ3 (2002), str. 1-27. |
KRATKA VSEBINA | A new algorithm for triangulating simple polygons is proposed. The algorithm uses a uniform space subdivision to speed-up the triangulation. The algorithm efficiently combines two approaches: an ear-cutting and a diagonal insertion. Comparison with the popular polygon triangulation algorithms (Sloan's ear-cutting algorithm, Seidel's randomized incremental algorithm, algorithm based on Graham scan, and Garey's et al plane-sweep algorithm) for different classes of simple polygons (general, convex, monotone, star-shaped, and the polygons taken from a GIS database) is presented. For general polygons and GIS polygons, the proposed algorithm is the most efficient among the tested algorithms. // V delu predstavimo nov algoritem za triangulacijo enostavnih mnogokotnikov. Za pohitriteh triangulacije uporabimo enakomerno delitev prostora. Algoritem učinkovito kombinira dva pristopa: rezanje uhljev in vstavljanje diagonal. V poročilu predstavimo primerjave s popularnimi algoritmi triangulacije mnogokotnikov (Sloanov algoritem rezanja uhljev, Seidelov naključni inkrementalni algoritem, algoritem, ki temelji na Grahamoem preiskovanju in Gareyev algoritem preiskovalne premice) ob uporabi mnogokotnikov z različnimi karakteristikami (splošni, konveksni, monotoni, zvezdasti in algoritmi iz GIS podatkovne baze). Za splošne mnogokotnike in realne mnogokotnike iz GIS podatkovne baze je predlagan algoritem najučinkovitejši. |
OPOMBE | Bibliografija: str. 25-27 |
OSTALI NASLOVI | Učinkovit in enostaven algoritem triangulacijemnogokotnikov z uporabo enakomerne delitve |
PREDMETNE OZNAKE | // rečunalniška geometrija // enostavni mnogokotniki // uniformirmna delitev prostora // triangulacija mnogokotnika |
UDK | 004.9 |