A Point in Non-Convex Polygon Location Problem Using the Polar Space Subdivision in E2
The result's identifiers
Result code in 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>
Result on the web
<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>
Alternative languages
Result language
angličtina
Original language name
A Point in Non-Convex Polygon Location Problem Using the Polar Space Subdivision in E2
Original language description
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.
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
CEP classification
IN - Informatics
OECD FORD branch
—
Result continuities
Project
<a href="/en/project/LH12181" target="_blank" >LH12181: Development of Algorithms for Computer Graphics and CAD/CAM systems</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>S - Specificky vyzkum na vysokych skolach
Others
Publication year
2015
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
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
—
Number of pages
11
Pages from-to
394-404
Publisher name
Springer
Place of publication
Cham
Event location
Tianjin
Event date
Aug 13, 2015
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—