TřiVis: Versatile, Reliable, and High-Performance Tool for Computing Visibility in Polygonal Environments

Abstract

Visibility is a fundamental concept in computational geometry, with numerous applications in surveillance, robotics, and games. This software paper presents TřiVis, a C++ library developed by the authors for computing numerous visibility-related queries in highly complex polygonal environments. Adapting the triangular expansion algorithm, TřiVis stands out as a versatile, high-performance, more reliable and easy-to-use alternative to current solutions that is also free of heavy dependencies. Through evaluation on a challenging dataset, TřiVis has been benchmarked against existing visibility libraries. The results demonstrate that TřiVis outperforms the competing solutions by at least an order of magnitude in query times, while exhibiting more reliable runtime behavior. TřiVis is freely available for private, research, and institutional use at https://github.com/janmikulacz/trivis.

8 pages, 12 figures (including subfigures); accepted to appear at the 2024 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS); associated repository: https://github.com/janmikulacz/trivis