Диаграма на Вороной

В математиката, диаграма на Вороной е вид пълно разделение на метрично пространство, определено от разстояния до дадено множество точки. Диаграмата носи името на руския математик Григорий Вороной и е още известна като декомпозиция на Вороной и мозайка на Вороной.

Пример за варианта на диаграмата в двуизмерно пространство с произволни точки (многоъгълниците са оцветени за удобство)

В най-простия си и най-широко използван вариант, в равнина със зададени точки O_{i, i=(0..n)}, диаграмата на Вороной представлява множеството многоъгълници P_{i, i=(0..n)}, такова че P_i, съдържа O_i, и най-близката до всяка точка в рамките на P_i е именно O_i.

Формална дефиниция

Нека O_{i, i=(0..n)} е множество от точки в пространството. За всяка точка X от пространството имаме една от трите възможности.

1. Сред множеството О има единствена О_i, за която О_iХ е най-малко
2. Сред множеството О има две точки O_i и O_j, за които О_iХ=О_jХ е най-малко
3. Сред множеството О има три или повече O_i1, О_i2, ... О_in, за които разстоянието до Х е най-късо

В първия случай Х принадлежи на многоълника P_i. Във втория случай Х е на ръба между многоълниците Р_i и Р_j. В третия случай това е точката, обща за многоълниците Р_i1, Р_i2, ... Р_in.

Свойства

• Всяка точка от О споделя ръб с най-близката до нея
• Ръбът между две точки от О, представлява симетрала на отсечката, образувана от тях
• Две точки от O са съседни върху изпъкналото обкръжение на О тогава и само тогава, когато споделят безкраен ръб
• Двойственият на графа, образуван от върховете и ръбовете на многоълниците, представлява триангулация на Делоне на множеството О

Диаграма на Вороной с периодични гранични условия

Анимация, която представя диаграма на Вороной с периодични гранични условия

Периодичните гранични условия се използват за симулиране на безкрайна система чрез репликиране на крайна система периодично във всички посоки. Този подход помага да се премахнат граничните ефекти, без да се изисква непрактично голям обем изчисления. За да се създаде диаграма на Вороной с периодични гранични условия в дискретна среда с размери MxN елемента е достатъчно да се изчислят координатите на съседните елементи съответно по модул M и N. Така елементите на дясната граница на дискретната мрежа се оказват съседни на елементите на лявата граница, а елементите на долната граница се оказват съседни на елементите на горната граница. Пример за диаграма на Вороной с периодични гранични условия е показан на фигурата вдясно. Анимацията демонстрира периодичността на диаграмата като превърта (скролира) изображението в хоризонтално и вертикално направление.

Външни препратки

• https://www.mathworks.com/help/matlab/ref/voronoi.html Функция на Matlab, която изчертава диаграма на Вороной по зададени вектори x и y с координати на точки.
• Демонстрационна програма за алгоритма SFTessellation, която създава диаграма на Вороной с исползоване на модела на степният пожар

Източници

• Aurenhammer, Franz, Klein, Rolf, Lee, Der-Tsai. Voronoi Diagrams and Delaunay Triangulations. World Scientific, 2013. ISBN 978-9814447638.
• O. I. Zhelezov and V. M. Petrova, "An Algorithm for Random Tessellation Using a Steppe Fire Model," 2023 International Conference Automatics and Informatics (ICAI), Varna, Bulgaria, 2023, pp. 170-173, doi: 10.1109/ICAI58806.2023.10339070.