[Перевод] Алгоритм Форчуна, подробности реализации

Хабрахабр / Лучшие публикации за сутки.
Последние несколько недель я работал над реализацией алгоритма Форчуна на C++. Этот алгоритм берёт множество 2D-точек и строит из них диаграмму Вороного. Если вы не знаете, что такое диаграмма Вороного, то взгляните на рисунок:

Для каждой входной точки, которая называется «местом» (site), нам нужно найти множество точек, которые ближе к этому месту, чем ко всем остальным. Такие множества точек образуют ячейки, которые показаны на изображении выше.

В алгоритме Форчуна примечательно то, что он строит такие диаграммы за время

$O(n\log n)$

(что оптимально для использующего сравнения алгоритма), где

$n$

— это количество мест.

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

Как обычно, код выложен на github, а все использованные мной справочные материалы перечислены в конце статьи.
Читать дальше →

Добавить комментарий