The problem of off-road routing and terrain discretization with using visibility graphs is considered. Traditionally, routing engines find a path over a road graph, but the problem of off-road routing is also relevant. A polygon approximation method is proposed as applied to constructing a visibility graph on a plane, as well as pathfinding without constructing a complete graph for solving the problem of off-road navigation. The developed algorithm for finding supporting lines to a convex polygon on a plane and a hierarchical approach to building a visibility graph are described. The considered approaches are implemented in a software system and applied to real geographic data.

navigation system, computational geometry, visibility graph

Kozub Denis Vladimirovich,  ,  orcid.org/0000-0001-9317-4680,  Lomonosov Moscow State University

Korukhova Yulia Stanislavovna,  ,  orcid.org/0000-0001-5221-5730,  Lomonosov Moscow State University