Fast implementation of a non-convex stripe merging algorithm for Delaunay triangulation
The paper presents a fast implementation of a Stripe Merging algorithm for Delaunay triangulation of a set of points in the plane. Initially, the area containing the points is divided into stripes of a specified width, and the points within each stripe are sorted. Subsequently, a separate non-convex triangulation is constructed in each stripe using the Sweep Line algorithm. Neighboring stripes are then merged together, and upon obtaining a triangulation of the entire area, the triangles are rebuilt according to the Delaunay criterion. The performance of the algorithm is demonstrated on both uniform and non-uniform (fractal) point distributions within the domain. The execution time of the proposed algorithm turned out to be 1,7 times faster than that of the most efficient iterative algorithm with dynamic hashing for triangle searches. This improvement can be attributed to the significantly reduced number of Delaunay criterion checks and triangles rebuilds performed by the proposed method. Contribution of the authors: the authors contributed equally to this article. The authors declare no conflicts of interests.
Keywords
Delaunay triangulation,
stripe merging algorithm,
sweep line algorithm,
algorithm comparisonAuthors
| Litovchenko Marina I. | National Research Tomsk State University | litovchenkom21@yandex.ru |
| Kostyuk Yuriy L. | National Research Tomsk State University | kostyuk.yu48@mail.ru |
Всего: 2
References
Костюк Ю.Л., Гульбин К.Г., Пешехонов С.В. Построение поверхностной триангуляции и выделение пространственных фигур по данным лазерного сканирования // Вестник Томского государственного университета. Сер. «Информатика, кибернетика, математика». 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).
