| KRATKA VSEBINA | V delu predstavljamo novi algoritem za rešitevproblema vsebnostnega testa. Algoritem je zasnovan za primere, ko moramo primerjati množico točk glede na vsebnost v mnogokotniku. Algoritem deluje v dveh korakih. Najprej ravnino enakomerno razdelimo v mrežo enkih celic, na katero položimo mnogokotnik. Za določitev dimenzij celic predlagamo heuristiko. Celice enakomerne delitve zatem označimo kot tiste, ki so zunaj, na meji ali v notranjosti mnogokotnika. V ta namen upoorabimo prirejen algoritem poplavljanja. V drugem koraku testiramo točke iz vhodne množice točk. Če testirana točka pade v celico, ki je označena kot notranjaali zunanja, vrnemo njen položaj brez dodatnih izračunavanj. Če pa se celica nahaja v mejni celici, lahko lokalno (samo z robovi, ki se nahajajo v tej celici) določimo, ali je testirana točka v notranjosti, zunanjosti ali na meji testirnega mnogokotnika. Analiza časovne zahtevnosti pokaže, daje inicializacija opravljena v času O(n▫$[kvadratni koren]n$▫), pričakovanačasovna zahtevnost samega vsebnostnega testa pa je boljša kot O(log n), kjer je n število oglišč mnogokotnika. Na koncu dela prikažemo rezultate narazličnih mnogokotnikih. // This work describes a new algorithm for a point-in-polygon problem. It is especially suitable, when many points are checked whether they are placed inside a polygon or not. The algorithm works in two steps. At first, a grid of equally sized cells is generated, and the polygon is laid on that grid. A heuristic is proposed for cells dimensioning. The cells of the grid are marke das being inside, outside, orpolygon border. A modified flood-fill algorithm is applied for cells classification. In the second step, points are tested individually. If the tested point falls into an inner or an outer cell, result is returned without any additional calculations. If the cell contains polygon's border,it is possible to determine locally, if the point is inside,outside, or on the border of the polygon. The analysis of time complexity shows that the initialization is finished in O(n▫$[square root]n$▫)time, while the expectdtime complexity for checking individual pointis O(▫$[square root]n$▫), whenn represent the number of polygon edges. At the end, the repotr gives also practical results using artificial and real polygons from GIS environment. |