Přejít k obsahu


A new visibility walk algorithm for point location in planar triangulation

Citace: [] SOUKAL, R., MÁLKOVÁ, M., KOLINGEROVÁ, I. A new visibility walk algorithm for point location in planar triangulation. In Advances in Visual Computing, 8th International Symposium, ISVC 2012. Heidelberg, Berlin: Springer Verlag, 2012. s. 736-745. ISBN: 978-3-642-33191-6 , ISSN: 0302-9743
Druh: STAŤ VE SBORNÍKU
Jazyk publikace: eng
Anglický název: A new visibility walk algorithm for point location in planar triangulation
Rok vydání: 2012
Místo konání: Heidelberg, Berlin
Název zdroje: Springer Verlag
Autoři: Ing. Roman Soukal , Ing. Martina Málková , Prof. Dr. Ing. Ivana Kolingerová
Abstrakt CZ: Hledání trojúhelníku, který geometricky obsahuje hledaný bod, je velmi často řešeným problémem výpočetní geometrie. Obvykle je třeba vyhledat velké množství bodů a proto je třeba rychlého algoritmu, který bude odolný na změny v triangulaci a který bude mít minimální dodatečné paměťové nároky. Tzv. procházkové algoritmy nabízejí nízkou výpočetní složitost, lehkou implementaci a zanedbatelné paměťové nároky, proto jsou vhodné právě pro zmíněnou aplikaci. V článku prezentujeme nový procházkový algoritmus, který výrazně vylepšuje původní algoritmus využívající barycentrické souřadnice, a dále nabízíme způsob, kterým ho lze efektivně skombinovat s vhodnou hierarchickou datovou strukturou, čímž snížíme výpočetní složitost. Zmíněná hierarchická datová struktura nabízí lehkou implementaci a vyžaduje pouze nízké dodatečné paměťové nároky, ovšem přináší výrazné urychlení, díky logaritmické výpočetní složitosti vyhledávání.
Abstrakt EN: Finding which triangle in a planar triangle mesh contains a query point is one of the most frequent tasks in computational geometry. Usually, a large number of point locations has to be performed, and so there is a need for fast algorithms resistant to changes in triangulation and having minimal additional memory requirements. The so-called walking algorithms offer low complexity, easy implementation and negligible additional memory requirements, which makes them suitable for such applications. In this paper, we propose a walking algorithm which significantly improves the current barycentric approach and propose how to effectively combine this algorithm with a suitable hierarchical structure in order to improve its computational complexity. The hierarchical data structure used in our solution is easy to implement and requires low additional memory while providing a significant acceleration thanks to the logarithmic computational complexity of the search process.
Klíčová slova

Zpět

Patička