Быстрая реализация алгоритма невыпуклого полосового слияния триангуляции Делоне

doi:10.17223/19988605/71/9

Эндаумент фонд ТГУ!
Впиши своё имя в историю университета
- Сделать пожертвование -

Add to "Quick Collection"

Description	Size	Format
Быстрая реализация алгоритма невыпуклого полосового слияния триангуляции Делоне	745 KB	Adobe Acrobat PDF	Read	Download
DOI Доступ к ресурсу на сайте издателя			10.17223/19988605/71/9

#Делоне триангуляция

#полосовой алгоритм

#алгоритм заметающей прямой

#сравнение алгоритмов

Title: Быстрая реализация алгоритма невыпуклого полосового слияния триангуляции Делоне
Title: Fast implementation of a non-convex stripe merging algorithm for Delaunay triangulation
Creator: Литовченко, Марина Игоревна
|
Костюк, Юрий Леонидович
Date: 2025
DOI: 10.17223/19988605/71/9
Description: Рассматривается быстрая реализация полосового алгоритма триангуляции Делоне набора точек плоскости. Вначале область с точками делится на полосы некоторой ширины, и производится сортировка точек в каждой полосе. Далее в каждой полосе строится отдельная невыпуклая триангуляция методом заметающей прямой. Затем соседние полосы сшиваются между собой, а после получения триангуляции всей области выполняется перестроение треугольников по критерию Делоне. Приведены результаты работы алгоритма для равномерного и неравномерного (фрактального) распределения точек внутри области. Время работы предложенного алгоритма по сравнению с наиболее быстрым алгоритмом динамического кэширования оказалось меньше в 1,7 раза. Это объясняется существенно меньшим количеством проверок и перестроений треугольников по критерию Делоне в предложенном алгоритме.