Алгоритм Форчуна

Анимация алгоритма Форчуна

Алгоритм Форчуна — это алгоритм заметающей прямой для генерации диаграммы Вороного из набора точек на плоскости за время O$(n\log n)$ с использованием памяти O(n)Шаблон:SfnШаблон:Sfn. Алгоритм первоначально опубликовал Стивен Форчун в 1986 в своей статье «Алгоритм заметающей прямой для диаграмм Вороного»Шаблон:Sfn.

Описание алгоритма

Алгоритм поддерживает заметающую прямую и береговую линию, которые двигаются по плоскости в процессе работы алгоритма. Заметающая прямая — это прямая, которую мы по традиции можем считать вертикальной и движущейся слева направо. В любой момент работы алгоритма точки из набора слева от заметающей прямой будут включены в диаграмму Вороного, в то время как точки справа от заметающей прямой ещё не отработаны. Береговая линия не является прямой, а является сложной, состоящей из кусочков парабол, кусочно-заданной кривой слева от заметающей прямой. Она отделяет порцию плоскости, внутри которой диаграмма Вороного может быть известна, независимо от других точек справа от заметающей прямой. Для каждой точки слева от заметающей прямой можно определить параболу для точки, которая равноудалена как от этой точки, так и от заметающей прямой. Береговая линия — это граница объединений этих парабол. По мере движения прямой вершины береговой линии, в которых две параболы пересекаются, вычерчивают рёбра диаграммы Вороного. Береговая линия продвигается, сохраняя основание каждой параболы в точности на половину пути между начальным положением заметающей прямой и новой позицией заметающей прямой. Математически это значит, что каждая парабола образуется с помощью заметающей прямой как директрисы, а заданная точка из набора служит фокусом.

Алгоритм поддерживает структуру данных двоичного дерева, описывающего комбинаторную структуру береговой линии, и очередь с приоритетом, перечисляющую потенциальные события в будущем, которые могли бы изменить структуру береговой линии. Эти события включают добавление другой параболы в береговую линию (когда заметающая прямая проходит через другую входную точку) и удаление кривой из береговой линии (когда заметающая прямая становится касательной к окружности через некоторые три входных точки, параболы которых образуют последовательные сегменты береговой линии). Каждому такому событию может быть присвоен приоритет по x-координате заметающей прямой в точке, где событие произошло. Алгоритм состоит из последовательного удаления события из очереди с приоритетом, нахождения изменений событий в береговой линии и обновление структуры данных.

Так как имеется O(n) событий для обработки (каждое ассоциировано с некоторым свойством диаграммы Вороного) и времени O(log n) для обработки события (которое состоит из постоянного числа поисков по двоичному дереву и операций очереди с приоритетом), общее время равно $O(n\log n)$.

Псевдокод

Псевдокод алгоритмаШаблон:Sfn.

Пусть $*(z)$ будет преобразованием $*(z)=(z_x,z_y+d(z))$,
  где $d(z)$ — евклидово расстояние между  Шаблон:Mvar и ближайшей точкой
