Теперь, когда мы знаем немного больше о том, что такое диаграммы Вороного, и об их особенностях, давайте углубимся в лучший способ их вычисления, который представляет собой алгоритм развертки плоскости, вдохновленный работой Стивена Форчуна.
Алгоритм развертки плоскости
Развертка плоской линии — тип алгоритма, широко используемый в вычислительной геометрии. Идея заключается в том, чтобы иметь линию, которая перемещает план в одном направлении — вертикально или горизонтально — и выполняет операцию всякий раз, когда линия сталкивается с точкой.
Применительно к нашей проблеме Вороного у нас возникло бы искушение сказать что-то вроде «когда линия встречает семя, мы создаем его область Вороного». Проблема в том, что когда мы находимся на определенном семени, у нас все равно нет возможности узнать, где начинается и заканчивается его регион. Нам нужно немного пошалить.
Параболы
Одним из решений этой проблемы является использование парабол. Почему параболы?
Что ж, параболы часто известны по их уравнениям в форме y = ax² + bx + c, где a является постоянной и отличной от нуля.
Но есть и другой способ их определения. Парабола может быть построена с использованием одной точки, называемой фокусом, и линии, называемой директрисой. При использовании этих двух элементов парабола состоит из всех точек, равноудаленных от фокуса и от ближайшей точки на директрисе.
Важной частью здесь является слово «эквидистантный», оно будет очень полезно для создания ребер Вороного.
Пляжная линия
Зная, что теперь мы можем изменить наш подход к алгоритму развертки. Всякий раз, когда мы сталкиваемся с семенем, мы создаем новую параболу. Его фокус будет семенем, а его направляющей будет сама линия развертки. Мы сохраним в памяти список всех существующих дуг, которые назовем береговой линией.
Визуально береговая линия состоит из ряда смежных парабол разного размера, что напоминает линии, проведенные водой на пляже, отсюда и название.
Строительство кромок
Когда вы добавляете новую параболу к линии пляжа, сначала это будет вертикальная линия, которая будет пересекаться с другой параболой в одной точке, учитывая, что линия пляжа не пуста. Эта точка является началом ребра Вороного. Когда линия развертки продолжится, будет создана парабола, которая будет расти. Эта парабола пересекается с другой параболой. По определению точка пересечения теперь равноудалена от фокусных точек обеих парабол. Точка является частью ребра Вороного между двумя точками фокусировки. По мере того, как линия развертки продолжается, а параболы растут, точки пересечения будут перемещаться, и по этим точкам строятся края.
Обработка края / Закрытие области
Визуально, когда линия перемещается, мы можем видеть, что в некоторых точках несколько ребер сойдутся в одну точку, а одна или несколько дуг параболы полностью исчезнут. От этой точки схождения оставшиеся параболические дуги встретятся и начнут новое ребро.
Потенциальные кандидаты на вершину
Всякий раз, когда мы добавляем новую дугу, мы можем искать возможные вершины-кандидаты. Нам просто нужно найти центр описанной окружности только что добавленного участка и две его предыдущие дуги, а затем центр описанной окружности вновь добавленной и двух следующих дуг. Если они есть конечно. Нам не нужно проверять случай, когда вновь добавленная точка находится посередине, потому что созданные ребра будут расходиться.
И в этом вся хитрость. Для каждой потенциальной вершины мы проверяем, сходятся ли созданные дуги. Если это не так, значит, вершина находится выше береговой линии и уже пройдена, учитывая, что плоскость заметается сверху вниз.
Описание алгоритма
Теперь у нас есть все необходимое для простого описания алгоритма:
- Создайте приоритетную очередь, содержащую все сайты. Плоскость заметается сверху вниз, поэтому мы хотим, чтобы очередь сортировалась по убыванию координат y.
- Пока очередь не пуста
- Возьмите первый элемент
- Если элемент представляет собой участок, добавьте новую параболу с фокусом на эту точку к линии пляжа. Затем проверьте возможные вершины и добавьте их в очередь приоритетов. Создайте полуребра пересечений.
- Если элемент является вершиной, это означает, что дуга исчезает. Удалите его с береговой линии, закончите края относительно него и создайте новые, начиная с него. Затем проверьте возможные вершины между новыми соседними дугами и добавьте их в очередь событий.
- Когда очередь событий пуста, дело сделано. Если вам нужно отобразить график, вам придется связать диаграмму, чтобы иметь возможность отображать «бесконечные» ребра — те, что из неограниченных регионов.
Вот и все, что касается глобальной идеи. В следующей статье мы обсудим, как это реализовать. Это не так просто, как кажется, и я все еще в процессе завершения, так что статья может занять некоторое время, прежде чем она появится, но она обязательно появится.
Предыдущая статья из цикла:
Ссылки, использованные при написании этой статьи:
Вычислительная геометрия: алгоритмы и приложения, Марк ван Кревельд, Марк де Берг, Марк Овермарс.
https://www.desmos.com/calculator Для создания изображений
