Многоугольник видимости

Наивные алгоритмы легко понять и реализовать, но они не оптимальны, поскольку они могут быть существенно медленнее других алгоритмов.

В реальной жизни светящаяся точка освещает область, видимую из точки, поскольку точка излучает свет во всех направлениях. Это можно смоделировать путём проведения лучей во многих направлениях. Предположим, что имеется точка ${\displaystyle p}$ и набор препятствий ${\displaystyle S}$. Тогда псевдокод может быть выражен следующим образом:

Алгоритм простой_плохой_алгоритм(${\displaystyle p}$, ${\displaystyle S}$)
 ${\displaystyle V}$ := ${\displaystyle \emptyset }$
 для ${\displaystyle \theta =0,\cdots ,2\pi }$:
 // проводим луч с углом with angle ${\displaystyle \theta }$
   ${\displaystyle r}$ := ${\displaystyle \infty }$
   для каждого препятствия из ${\displaystyle S}$:
     ${\displaystyle r}$ := min(${\displaystyle r}$, расстояние от ${\displaystyle p}$ до препятствия в этом направлении)
   добавляем вершину ${\displaystyle (\theta ,r)}$ в ${\displaystyle V}$
 возвращаем ${\displaystyle V}$

Теперь, если была бы возможность просмотреть бесконечно много углов, результат был бы правильным. К сожалению, невозможно просмотреть все возможные направления ввиду ограничений компьютеров. Можно создать приближение путём проведения, скажем, 50 лучей равномерно. Однако это не точное решение, поскольку препятствия могут быть пропущены между двумя соседними лучами. Более того, алгоритм очень медленный, поскольку нужно проводить много лучей, а выходной многоугольник видимости может иметь много больше вершин, чем необходимо.

Описанный выше алгоритм может быть существенно улучшен как по скорости, так и по корректности путём наблюдения, что достаточно проводить лучи только к вершинам препятствий. Это потому, что любое огибание угла препятствия вдоль границы многоугольника видимости должно быть в некоторой угловой вершине препятствия.

