Open AccessАппроксимация диаграммы вороного k-го порядка
Author(s) -
С А Хальзов,
В В Фертиков
Publication year - 2019
Publication title -
vestnik voronežskogo gosudarstvennogo universiteta. seriâ sistemnyj analiz i informacionnye tehnologii
Language(s) - Russian
Resource type - Journals
ISSN - 1995-5499
DOI - 10.17308/sait.2019.2/1287
Subject(s) - materials science
Представлен алгоритм построения обобщенной дискретной диаграммы Вороного k-го порядка на сетке с переменным шагом, основанный на идее рекурсивного разбиения пространства. В алгоритме в качестве структуры данных используется дерево разбиения пространства (2d-дерево), также известное как квадродерево и октодерево для 2-х и 3-х мерных пространств. Алгоритм рекурсивно уточняет границы ячеек Вороного (би-секторы), используя только локальные свойства в каждой точке области построения. В результате вычисления сосредотачиваются в области границ ячеек (глубина 2d-дерева больше в области границ ячеек), и достигается существенный выигрыш производительности по сравнению с наивным алгоритмом (полным перебором). Алгоритм позволяет обобщать форму сайтов, используемую метрику, порядок диаграммы и число измерений.