Přejít k obsahu


Construction of Pseudo-triangulation by Incremental Insertion

Citace: [] KOLINGEROVÁ, I., TRČKA, J., HOBZA, L. Construction of Pseudo-triangulation by Incremental Insertion. In Computational Science and Its Applications - ICCSA 2011. Berlin: Springer, 2011. s. 30-43. ISBN: 978-3-642-21930-6 , ISSN: 0302-9743
Druh: STAŤ VE SBORNÍKU
Jazyk publikace: eng
Anglický název: Construction of Pseudo-triangulation by Incremental Insertion
Rok vydání: 2011
Místo konání: Berlin
Název zdroje: Springer
Autoři: Prof. Dr. Ing. Ivana Kolingerová , Jan Trčka , Ladislav Hobza
Abstrakt CZ: Pseudo-triangulace je dělení roviny na pseudo-trojúhelníky - polygony se třemi konvexními vrcholy, užívané především v problémech plánování pohybu v robotice. Protože jde o poměrně nový koncept, neexistuje mnoho algoritmů konstrukce. V tomto článku navrhujeme online verzi inkrementálního vkládání, se zobecněnými flipy pro zlepšení tvaru pseudo-trojúhelníků. Toto algoritmické paradigma se často využívá v Delaunayho triangulacích, ale pro pseudo-triangulace bylo využito zatím jen v off-line verzi (pro seřazené vstupní body). Experimentovali jsme také s několika optimalizačními kritérii pro flipy a ukazujeme jejich vliv na tvar pseudo-trojúhelníků.
Abstrakt EN: A pseudo-triangulation is a planar subdivision into pseudotriangles - polygons with three convex vertices, used mainly in motion planning problems in robotics. As it is a rather new concept, not too many algorithms to construct it exist. In this paper, we propose an online version of ncremental insertion, with generalized flips to improve the shape of pseudo-triangles. This algorithmic paradigm is often used for Delaunay triangulations, but for pseudo-triangulations it has been used only in an off-line version (for sorted input points). We also experimented with several optimization criteria for the flips and show their influence on the shape of pseudo-triangles.
Klíčová slova

Zpět

Patička