Алгоритм простой_улучшенный_алгоритм(${\displaystyle p}$, ${\displaystyle S}$)
  ${\displaystyle V}$ := ${\displaystyle \emptyset }$
  для каждого препятствия ${\displaystyle b}$ из ${\displaystyle S}$:
    для каждой вершины ${\displaystyle v}$ of ${\displaystyle b}$:
      // проводим луч из ${\displaystyle p}$ в ${\displaystyle v}$
      ${\displaystyle r}$ := расстояние от ${\displaystyle p}$ до ${\displaystyle v}$
      ${\displaystyle \theta }$ := угол of ${\displaystyle v}$ с ${\displaystyle p}$
      для каждого препятствия ${\displaystyle b'}$ из ${\displaystyle S}$:
        ${\displaystyle r}$ := min(${\displaystyle r}$, расстояние от ${\displaystyle p}$ до ${\displaystyle b'}$)
      добавляем вершину ${\displaystyle (\theta ,r)}$ в ${\displaystyle V}$
  возвращаем ${\displaystyle V}$

Временная сложность алгоритма равна ${\displaystyle O(n^{2})}$. Это потому, что алгоритм проводит луч в каждую из ${\displaystyle n}$ вершин и проверяет, где обрывается луч. Алгоритм должен проверить пересечение с каждым из ${\displaystyle O(n)}$ препятствий. Это достаточно для многих простых приложений, таких как компьютерные игры и многие онлайновые обучающие курсы учат этому методу[8]. Однако, как мы можем видеть далее, существуют более быстрые алгоритмы со скоростью работы ${\displaystyle O(n\log n)}$ (или даже быстрее, если препятствие является простым многоугольником или имеется фиксированное число многоугольных дыр).

Многоугольник видимости для точки в центре (показана белой точкой) в простом многоугольнике, показанным чёрным цветом.

Если дан простой многоугольник ${\displaystyle {\mathcal {P}}}$ и точка ${\displaystyle p}$, алгоритм линейного времени является оптимальным для вычисления области ${\displaystyle {\mathcal {P}}}$, которая видна из точки ${\displaystyle p}$. Такой алгоритм был предложен в 1981[2]. Однако он довольно сложен. В 1983 был предложен концептуально более простой алгоритм[3], но он имел небольшую ошибку, которая была исправлена в 1987[4].

Последний упомянутый алгоритм будет кратко изложен здесь. Он просто проходит границу многоугольника ${\displaystyle {\mathcal {P}}}$, последовательно перебирая вершины, и хранит стек вершин ${\displaystyle {\mathcal {S}}=s_{0},s_{1},\cdots ,s_{t}}$, где ${\displaystyle s_{t}}$ — вершина стека. Стек состоит из вершин, видимых из ${\displaystyle p}$. Если потом обнаружатся вершины, которые закрывают часть ${\displaystyle {\mathcal {S}}}$, то закрытые вершины выталкиваются из стека ${\displaystyle {\mathcal {S}}}$. Алгоритм прекращает работу, когда ${\displaystyle {\mathcal {S}}}$ состоит из всех видимых вершин, то есть из желаемого многоугольника видимости. Эффективная реализация была опубликована в 2014[9].

Для точки в многоугольнике с ${\displaystyle h}$ дырами и ${\displaystyle n}$ вершинами (в сумме) можно показать, что в худшем случае алгоритм ${\displaystyle \Theta (n+h\log h)}$ оптимален. Такой алгоритм был предложен в 1995 вместе с доказательством его оптимальности[10]. Однако этот алгоритм опирается на алгоритм линейного времени триангуляризации многоугольника Чазелле, который крайне сложен.

Многоугольник видимости для точки в центре (показана белым цветом) среди набора произвольных отрезков на плоскости, которые могут пересекаться только нa концах, выступающих в роли препятствий (показаны чёрным).

Для точки среди множества из ${\displaystyle n}$ отрезков, которые могут пересекаться только на их концах, можно показать, что в худшем случае алгоритм со временем работы ${\displaystyle \Theta (n\log n)}$ оптимален. Это потому, что алгоритм многоугольника видимости должен выводить вершины многоугольника видимости в отсортированном порядке, а следовательно, задача сортировки может быть сведена к вычислению многоугольника видимости[11].

Заметим, что любой алгоритм, который вычисляет многоугольник видимости, для точки среди отрезков может быть использован для вычисления многоугольника видимости для всех видов многоугольных препятствий, поскольку многоугольник может быть разбит на отрезки.

Алгоритм «Разделяй и властвуй» для вычисления многоугольника видимости был предложен в 1987[12].

Угловое выметание, то есть вращательный алгоритм выметающей прямой для вычисления многоугольника видимости был предложен в 1985[13] и 1986[11]. Идея заключается в начальной сортировке концов отрезков по углу, а затем просмотре отсортированных точек. Во время итерирования события обрабатываются как куча. Эффективная реализация была опубликована в 2014[9].

Для точки среди отрезков, пересекающихся произвольным образом, задача о многоугольнике видимости сводится за линейное время к задаче о нижней огибающей. Согласно доводам Дэвенпорта — Шинцеля вычисление нижней огибающей в худшем случае имеет сложность ${\displaystyle \Theta (n\alpha (n))}$ от числа вершин, где ${\displaystyle \alpha (n)}$ — обратная функции Аккермана. Оптимальный в худшем случае алгоритм «разделяй и властвуй», работающий за время ${\displaystyle \Theta (n\log n)}$, создал Джон Хершбергер в 1989[14].

• VisiLibity: A free open source C++ library for visibility computations in planar polygonal environments.
• visibility-polygon-js: A public domain Javascript library for computing многоугольник видимости for a point among segments using the Угловое выметание method.