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 |
ODGOVORNOST | Žalik, Borut - avtor // Podgorelec, David - avtor // Krivograd, Sebastian - avtor // Klajnšek, Gregor - avtor // Zadravec, Mirko - avtor |
NASLOV | Trapezoid polygon decomposition |
V PUBLIKACIJI | Contributions to geometric modelling and multimedia. - ISSN 1580-5689. - ǂVol. ǂ2, ǂno. ǂ2 (2002), str. 1-25. |
KRATKA VSEBINA | A efficient algorithm for simple polygons trapezoidation based on a sweep-line paradigm is described. As the sweep-line glides over the plane, a set of so-called open trapezoids is maintained. It is shown that boundary case (more polygon vertices are located on the sweep-line) is solved safely and do not slow-down the algorithm. If desired, the polygon holes trapezoidated in one pass, too, what is applicable in some applications. The proposed algorithm is faced with the fastest algorithm up to know developed by Seidel [2] and turns outas more efficient for different classes of polygons. // V poročilu opišemo nov algoritem za razdelitev mnogokotnika v trapezoide. Algoritem temelji nauporabi principa skanirne premice. Med polzenjem skanirne premice preko ravnine nadziramo množico takoimenovanih odprtih trapezoidov. Pokažemo, da robne primere (ko leži na skanirni premici več oglišč mnogokotnika) rešimo enostavno in da ti primeri ne upočanjujejo algoritma. Algoritem omogoča trapezoidacijo tudi lukenj mnogokotnika. Predlagan algoritem primerjamo s Seidelovim algoritmom [12] in pokažemo, da je naš algoritem uspešnejši za različne razrede mnogokotnikov. |
OPOMBE | Soavtorji: David Podgorelec, Sebastian Krivograd, Gregor Klajnšek, Mirko Zadravec // Bibliografija: str. 24-25 |
OSTALI NASLOVI | Delitev mnogokotnika na trapezoide |
PREDMETNE OZNAKE | // mnogokotniki // računalniška geometrija |
UDK | 004.9:514.116 |