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

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

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

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

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

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

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

Псевдокод

Псевдокод алгоритма.

Пусть $*(z)$ будет преобразованием $*(z)=(z_{x},z_{y}+d(z))$,
  где $d(z)$ — евклидово расстояние между  z и ближайшей точкой
Пусть T будет «береговой линией»
Пусть $R_{p}$ будет областью, покрывающей точку p.
Пусть $C_{pq}$ будет граничным лучом между точками p и q.
Пусть $p_{1},p_{2},...,p_{m}$ будут точками с минимальной y-координатой, упорядоченными по x-координате
$Q\gets 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\gets *(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(Q) выполнить
    $p\gets \mathrm {DeleteMin} (Q)$
    в случае если 
    p является точкой в $*(V)$:
        Находим область $*(R_{q})$ в T, содержащую p,
          ограниченную кривой $C_{rq}$ слева и кривой $C_{qs}$ справа
        создаём новые граничные лучи $C_{pq}^{-}$ и $C_{pq}^{+}$ с основанием p
        заменяем $*(R_{q})$ на $*(R_{q}),C_{pq}^{-},*(R_{p}),C_{pq}^{+},*(R_{q})$ в T
        удаляем из Q любое пересечение между $C_{rq}$ и $C_{qs}$
        вставляем в Q любое пересечение $C_{rq}$ и $C_{pq}^{-}$
        вставляем в Q любое пересечение $C_{pq}^{+}$ и $C_{qs}$
    p является вершиной Вороного в $*(V)$:
        пусть p будет пересечением $C_{qr}$ слева и $C_{rs}$ справа
        пусть $C_{uq}$ будет левым соседом $C_{qr}$ и
          пусть $C_{sv}$ будет правым соседом $C_{rs}$ в T
        создаём новый граничный луч $C_{qs}^{0}$, если $q_{y}=s_{y}$,
          или создаём $C_{qs}^{+}$, если p правая часть более высокой  из q и s,
          в противном случае создаём $C_{qs}^{-}$
        заменяем $C_{qr},*(R_{r}),C_{rs}$ на вновь созданную $C_{qs}$ в T
        удаляем из Q любое пересечение $C_{uq}$ и $C_{qr}$
        удаляем из Q любое пересечение $C_{rs}$ и $C_{sv}$
        вставляем в Q любое пересечение $C_{uq}$ и $C_{qs}$
        вставляем в Q любое пересечение $C_{qs}$ и $C_{sv}$
        записываем p как вершину $C_{qr}$ и $C_{rs}$ и основание $C_{qs}$
        выводим сегменты границ $C_{qr}$ и $C_{rs}$
    конец в случае
конец пока
выводим оставшиеся граничные лучи из T

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

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

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

Ссылки

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