Přejít k obsahu


Hybrid Walking Point Location Algorithm

Citace: [] SOUKAL, R., MÁLKOVÁ, M., VOMÁČKA, T., KOLINGEROVÁ, I. Hybrid Walking Point Location Algorithm. In ADVCOMP 2011. Lisbon: IARIA, 2011. s. 7-11. ISBN: 978-1-61208-172-4
Druh: STAŤ VE SBORNÍKU
Jazyk publikace: eng
Anglický název: Hybrid Walking Point Location Algorithm
Rok vydání: 2011
Místo konání: Lisbon
Název zdroje: IARIA
Autoři: Ing. Roman Soukal , Ing. Martina Málková , Ing. Tomáš Vomáčka , Prof. Dr. Ing. Ivana Kolingerová
Abstrakt CZ: Tento článek popisuje nový vyhledávací algoritmus pro lokaci bodu v triangulaci. Algoritmus kombinuje principy všech tří známých existujících technik pro lokaci bodu v rovinné triangulaci, kdy vhodnou kombinací využívá především jejich výhod a eliminuje jejich nevýhody. Experimentální výsledky potvrdily, že náš algoritmus je velmi rychlý a dostatečně robustní i pro neobvyklá data.
Abstrakt EN: Finding which triangle in a planar triangular mesh contains a query point (so-called point location problem) is one of the most frequent tasks in computational geometry. In this paper, we propose a new walking algorithm combining two existing approaches to provide speed, robustness and easy implementation, and compare it with the fastest representatives of walking algorithms. Experiments proved that our algorithm is faster than the fastest existing visibility and straight walk algorithms, and depending on the character of input data, either as fast as the orthogonal walk algorithms or faster.
Klíčová slova

Zpět

Patička