Optimizing Mesh to Improve the Triangular Expansion Algorithm for Computing Visibility Regions

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F24%3A00372268" target="_blank" >RIV/68407700:21230/24:00372268 - isvavai.cz</a>

Nalezeny alternativní kódy

RIV/68407700:21730/24:00372268

Výsledek na webu

<a href="https://doi.org/10.1007/s42979-023-02561-y" target="_blank" >https://doi.org/10.1007/s42979-023-02561-y</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/s42979-023-02561-y" target="_blank" >10.1007/s42979-023-02561-y</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Optimizing Mesh to Improve the Triangular Expansion Algorithm for Computing Visibility Regions

Popis výsledku v původním jazyce

This paper addresses the problem of improving the query performance of the triangular expansion algorithm (TEA) for computing visibility regions by finding the most advantageous instance of the triangular mesh, the preprocessing structure. The TEA recursively traverses the mesh while keeping track of the visible region—the set of all points visible from a query point in a polygonal world. We show that the measured query time is approximately proportional to the number of triangle edge expansions during the mesh traversal. We propose a new type of triangular mesh that minimizes the expected number of expansions assuming the query points are drawn from a known probability distribution. We design a heuristic method to approximate the mesh and evaluate the approach on many challenging instances that resemble real-world environments. The proposed mesh improves the mean query times by 12–16% compared to the reference constrained Delaunay triangulation. The approach is suitable to boost offline applications that require computing millions of queries without addressing the preprocessing time. The implementation is publicly available to replicate our experiments and serve the community.

Název v anglickém jazyce

Optimizing Mesh to Improve the Triangular Expansion Algorithm for Computing Visibility Regions

Popis výsledku anglicky

This paper addresses the problem of improving the query performance of the triangular expansion algorithm (TEA) for computing visibility regions by finding the most advantageous instance of the triangular mesh, the preprocessing structure. The TEA recursively traverses the mesh while keeping track of the visible region—the set of all points visible from a query point in a polygonal world. We show that the measured query time is approximately proportional to the number of triangle edge expansions during the mesh traversal. We propose a new type of triangular mesh that minimizes the expected number of expansions assuming the query points are drawn from a known probability distribution. We design a heuristic method to approximate the mesh and evaluate the approach on many challenging instances that resemble real-world environments. The proposed mesh improves the mean query times by 12–16% compared to the reference constrained Delaunay triangulation. The approach is suitable to boost offline applications that require computing millions of queries without addressing the preprocessing time. The implementation is publicly available to replicate our experiments and serve the community.

Druh

J_SC - Článek v periodiku v databázi SCOPUS

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

<a href="/cs/project/EH22_008%2F0004590" target="_blank" >EH22_008/0004590: Robotika a pokročilá průmyslová výroba</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í

2024

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 periodika

SN Computer Science

ISSN

2661-8907

e-ISSN

—

Svazek periodika

5

Číslo periodika v rámci svazku

2

Stát vydavatele periodika

SG - Singapurská republika

Počet stran výsledku

21

Strana od-do

—

Kód UT WoS článku

—

EID výsledku v databázi Scopus

2-s2.0-85188347052