Диаграма на Вороной
 | За информацията в тази статия или раздел не са посочени източници. Въпросната информация може да е непълна, неточна или изцяло невярна. Имайте предвид, че това може да стане причина за изтриването на цялата статия или раздел. |  |
В математиката, диаграма на Вороной е вид пълно разделение на метрично пространство, определено от разстояния до дадено множество точки. Диаграмата носи името на руския математик Григорий Вороной и е още известна като декомпозиция на Вороной и мозайка на Вороной.
В най-простия си и най-широко използван вариант, в равнина със зададени точки Oi, i=(0..n), диаграмата на Вороной представлява множеството многоъгълници Pi, i=(0..n), такова че Pi, съдържа Oi, и най-близката до всяка точка в рамките на Pi е именно Oi.
Формална дефиниция
[редактиране | редактиране на кода]Нека Oi, i=(0..n) е множество от точки в пространството. За всяка точка X от пространството имаме една от трите възможности.
- Сред множеството О има единствена Оi, за която ОiХ е най-малко
- Сред множеството О има две точки Oi и Oj, за които ОiХ=ОjХ е най-малко
- Сред множеството О има три или повече Oi1, Оi2, ... Оin, за които разстоянието до Х е най-късо
В първия случай Х принадлежи на многоълника Pi. Във втория случай Х е на ръба между многоълниците Р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.