visibilitygraph.hpp File Reference

Visibility graphs by triangular expansion. More...

#include "algorithm/graph.hpp"
#include <compare>
#include <cstddef>
#include <cstdint>
#include <vector>

Go to the source code of this file.

Namespaces
namespace	pgl

Detailed Description

Visibility graphs by triangular expansion.

One traversal of the triangulated domain per vertex, carrying a cone of still unobstructed directions that every crossed diagonal clips. The cone is held as a pair of vertices rather than as materialized rays, so the whole algorithm is orientation predicates on stored points: nothing is constructed, and an exact coordinate type stays exact and never grows.

The three graphs share that expansion. Clear visibility is what it computes directly. Full visibility is clear visibility plus the mesh's own blocking edges — together the pairs that see each other with no vertex in between — closed along collinear chains, since a segment through a vertex stays in the domain exactly when both halves do. Reduced visibility filters the full graph by tangency at both endpoints.