Triangular Expansion Revisited: Which Triangulation Is The Best?

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F22%3A00358786" target="_blank" >RIV/68407700:21230/22:00358786 - isvavai.cz</a>

Nalezeny alternativní kódy

RIV/68407700:21730/22:00358786

Výsledek na webu

<a href="https://doi.org/10.5220/0011278700003271" target="_blank" >https://doi.org/10.5220/0011278700003271</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.5220/0011278700003271" target="_blank" >10.5220/0011278700003271</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Triangular Expansion Revisited: Which Triangulation Is The Best?

Popis výsledku v původním jazyce

Visibility region is a classic structure in computational geometry that finds use in many agent planning problems. Triangular expansion algorithm (TEA) is the state-of-the-art algorithm for computing visibility regions within polygons with holes in two dimensions. It has been shown that it is two orders of magnitude faster than the traditional rotation sweep algorithm for real-world scenarios. The algorithm triangulates the underlying polygon and recursively traverses the triangulation while keeping track of the visible region. Instead of the constraint Delaunay triangulation used by default, this paper introduces the idea of optimizing the triangulation to minimize the expected number of triangle edges expanded during the TEA’s traversal while assuming that every point of the input polygon is equally likely to be queried. The proposed triangulation is experimentally evaluated and shown to improve TEA’s mean query time in practice. Furthermore, the TEA is modified to consider limited visibility range of real-life sensors. Combined with the proposed triangulation, this adjustment significantly speeds up the computation in scenarios with limited visibility. We provide an efficient open-source implementation called TriVis which, besides the mentioned, includes determining visibility between two points and other useful visibility-related operations.

Název v anglickém jazyce

Triangular Expansion Revisited: Which Triangulation Is The Best?

Popis výsledku anglicky

Visibility region is a classic structure in computational geometry that finds use in many agent planning problems. Triangular expansion algorithm (TEA) is the state-of-the-art algorithm for computing visibility regions within polygons with holes in two dimensions. It has been shown that it is two orders of magnitude faster than the traditional rotation sweep algorithm for real-world scenarios. The algorithm triangulates the underlying polygon and recursively traverses the triangulation while keeping track of the visible region. Instead of the constraint Delaunay triangulation used by default, this paper introduces the idea of optimizing the triangulation to minimize the expected number of triangle edges expanded during the TEA’s traversal while assuming that every point of the input polygon is equally likely to be queried. The proposed triangulation is experimentally evaluated and shown to improve TEA’s mean query time in practice. Furthermore, the TEA is modified to consider limited visibility range of real-life sensors. Combined with the proposed triangulation, this adjustment significantly speeds up the computation in scenarios with limited visibility. We provide an efficient open-source implementation called TriVis which, besides the mentioned, includes determining visibility between two points and other useful visibility-related operations.

Druh

D - Stať ve sborníku

CEP obor

—

OECD FORD obor

20204 - Robotics and automatic control

Projekt

<a href="/cs/project/EF15_003%2F0000470" target="_blank" >EF15_003/0000470: Robotika pro Průmysl 4.0</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>S - Specificky vyzkum na vysokych skolach

Rok uplatnění

2022

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

Proceedings of the 19th International Conference on Informatics in Control, Automation and Robotics - ICINCO

ISBN

978-989-758-585-2

ISSN

—

e-ISSN

2184-2809

Počet stran výsledku

7

Strana od-do

313-319

Název nakladatele

Science and Technology Publications, Lda

Místo vydání

Setúbal

Místo konání akce

Lisbon

Datum konání akce

14. 7. 2022

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

000852751300035