VRSTA GRADIVA | analitična raven (sestavni del), tekstovno gradivo, tiskano, 1.03 - kratki znanstveni prispevek |
DRŽAVA IZIDA | Slovenija |
LETO IZIDA | 2001 |
JEZIK BESEDILA/IZVIRNIKA | angleški |
PISAVA | latinica |
AVTOR | Podgorelec, David - avtor |
ODGOVORNOST | Žalik, Borut - avtor |
NASLOV | ǂA ǂtriangulation algorithm for concave polygons containing holes |
V PUBLIKACIJI | Contributions to geometric modelling and multimedia. - ISSN 1580-5689. - ǂVol. ǂ1, ǂno. ǂ1 (2001), str. 1-28. |
KRATKA VSEBINA | V poročilu podajamo nekaj podrobnosti, ki se nanašajo na implementacijo algoritma za triangulacijo mnogokotnika. Obravnavamo znani algoritem, ki najprej razdeli mnogokotnik v monotone dele, nato pa le-te triangulira vsakega posebej. Metoda uspešno deluje tudiza mnogokotnike, ki vsebujejo luknje. Vključena naj bi bila v večjo komercialno aplikacijo, zato jo je bilo treba implementirati karseda robsustno. Nujno se je bilo treba izogniti vsem aritmetičnim operacijam, katerih rezultati so lahko nenatančni: deljenju, kotnim funkcijam in korenjenju. Uporabili smo tudi posebne podatkovne strukture - drevesa sosedov, ki poenostavijo in pospešijo delitev v monotone dele. // In the report, some details on implementation of a polygon triangulation algorithmare given. The well-known algorithm, which first divides the polygon into monotone pieces and then triangulate particular pieces, is considered. The method also works successfully with polygons containing holes. While it wasintended to be a part of some widely used commercial software system, we also had to achieve a robust implementation by avoiding all arithmetical operations that colud produce inexact results: floating point divisions, triangular functions and square root calculations. We have also employed some special data structures i.e. neighbor trees to facilitate and accelerate the division into monotone pieces. |
OPOMBE | Bibliografija: str. 28 |
PREDMETNE OZNAKE | // traingulacija // računalniška geometrija // računalniška grafika |
UDK | 004.42:514.113, 514.113 |