Алгоритм Фортуны - Википедия - Fortunes algorithm

Анимация алгоритма фортуны

Алгоритм фортуны это алгоритм линии развертки для создания Диаграмма Вороного из набора точек на плоскости с помощью О (п бревноп) время и O (п) Космос.^[1]^[2] Первоначально он был опубликован Стивен Форчун в 1986 г. в своей статье «Алгоритм Sweepline для диаграмм Вороного».^[3]

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

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

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

Поскольку есть O (п) событий для обработки (каждое из которых связано с какой-либо функцией диаграммы Вороного) и O (журнал п) время обработки события (каждое из которых состоит из постоянного числа операций двоичного дерева поиска и приоритетной очереди), общее время составляет O (п бревно п).

Псевдокод

Псевдокод описание алгоритма.^[4]

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

Взвешенные сайты и диски

Как описывает Fortune в исх. ^[1]модифицированная версия алгоритма развертки линии может быть использована для построения диаграммы Вороного с аддитивным взвешиванием, в которой расстояние до каждого сайта смещено на вес сайта; это можно эквивалентно рассматривать как диаграмму Вороного набора дисков, центрированных в узлах с радиусом, равным его весу.

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

внешняя ссылка

[Mark2000-1] а ^б де Берг, Марк; ван Кревельд, Марк; Овермарс, Марк; Шварцкопф, Отфрид (2000), Вычислительная геометрия (2-е изд. Перераб.), Springer-Verlag, ISBN 3-540-65620-0 Раздел 7.2: Вычисление диаграммы Вороного: стр. 151–160.

[2] Остин, Дэвид, Диаграммы Вороного и день на пляже, Столбец функций, Американское математическое общество.

[3] Стивен Форчун. Алгоритм Sweepline для диаграмм Вороного. Материалы второго ежегодного симпозиума по вычислительной геометрии.. Yorktown Heights, Нью-Йорк, США, стр. 313–322. 1986 г. ISBN 0-89791-194-6. Цифровая библиотека ACM SpringerLink

[4] Кенни Вонг, Хауси А. Мюллер, Эффективная реализация алгоритма развертки Фортуны для диаграмм Вороного, CiteSeerX 10.1.1.83.5571.

[1]

[2]

[3]

[4]

Алгоритм Фортуны - Википедия - Fortunes algorithm

Содержание

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

Псевдокод

Взвешенные сайты и диски

Рекомендации

внешняя ссылка