Быстрая реализация алгоритма невыпуклого полосового слияния триангуляции Делоне | Вестник Томского государственного университета. Управление, вычислительная техника и информатика. 2025. № 71. DOI: 10.17223/19988605/71/9

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

Рассматривается быстрая реализация полосового алгоритма триангуляции Делоне набора точек плоскости. Вначале область с точками делится на полосы некоторой ширина:, и производится сортировка точек в каждой полосе. Далее в каждой полосе строится отдельная невыпуклая триангуляция методом заметающей прямой. Затем соседние полосы сшиваются между собой, а после получения триангуляции всей области выполняется перестроение треугольников по критерию Делоне. Приведена: результата: работы алгоритма для равномерного и неравномерного (фрактального) распределения точек внутри области. Время работа: предложенного алгоритма по сравнению с наиболее быстрым алгоритмом динамического кэширования оказалось меньше в 1,7 раза. Это объясняется существенно меньшим количеством проверок и перестроений треугольников по критерию Делоне в предложенном алгоритме. Вклад авторов: все авторы сделали эквивалентный вклад в подготовку публикации. Авторы заявляют об отсутствии конфликта интересов.

Скачать электронную версию публикации

Загружен, раз: 5

Ключевые слова

триангуляция Делоне, полосовой алгоритм, алгоритм заметающей прямой, сравнение алгоритмов

Авторы

ФИО	Организация	Дополнительно	E-mail
Литовченко Марина Игоревна	Национальный исследовательский Томский государственный университет	ассистент, аспирант кафедры теоретических основ информатики Института прикладной математики и компьютерных наук	litovchenkom21@yandex.ru
Костюк Юрий Леонидович	Национальный исследовательский Томский государственный университет	профессор, доктор технических наук, профессор кафедры теоретических основ информатики Института прикладной математики и компьютерных наук	kostyuk.yu48@mail.ru

Всего: 2

Ссылки

Костюк Ю.Л., Гульбин К.Г., Пешехонов С.В. Построение поверхностной триангуляции и выделение пространственных фигур по данным лазерного сканирования // Вестник Томского государственного университета. Сер. «Информатика, кибернетика, математика». 2006. № 293. С. 151-155.

Костюк Ю.Л., Литовченко М.И. Распознавание граней трехмерных объектов по данным лазерного сканирования // Информационные технологии и математическое моделирование (ИТММ-2017) : материалы XVI Междунар. конф. им. А.Ф. Терпугова. Томск : Изд-во НТЛ, 2017. С. 55-61.

Храмов В.В. Способ описания объектов сцены системы технического зрения робота средствами нечеткой триангуляции Делоне с использованием адаптивной сетки // Современные информационные технологии и ИТ-образование. 2020. Т. 16, № 4. С. 833-840. doi: 10.25559/SITITO.16.202004.833-840.

Крамаров С.О., Митясова О.Ю., Темкин И.О., Храмов В.В. Методология интеллектуальной навигации для управления автономными подвижными объектами на основе триангуляции Делоне // Горный информационно-аналитический бюллетень. 2021. № 2. C. 87-98. doi: 10.25018/0236-1493-2021-2-0-87-98.

Препарата Ф., Шеймос М. Вычислительная геометрия: введение : пер. с англ. М. : Мир, 1989.

Скворцов А.В. Триангуляция Делоне и ее применение. Томск : Изд-во Том. ун-та, 2002.

Elshakhs Yu.S. et al. A comprehensive survey on Delaunay triangulation: applications, algorithms, and implementations over CPUs, GPUs, and FPGAs // IEEE Access. 2024. V. 12. P. 12562-12585. doi: 10.1109/ACCESS.2024.3354709.

Hadi N.A., Farhani A., Dahalan W.M. An Improved Simple Sweep Line Algorithm for Delaunay Refinement Triangulation // Advanced Engineering for Processes and Technologies II / A. Ismail, W.M. Dahalan, A. Ochsner (eds.). Springer, 2021. С. 263-270. doi: 10.1007/978-3-030-67307-9_23.

Dimitriou P., Karyotis V. On the computation of Delaunay triangulations via genetic algorithms // Evolutionary Intelligence. 2024. V. 17 (4). P. 2413-2432. doi:10.1007/s12065-023-00893-5.

Бикбулатов Т.Х., Тумаков Д.Н. Использование частичной параллелизации для триангуляции двумерных областей // Программные продукты и системы. 2022. Т. 35, № 3. С. 293-304. doi: 10.15827/0236-235X.139.293-304.

Скворцов А.В., Костюк Ю.Л. Эффективные алгоритмы построения триангуляции Делоне // Геоинформатика. Теория и практика. 1998. Вып. 1. С. 22-47.

Костюк Ю.Л. Эффективные алгоритмы обработки и отображения графических данных и их реализация в программных комплексах : автореф. дис. д-ра техн. наук. Томск, 2002. URL: http://vital.lib.tsu.ru/vital/access/manager/Repository/vtls:000139431 (дата обращения: 26.12.2024).