WikiSort.ru - Не сортированное

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

В реальной жизни светящаяся точка освещает область, видимую из точки, поскольку точка излучает свет во всех направлениях. Это можно смоделировать путём проведения лучей во многих направлениях. Предположим, что имеется точка ${\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 n}$ отрезков, которые могут пересекаться только на их концах, можно показать, что в худшем случае алгоритм со временем работы ${\displaystyle \Theta (n\log n)}$ оптимален. Это потому, что алгоритм многоугольника видимости должен выводить вершины многоугольника видимости в отсортированном порядке, а следовательно задача сортировки может быть сведена к вычислению многоугольника видимости^[11].

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

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

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