Вороной и Делоне

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

Как это устроено

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

Облик мозаики решают «Точки». Случайные дают вперемешку крошечные и огромные ячейки. Пуассоновский диск ставит точки не ближе r друг к другу, но в остальном случайно — по алгоритму Бридсона: новая точка пробуется в кольце вокруг уже поставленной, до тридцати попыток. Похоже, кстати, расположены колбочки на периферии сетчатки глаза. «Релаксация» — алгоритм Ллойда: каждая точка переезжает в центр масс своей ячейки, диаграмма перестраивается, и через несколько шагов ячейки выравниваются, стремясь к шестиугольникам пчелиных сот. В режиме тайла точки живут на торе, и мозаика стыкуется без шва.

Немного истории

Такие разбиения мимоходом рисовал Декарт в 1644 году, Дирихле в 1850-м применял их к квадратичным формам, а в 1854-м лондонский врач Джон Сноу очертил на карте район, откуда ближе всего до колонки на Брод-стрит, и показал, что большинство умерших от холеры жили именно там. Общую теорию для любой размерности построил в 1908 году Георгий Вороной, а Борис Делоне в 1934-м сформулировал критерий пустой окружности. Стюарт Ллойд придумал свой алгоритм в Bell Labs в 1957 году для квантования сигналов, но опубликовал лишь в 1982-м; сегодня тот же алгоритм — стандартный способ решать задачу k-средних. Быстрый пуассоновский диск Роберт Бридсон описал в 2007 году.

Что покрутить

• Сравните «Точки» «случайные» и «пуассоновский диск», пока «Релаксация» равна 0, а потом поднимите её до 10 — ячейки почти превратятся в соты.
• «Вид» «триангуляция» показывает двойственную сетку Делоне с исходными точками, «low-poly» заливает её треугольники, а если «Раскраска» — «по шуму», выходит модная полигональная иллюстрация.
• «Вид» «точки» ставит в каждую ячейку кружок, площадь которого пропорциональна площади ячейки.
• «Зазор» и «Скругление» превращают ячейки в гальку или клетки под микроскопом.
• При виде «витраж» добавьте сверху эффект «Свечение» — стёкла засветятся, будто сквозь них бьёт солнце.