Генератор диаграмм Вороного

Генератор диаграмм Вороного разбивает 2D-плоскость на области на основе близости к заданному множеству начальных точек. Каждая точка на плоскости принадлежит ячейке той начальной точки, которая является к ней ближайшей, поэтому диаграмма выглядит как мозаика из ячеек вокруг входных точек. Этот инструмент генерирует диаграммы Вороного интерактивно прямо в вашем браузере — добавляйте новые точки кликом мыши, перетаскивайте любую точку для перерисовки ячеек в реальном времени, переключайтесь между четырьмя метриками расстояния и применяйте релаксацию Ллойда для выравнивания размеров ячеек. Экспортируйте результат в четкий формат SVG или готовый для публикации PNG.

Четыре метрики расстояния — визуализация

Форма каждой ячейки Вороного определяется тем, какую метрику расстояния вы используете. Каждая метрика определяет, как выглядит «окружность» — и форма этой окружности в точности соответствует форме, которая сталкивается со своими соседями, образуя границы ячеек.

Именно поэтому ячейки в метрике Манхэттена имеют только горизонтальные, вертикальные и расположенные под углом 45° края, в то время как ячейки Чебышёва имеют только горизонтальные и вертикальные края — граница между двумя ячейками всегда касается форм этих двух «окружностей». Евклидова метрика дает классическую диаграмму Вороного с криволинейными краями, которую все ассоциируют с этим названием. Метрика Минковского p=3 — это математически элегантный промежуточный случай, используемый в вычислительном дизайне, когда углы L1 кажутся слишком резкими, а окружности L2 — слишком круглыми.

Что делает этот генератор особенным

Где применяются диаграммы Вороного

• Карты покрытия вышек сотовой связи — телефон подключается к той вышке, к которой он ближе всего, что как раз соответствует ячейке Вороного для этой вышки.
• Карта холеры Джона Сноу 1854 года — Сноу нарисовал ячейку Вороного вокруг каждого водяного насоса в Сохо и подсчитал количество смертей от холеры внутри каждой ячейки, что позволило изолировать зараженный насос на Брод-стрит.
• Процедурное текстурирование — шум Ворлея (клеточный шум) используется во всем: от шейдеров кожи до генерации ландшафтов в таких играх, как Minecraft и No Man's Sky.
• Генерация сеток — решатели метода конечных элементов предпочитают треугольники, близкие к равносторонним, а триангуляция Делоне (дуальная к диаграмме Вороного) максимизирует минимальный угол среди всех треугольников.
• Планирование траекторий роботов — ребра диаграммы Вороного вокруг точек-препятствий являются наиболее безопасными путями, по которым может пройти робот, поскольку они максимизируют расстояние от каждого препятствия.
• Пуантилизм и полутонирование — диаграммы Вороного с релаксацией Ллойда создают визуально приятные распределения точек, используемые в художественном пуантилизме и растрировании при печати.
• Астрономия — сверхскопления галактик и космическая паутина имеют структуру, подобную Вороного, благодаря гравитационному сгущению; тесселяция Вороного является стандартным инструментом для оценки плотности галактик.
• Кристаллография — ячейки Вигнера — Зейтца (ячейки Вороного вокруг атомов в кристаллической решетке) определяют примитивный объем каждой элементарной ячейки в физике твердого тела.

Математические подробности

Как использовать этот инструмент

1. Выберите пресет или настройте форму. Кнопки пресетов в верхней части формы — это отправные точки для запуска в один клик: Классические ячейки, Соты, Городские кварталы, Шахматный король, Золотая спираль, Рябь, Релаксация Ллойда, Каркас, Пуантилизм, 3 территории.
2. Выберите метрику расстояния. Евклидова для классического вида, Манхэттенская для блочных ячеек, Чебышёва для квадратов, выровненных по осям, Минковского p=3 для скругленных квадратных промежуточных ячеек.
3. Нажмите «Сгенерировать». Диаграмма отобразится с анимацией роста ячеек, чтобы вы могли увидеть, как каждая точка «заявляет права» на свою территорию.
4. Редактируйте на холсте. Кликните по пустому месту, чтобы добавить новую начальную точку. Перетаскивайте любую точку, чтобы переместить её — ячейки следуют за вашим движением в реальном времени. Дважды кликните по точке, чтобы удалить её.
5. Улучшите результат с помощью релаксации Ллойда. Нажмите кнопку релаксации Ллойда (или нажмите R), чтобы сместить каждую точку к центроиду её ячейки. Несколько проходов дадут вам визуально однородную тесселяцию.
6. Переключайте метрику без потери набора точек. Используйте кнопки метрик над холстом — те же точки, другое правило расстояния, совершенно разные ячейки.
7. Экспорт. SVG для векторного использования, PNG для растрового обмена или скопируйте PNG прямо в буфер обмена.

Советы по получению великолепных диаграмм

• Для получения визуально однородных ячеек начните со Случайной или Равномерной раскладки и примените 3–4 прохода релаксации Ллойда. Вы увидите, как ячейки сходятся к шестиугольному узору с очень близкими размерами.
• Для плакатов в стиле поп-арт используйте раскладку Кластер с палитрой Радуга и включите края ячеек. Три территории создают поразительную визуальную иерархию с яркими цветовыми блоками.
• Для диаграмм в техническом стиле используйте стиль Каркас на Равномерной раскладке — четкие черные линии на белом фоне выглядят как чертеж в CAD.
• Для органических, нарисованных от руки узоров используйте стиль Пуантилизм — алгоритм воспринимает края ячеек как точечную работу и создает эффект рисунка пером и чернилами, используемый в научных иллюстрациях.
• Для математической ясности переключитесь на Манхэттенскую или Чебышёва с небольшим количеством точек (8–12 точек). Прямоугольные края позволяют легко проследить вручную, почему каждая ячейка имеет именно такую форму.

Часто задаваемые вопросы