1300 KB18 KB199320262004Gomboši, Matejletnik:12številka:2str. 90-96ISSN:1318-1882COBISSID:8898838URN:URN:NBN:SI:doc-IFL9NU9WslSlovensko društvo InformatikaUporabna informatika (Ljubljana)algoritmimnogokotnikipodatkovne struktureUgotavljanje vsebnosti točk nad posplošenimi mnogokotniki|The paper describes an extended algorithm for solving the point-in-polygon problem. The polygon in this case consists of 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 complexityV č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 zahtevnostiTEXTznanstveno časopisjejournalsSlovenian National E-content AggregatorNational and University Library of SloveniaSlovensko društvo Informatika