VRSTA GRADIVA | analitična raven (sestavni del), tekstovno gradivo, tiskano, 1.01 - izvirni znanstveni članek |
DRŽAVA IZIDA | Slovenija |
LETO IZIDA | 2004 |
JEZIK BESEDILA/IZVIRNIKA | slovenski |
PISAVA | latinica |
AVTOR | Gomboši, Matej - avtor |
NASLOV | Ugotavljanje vsebnosti točk nad posplošenimi mnogokotniki |
V PUBLIKACIJI | Uporabna informatika. - ISSN 1318-1882. - ǂLetn. ǂ12, ǂšt. ǂ2 (apr./maj/jun. 2004), str. 90-96. |
KRATKA VSEBINA | V članku je opisan razširjen algoritem za določanje vsebnosti točk nad posplošenimi mnogokotniki, ki poleg daljic vsebujejo tudi krožne loke. Algoritem uporablja klasično metodo sekanja žarka. Razlika je v tem, da moramo testirati dve vrsti objektov. Nalogo opravimo z enostavnimi in učinkovitimi testi, ki nam hitro odgovorijo na vprašanje. Z uporabo ustreznih podatkovnih struktur nalogo rešimo zanesljivo in enostavno. Kljub razširitvi deluje algoritem še vedno v linearni časovni zahtevnosti. // The paper describes an extended algorithm for solving the point-in-polygon problem. The polygon in this case consistsof straight edges and al so of circular arcs. This represents a generalization of Reuleaux polygon. The algorithm uses the classical ray intersection method. The difference is that we have two types of geometric objects to test for intersections. Processing is done with simple and efficient tests, which quickly answer our question. Using the appropriate data structure, this task can be done safely and easily. Despite the extension of the classical ray intersection method, the algorithm still runs in linear time complexity. |
OSTALI NASLOVI | Containment test for generalized polygons |
PREDMETNE OZNAKE | // algoritmi // podatkovne strukture // mnogokotniki |
UDK | 004.92 |