Пусть Шаблон:Mvar будет «береговой линией»
Пусть $R_p$ будет областью, покрывающей точку Шаблон:Mvar.
Пусть $C_{pq}$ будет граничным лучом между точками Шаблон:Mvar и Шаблон:Mvar.
Пусть $p_1,p_2,...,p_m$ будут точками с минимальной Шаблон:Mvar-координатой, упорядоченными по Шаблон:Mvar-координате
$Q\leftarrow S-p_1,p_2,...,p_m$
создаёт начальные вертикальные граничные лучи $C_{p_1,p_2}^0,C_{p_2,p_3}^0,...C_{p_{m-1},p_m}^0$
$T\leftarrow *(R_{p_1}),C_{p_1,p_2}^0,*(R_{p_2}),C_{p_2,p_3}^0,...,*(R_{p_{m-1}}),C_{p_{m-1},p_m}^0,*(R_{p_m})$
пока не IsEmpty(Шаблон:Mvar) выполнить
    $p\leftarrow \mathrm{D}\mathrm{e}\mathrm{l}\mathrm{e}\mathrm{t}\mathrm{e}\mathrm{M}\mathrm{i}\mathrm{n}(Q)$
    в случае если 
    Шаблон:Mvar является точкой в $*(V)$:
        Находим область $*(R_q)$ в Шаблон:Mvar, содержащую Шаблон:Mvar,
          ограниченную кривой $C_{rq}$ слева и кривой $C_{qs}$ справа
        создаём новые граничные лучи $C_{pq}^{-}$ и $C_{pq}^{+}$ с основанием Шаблон:Mvar
        заменяем $*(R_q)$ на $*(R_q),C_{pq}^{-},*(R_p),C_{pq}^{+},*(R_q)$ в Шаблон:Mvar
        удаляем из Шаблон:Mvar любое пересечение между $C_{rq}$ и $C_{qs}$
        вставляем в Шаблон:Mvar любое пересечение $C_{rq}$ и $C_{pq}^{-}$
        вставляем в Шаблон:Mvar любое пересечение $C_{pq}^{+}$ и $C_{qs}$
    Шаблон:Mvar является вершиной Вороного в $*(V)$:
        пусть Шаблон:Mvar будет пересечением $C_{qr}$ слева и $C_{rs}$ справа
        пусть $C_{uq}$ будет левым соседом $C_{qr}$ и
          пусть $C_{sv}$ будет правым соседом $C_{rs}$ в Шаблон:Mvar
        создаём новый граничный луч $C_{qs}^0$, если $q_y=s_y$,
          или создаём $C_{qs}^{+}$, если Шаблон:Mvar правая часть более высокой  из Шаблон:Mvar и Шаблон:Mvar,
          в противном случае создаём $C_{qs}^{-}$
        заменяем $C_{qr},*(R_r),C_{rs}$ на вновь созданную $C_{qs}$ в Шаблон:Mvar
        удаляем из Шаблон:Mvar любое пересечение $C_{uq}$ и $C_{qr}$
        удаляем из Шаблон:Mvar любое пересечение $C_{rs}$ и $C_{sv}$
        вставляем в Шаблон:Mvar любое пересечение $C_{uq}$ и $C_{qs}$
        вставляем в Шаблон:Mvar любое пересечение $C_{qs}$ и $C_{sv}$
        записываем Шаблон:Mvar как вершину $C_{qr}$ и $C_{rs}$ и основание $C_{qs}$
        выводим сегменты границ $C_{qr}$ и $C_{rs}$
    конец в случае
конец пока
выводим оставшиеся граничные лучи из Шаблон:Mvar

Взвешенные стороны и диски

Как указывает ФорчунШаблон:Sfn, модифицированная версия алгоритма заметающей прямой может быть использована для построения аддитивно взвешенной диаграммы Вороного, в которой расстояние до каждой точки нейтрализуется весом точки. Это можно рассматривать эквивалентно как диаграмма Вороного набора дисков с центрами в точках и радиусом, равным весу точки.

Взвешенные точки можно использовать для контроля площадей ячеек Вороного, когда диаграммы Вороного используются для построения Шаблон:Не переведено 5. В аддитивно взвешенной диаграмме Вороного биссектрисой между точками в общем случае является гипербола, в противоположность невзвешенным диаграммам Вороного и Шаблон:Не переведено 5 дисков, для которых это прямая.

Литература

• Шаблон:Книга
• Шаблон:Статья
• Шаблон:Книга SpringerLinkШаблон:Недоступная ссылка
• Шаблон:Статья

Ссылки

• Реализация Стивена Форчуна на C
• Алгоритм Форчуна для диаграмм Вороного, реализованный на C++
• Алгоритм Форчуна, реализованный на JavaScript