Береговая линия и диаграммы Воронова

Жил-был алгоритм Форчуна, который умел делить плоскость на территории с помощью береговой линии и заметающей прямой. Сегодня я о нём узнал и решил поделиться

Основная идея довольно хитрая: линия ползёт от одного края к другому и "пробуждает" точки по пути. Проснувшаяся точка выпускает параболу, которая растёт и толкается с соседями. Там где столкнётся получаются прямые

Параболы встречаются и образуют береговую линию — граница зон близости к центу точек. Каждая зона разбивается так что из любой точки внутри зоны ей ближе к точке-центру

Алгоритм прикольный, пришлось повозиться пока делал, но описан довольно хорошо. Ну и название прикольное, если вы понимаете о чём я. Вообще, вся эта вычислительная геометрия удивительно увлекательная штука, рекомендую! А вот тут тыкетсо: https://g.moose.rodeo/fortunes-algorithm