Přejít k obsahu


Straight Walk Algorithm Modification for Point location in a Trianglulation

Citace: [] SOUKAL, R., KOLINGEROVÁ, I. Straight Walk Algorithm Modification for Point location in a Trianglulation. Brussels, 2009., ISBN: neuvedeno,
Druh: Zaniklé typy
Jazyk publikace: eng
Anglický název: Straight Walk Algorithm Modification for Point location in a Trianglulation
Rok vydání: 2009
Místo konání: Brussels
Název zdroje: ULB Brussels
Autoři: Ing. Roman Soukal , Doc. Dr. Ing. Ivana Kolingerová
Abstrakt CZ: Lokace bodu je velmi často řešenou úlohou v oblasti počítačové grafiky. Efektivní lokační algoritmy používají různorodé datové struktury (DAG, skip list, quadtree, datové struktury s náhodným vzorkováním a další). Algoritmy využívající tyto datové struktury dosahují očekávané složitosti O(log n) na jeden lokalizovaný bod, kde n je celkový počet vrcholů v triangulaci. Velikou nevýhodou těchto algoritmů je to, že mají poměrně velké paměťové nároky (zpravidla O(n)), a to je limitujícím faktorem u obrovských vstupních dat (milióny bodů). Někteří programátoři tak sahají k jinému paměťově úspornějšímu řešení ? například k lokaci pomocí procházkových algoritmů. Článek představuje nový algoritmus přímé procházky, který využívá nejen modifikovaný stávající algoritmus přímé procházky, ale i algoritmus procházky dle viditelnosti.
Abstrakt EN: Finding an element in a mesh which contains a query point is a very frequent task in computational geometry. The best known algorithms use additional data structures and achieve O(log n) complexity per point query, but using of additional data structures brings some disadvantages. Generally walking algorithms are suboptimal because they do not achieve the logarithmic per point complexity. Despite this problem walking algorithms are very popular because they do not require any additional memory and their implementation is relatively simpler than the logarithmic complexity solutions. This paper brings overview of algorithms from all three known planar walking strategies (Visibility walk, Straight walk and Orthogonal walk). Our goal is to introduce algorithms of mentioned techniques and compare each of them with each other.
Klíčová slova

Zpět

Patička