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

Многоугольник видимости показан жёлтым цветом. Четыре препятствия показаны синим цветом.

Многоугольник видимости или область видимости для точки p на плоскости среди препятствий — это (возможно неограниченная) многоугольная область всех точек плоскости, видимых из точки p. Многоугольник видимости можно определить для видимости из отрезка или многоугольника. Многоугольники видимости полезны в робототехнике, компьютерных играх и для определения позиций объектов, например, для определения наилучшего расположения охраны в картинных галереях.

Если многоугольник видимости ограничен, то он является звёздчатым многоугольником. Многоугольник видимости ограничен, если все лучи, проведённые из точки, в конце концов, обрываются на некотором препятствии. Это случается, например, когда препятствия являются рёбрами простого многоугольника, а точка p находится внутри многоугольника. В таком случае многоугольник видимости может быть найден за линейное время.

Определения

Формально мы можем определить задачу о планарном многоугольнике видимости следующим образом. Пусть $S$ будет набором препятствий (отрезки, либо многоугольники) в $\mathbb {R} ^{2}$. Пусть $p$ будет точкой в $\mathbb {R} ^{2}$, не находящейся внутри препятствия. Тогда многоугольник видимости точки $V$ — это множество точек в $\mathbb {R} ^{2}$, таких, что для любой точки $q$ из $V$ отрезок $pq$ не пересекает какой-либо объект из набора $S$.

Аналогично, многоугольник видимости отрезка или многоугольник видимости ребра — это точки, видимые с любого места отрезка.

Приложения

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

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

Алгоритмы для точек видимости многоугольников

Было предложено много алгоритмов вычисления многоугольника видимости для точки. Для различных вариантов задачи (то есть различных видов препятствий) алгоритмы могут отличаться по времени и сложности.

Наивные алгоритмы

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

«Физический» алгоритм равномерного проведения лучей

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

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

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

Проведение луча в каждую вершину

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

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

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

Оптимальные алгоритмы для точек в простом многоугольнике

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

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

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

Оптимальные алгоритмы для точек многоугольника с дырами

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

Оптимальные алгоритмы для точки среди отрезков

Отрезки, которые могут пересекаться только на концах

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

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

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

Разделяй и властвуй

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

Угловое выметание

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

Произвольно пересекающиеся отрезки

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

Ссылки

• https://web.archive.org/web/20170503033619/http://web.informatik.uni-bonn.de/I/GeomLab/VisPolygon/index.html.en (видимость в простых многоугольниках — апплеты)

Программное обеспечение

• 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.