Диаграмма Вороного
Диаграмма Вороного (Voronoi diagram) конечного множества точек S на плоскости представляет такое разбиение плоскости, при котором каждая область этого разбиения образует множество точек, более близких к одному из элементов множества S, чем к любому другому элементу.
Названа в честь Георгия Феодосьевича Вороного, который изучил общий n-мерный случай в 1908 году. Также известна как: мозаика Вороного, разбиение Вороного, разбиение Дирихле.
Названа в честь Георгия Феодосьевича Вороного, который изучил общий n-мерный случай в 1908 году. Также известна как: мозаика Вороного, разбиение Вороного, разбиение Дирихле.
Основные определения
Сайты (seeds, sites or generators) — точки, по которым строится диаграмма Вороного.
Ячейка (Voronoi cell, region) — область пространства, соответствующая какому-то сайту.
Границы ячеек (boundaries) — границы ячеек.
Вершина (vertex) — точки пересечения границ ячеек.
Замощение (tessellation) — разбиение плоскости на ячейки (многоугольники).
Ячейка (Voronoi cell, region) — область пространства, соответствующая какому-то сайту.
Границы ячеек (boundaries) — границы ячеек.
Вершина (vertex) — точки пересечения границ ячеек.
Замощение (tessellation) — разбиение плоскости на ячейки (многоугольники).
Алгоритм построения
- Соединяем все точки (сайты) линиями.
- Строим серединные перпендикуляры к отрезкам, соединяющим сайты.
- Ячейка получается в результате пересечения всех полуплоскостей, в которых находится сайт.
Свойства
- Вершины диаграммы Вороного равноудалены от соседних сайтов – это свойство часто используется в задачах оптимизации.
- Точки, находящиеся на границах ячеек, также равноудалены от ближайших сайтов, поскольку граница – это серединный перпендикуляр.
- Для любой точки внутри ячейки её ближайший сосед – это соответствующий сайт.
Интерактивное построение диаграммы Вороного
- Отметьте на экране точки (сайты).
- Нажмите на кнопку "Анимировать".
- Смотрите, как пошагово строится диаграмма Вороного.
- Меняйте параметры по своему вкусу.
- Скачивайте полученные изображения и gif.
- Перетаскивайте точки касанием.
- Удаляйте точки двойным нажатием на них.
Где используются диаграммы Вороного
- Гидрология и метеорология: определение областей влияния метеорологических станций (полигоны Тиссена) и расчёт среднего количества осадков.
- Эпидемиология: анализ распространения заболеваний (например, холера в Лондоне по примеру Джона Сноу).
- Археология и история искусства: анализ симметрии античных статуй для идентификации.
- Политология: исследование конкуренции между партиями и кандидатами на выборах.
- Экология: изучение роста лесных массивов и прогнозирование распространения пожаров.
- Этология: моделирование «зон опасности» для животных в теории эгоистичного стада.
- Астрофизика: адаптивное сглаживание астрономических изображений для поддержания оптимального отношения сигнал/шум.
- Физика твёрдого тела и материаловедение: описание структуры кристаллов и сплавов (ячейки Вигнера-Зейтца, зоны Бриллюэна).
- Авиация: определение ближайших аэродромов для экстренных посадок (ETOPS).
- Архитектура: создание уникальных архитектурных паттернов на основе разбиений Вороного.
- Горнодобывающая промышленность: оценка запасов полезных ископаемых на основе данных разведочных скважин.
- Робототехника: планирование безопасных маршрутов и управление перемещениями роботов в сложных средах.
- Компьютерная графика: генерация органических текстур (лава, трещины).
- Машинное обучение: классификация объектов методом ближайшего соседа (1-NN).
- Геометрия и градостроительство: оптимальное расположение объектов в городской инфраструктуре.
- И многие другие области.
Историческая справка
Неформальное использование диаграмм Вороного прослеживается со времён Декарта (1644 г.). Петер Густав Лежён Дирихле применял двумерные и трёхмерные диаграммы Вороного в исследованиях квадратичных форм в 1850 году. Британский врач Джон Сноу использовал подобную диаграмму в 1854 году, чтобы показать, что большинство жертв холеры в Лондоне жили ближе к заражённой водяной колонке.
Диаграммы получили своё название в честь русского и украинского математика Георгия Феодосьевича Вороного, который в 1908 году сформулировал общий случай для n-мерных пространств. В гидрологии, метеорологии и других областях разбиения Вороного также называют полигонами Тиссена.
Диаграммы получили своё название в честь русского и украинского математика Георгия Феодосьевича Вороного, который в 1908 году сформулировал общий случай для n-мерных пространств. В гидрологии, метеорологии и других областях разбиения Вороного также называют полигонами Тиссена.
Смотрите также
- Линейная функция
- Серединный перпендикуляр
- Расстояние между точками на плоскости
- Многоугольник