Многоугольник видимости
Многоугольник, покрывающий всё, что наблюдатель видит из заданной точки, ограниченный препятствиями сцены.
Его строят, пуская лучи в каждую вершину окружающих рёбер — плюс пару лучей чуть в стороне от вершины, чтобы поймать то, что выглядывает из-за неё, — и соединяя точки попаданий в порядке угла. Получается звёздчатая область, выглядящая в точности как свет точечного источника в комнате со стенами.
Применяется для 2D-поля зрения, тумана войны, конусов обзора стражников и мягких 2D-теней в играх вроде Monaco и Teleglitch. Близок к линии видимости, но проверка линии видимости отвечает «да/нет» для одной цели, а многоугольник видимости вычисляет всю видимую область сразу. Наивная версия — O(n log n) по числу вершин.