A Point in Non-Convex Polygon Location Problem Using the Polar Space Subdivision in E2

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F49777513%3A23520%2F15%3A43925825" target="_blank" >RIV/49777513:23520/15:43925825 - isvavai.cz</a>

Výsledek na webu

<a href="http://dx.doi.org/10.1007/978-3-319-21978-3_34" target="_blank" >http://dx.doi.org/10.1007/978-3-319-21978-3_34</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/978-3-319-21978-3_34" target="_blank" >10.1007/978-3-319-21978-3_34</a>

Jazyk výsledku

angličtina

Název v původním jazyce

A Point in Non-Convex Polygon Location Problem Using the Polar Space Subdivision in E2

Popis výsledku v původním jazyce

The point inside/outside a polygon test is used by many applications in computer graphics, computer games and geographical information systems. When this test is repeated several times with the same polygon a data structure is necessary in order to reduce the linear time needed to obtain an inclusion result. In the literature, different approaches, like grids or quadtrees, have been proposed for reducing the complexity of these algorithms. We propose a new method using a polar space subdivision to reduce the time necessary for this inclusion test. The proposed algorithm is robust and has a performance of O(k), where kMUCH LESS-THANN, k is the number of tested intersections with polygon edges, and the time complexity of the preprocessing is O(N), whereN is the number of polygon edges.

Název v anglickém jazyce

A Point in Non-Convex Polygon Location Problem Using the Polar Space Subdivision in E2

Popis výsledku anglicky

The point inside/outside a polygon test is used by many applications in computer graphics, computer games and geographical information systems. When this test is repeated several times with the same polygon a data structure is necessary in order to reduce the linear time needed to obtain an inclusion result. In the literature, different approaches, like grids or quadtrees, have been proposed for reducing the complexity of these algorithms. We propose a new method using a polar space subdivision to reduce the time necessary for this inclusion test. The proposed algorithm is robust and has a performance of O(k), where kMUCH LESS-THANN, k is the number of tested intersections with polygon edges, and the time complexity of the preprocessing is O(N), whereN is the number of polygon edges.

Druh

D - Stať ve sborníku

CEP obor

IN - Informatika

OECD FORD obor

—

Projekt

<a href="/cs/project/LH12181" target="_blank" >LH12181: Vývoj algoritmů počítačové grafiky a pro CAD/CAM systémy Development of Algorithms for Computer Graphics and CAD/CAM systems</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>S - Specificky vyzkum na vysokych skolach

Rok uplatnění

2015

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

Image and Graphics: 8th International Conference, ICIG 2015, Tianjin, China, August 13-16, 2015, Proceedings, Part I

ISBN

978-3-319-21977-6

ISSN

0302-9743

e-ISSN

—

Počet stran výsledku

11

Strana od-do

394-404

Název nakladatele

Springer

Místo vydání

Cham

Místo konání akce

Tianjin

Datum konání akce

13. 8. 2015

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—