Přejít k obsahu


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

Citace:
SKALA, V., ŠMOLÍK, M. A Point in Non-Convex Polygon Location Problem Using the Polar Space Subdivision in E2. In Image and Graphics: 8th International Conference, ICIG 2015, Tianjin, China, August 13-16, 2015, Proceedings, Part I. Cham: Springer, 2015. s. 394-404. ISBN: 978-3-319-21977-6 , ISSN: 0302-9743
Druh: STAŤ VE SBORNÍKU
Jazyk publikace: eng
Anglický název: A Point in Non-Convex Polygon Location Problem Using the Polar Space Subdivision in E2
Rok vydání: 2015
Místo konání: Cham
Název zdroje: Springer
Autoři: Prof. Ing. Václav Skala CSc. , Ing. Michal Šmolík
Abstrakt CZ: Test bodu uvnitř/vně polygonu je používán v mnoha aplikacích počítačové grafiky, počítačových her a geografických informačních systémech. Pokud je test opakován několikrát se stejným polygonem, je potřeba datová struktura pro snížení lineárního času, který je zapotřebí pro získání výsledku. V literatuře jsou prezentovány různé postupy, jako grid nebo quadtree ke snížení komplexity těchto algoritmů. Navrhujeme novou metodu, která využívá polárního dělení ke snížení času potřebného pro test. Navrhovaný algoritmus je robustní a má složitost O(k), kde k?N, k je počet testovaných průsečíků s hranami polygonu a časová složitost preprocessingu je O(N), kde n je počet hran polygonu.
Abstrakt EN: 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 k?N, k is the number of tested intersections with polygon edges, and the time complexity of the preprocessing is O(N), where N is the number of polygon edges.
Klíčová slova

Zpět

Patička