Математическая физика и компьютерное моделирование2587-63252587-690210.15688/mpcm.jvolsu.2025.4.3OtherМЕТОД СДВИГА КРАЙНИХ ТОЧЕК ДЛЯ ПОСТРОЕНИЯ ТРИАНГУЛЯЦИИMETHOD OF SHIFT OF BORDER POINTS FOR CONSTRUCTING A TRIANGULATIONКлячинАлексей АлександровичKlyachinAlekseyAleksey.klyachin@volsu.ruVolgograd State University (Volgograd, Russian Federation)Волгоградский государственный университет (Волгоград, Российская Федерация)3012202528443530710202514102025https://creativecommons.org/licenses/by/4.0/CC BY 4.0

В работе представлен метод построения триангуляции плоской области, граница которой задается в формате obj-файла. Идея нашего подхода заключается в следующем. На первом шаге плоскость равномерно разбивается на квадраты со стороной ℎ > 0. На втором шаге строится триангуляция фигуры, образованной квадратами, у которых хотя бы три вершины попадают в область. Окончательное построение триангуляции осуществляется на третьем шаге: определяется векторное поле, вдоль которого крайние узлы сдвигаются на границу области по определенному правилу. Разработано соответствующее программное обеспечение и построена триангуляция некоторых фигур, полученных их моделированием в системе Blender.

This paper presents a method for constructing a triangulation of a flat region whose boundary is specified in an .obj file. The idea behind our approach is as follows. In the first step, the plane is uniformly divided into squares with sides ℎ > 0. In the second step, a triangulation of the figure formed by the squares with at least three vertices within the region is constructed. The final triangulation is constructed in the third step: a vector field is defined along which the outermost nodes are shifted to the region boundary according to a specific rule. Corresponding software was developed, and triangulations of several figures obtained by modeling them in the Blender system were constructed.

триангуляция областисдвиг крайних узловрасчетная сеткаразбиение плоскостивекторное полеtriangulation of a regionshift of extreme nodescomputational gridplane partitioningvector fieldАлейников, С. М. Алгоритм генерации сетки в методе граничных элементов для плоских областей / С. М. Алейников, А. А. Седаев // Математическое моделирование. — 1995. — № 7 (7). — C. 81–93.Андрекайте, А. А. Вариационные методы построения расчетных сеток для конечно-элементных расчетов в многосвязных областях / А. А. Андрекайте // Вестник научно-технического развития. — 2010. — № 8 (36). — C. 1–7.Бичерахова, О. С. Построение треугольных сеток многосвязных областей на основе триангуляции Делоне / О. С. Бичерахова // Математическая физика и компьютерное моделирование. — 2025. — № 3 (28). — C. 37–49. — DOI: https://doi.org/10.15688/mpcm.jvolsu.2025.3.4Гаранжа, В. А. Регуляризация барьерного вариационного метода построения расчетных сеток / В. А. Гаранжа, И. Е. Капорин // Журнал вычисл. матем. и матем. физ. — 1999. — № 9 (39). — C. 1489–1503.Гаранжа, В. А. Билипшицевы параметризации негладких поверхностей и построение поверхностных расчетных сеток / В. А. Гаранжа // Журнал вычисл. матем. и матем. физ. — 2005. — № 8 (45). — C. 1383–1398.Гилева, Л. В. Обоснование асимптотической устойчивости алгоритма триангуляции трехмерной области / Л. В. Гилева, В. В. Шайдуров // Сиб. журн. вычисл. матем. — 2000. — № 3:2. — C. 123–136.Зорькин, Д. Ю. Триангуляция методом измельчения плоской области, заданной системой неравенств / Д. Ю. Зорькин, И. А. Тарасова, Н. В. Клячина // Вестник кибернетики. — 2025. — № 24 (1). — C. 11–18.Караваев, А. С. Алгоритмы построения и перестроения неструктурированных четырехугольных сеток в односвязных областях / А. С. Караваев, С. П. Копысов, А. Б. Пономарев // Вычислительная механика сплошных сред. — 2012. — № 2 (5). — C. 144–150.Клячин, А. А. Построение триангуляции плоских областей методом измельчения / А. А. Клячин // Вестник Волгоградского государственного университета. Серия 1, Математика. Физика. — 2017. — № 2(39). — C. 18–28.Клячин, В. А. Алгоритм триангуляции, основанный на условии пустого выпуклого множества / В. А. Клячин // Вестник Волгоградского государственного университета. Серия 1, Математика. Физика. — 2015. — № 3 (28). — C. 27–33.Немировский, Ю. В. Автоматизированная триангуляция многосвязных областей со сгущением и разрежением узлов / Ю. В. Немировский, С. Ф. Пятаев // Вычислительные технологии. — 2000. — № 5 (2). — C. 82–91.Полянский, Д. Ю. Триангуляция плоских областей решением методом конечных элементов в форме Галеркина задачи Дирихле / Д. Ю. Полянский // Известия высших учебных заведений. Поволжский регион. Физико-математические науки. — 2012. — № 3. — C. 38–46.Скворцов, А. В. Обзор алгоритмов построения триангуляции Делоне / А. В. Скворцов // Вычислительные методы и программирование. — 2002. — № 3. — C. 14–39.Скворцов, А. В. Алгоритмы построения триангуляции с ограничениями / А. В. Скворцов // Вычислительные методы и программирование. — 2002. — № 3. — C. 82–92.Шикин, А. В. Компьютерная графика. Полигональные модели / А. В. Шикин, А. В. Борисков. — М. : ДИАЛОГ - МИФИ, 2001. — 464 c.Labelle, F. Isosurface Stuffing: Fast Tetrahedral Meshes with Good Dihedral Angles / F. Labelle, J. Shewchuk // ACM Transactions on Graphics. — 2007. — Vol. 26, № 3. — P. 1–10.Mandad, M. Guaranteed-Quality Higher-Order Triangular Meshing of 2D Domains / M. Mandad, M. Campen // ACM Trans Graph. — 2021. — Vol. 40. — P. 1—s14.Aleynikov S.M., Sedaev A.A. Mesh Generation Algorithm in the Boundary Element Method for Planar Domains. Matematicheskoe modelirovanie [Mathematical Modeling.], 1995, no. 7 (7), pp. 81-93.Andrekayte A.A. Variational Methods for Constructing Computational Meshes for Finite Element Calculations in Multiply Connected Domains. Vestnik nauchno-tekhnicheskogo razvitiya [Bulletin of Scientific and Technological Development], 2010, no. 8 (36), pp. 1-7.Bicherakhova O.S. Construction of Triangular Meshes of Multiply Connected Regions Based on Delaunay Triangulation. Matematicheskaya fizika i kompyuternoe modelirovanie [Mathematical Physics and Computer Simulation], 2025, no. 3 (28), pp. 37-49. DOI: https://doi.org/10.15688/mpcm.jvolsu.2025.3.4Garanzha V.A., Kaporin I.E. Regularization of the Barrier Variational Method for Constructing Computational Grids. Zhurnal vychisl. matem. i matem. fiz. [J. Comput. Mathematics and Mathematics Phys.], 1999, no. 9 (39), pp. 1489-1503.Garanzha V.A. Bi-Lipschitz Parametrizations of Non-Smooth Surfaces and Construction of Surface Computational Grids. Zhurnal vychisl. matem. i matem. fiz. [J. Comput. Mathematics and Mathematics Phys.], 2005, no. 8 (45), pp. 1383-1398.Gileva L.V., Shaydurov V.V. Justification of the Asymptotic Stability of the Triangulation Algorithm for a Three-Dimensional Domain. Sib. zhurn. vychisl. matem. [Sib. J. Comput. Math.], 2000, no. 3:2, pp. 123-136.Zorkin D.Yu., Tarasova I.A., Klyachina N.V. Triangulation by the Method of Refining a Flat Domain Defined by a System of Inequalities. Vestnik kibernetiki [Bulletin of Cybernetics], 2025, no. 24 (1), pp. 11-18.Karavaev A.S., Kopysov S.P., Ponomaryov A.B. Algorithms for Constructing and Reconstructing Unstructured Quadrilateral Meshes in Simply Connected Domains. Vychislitelnaya mekhanika sploshnykh sred [Computational Continuum Mechanics], 2012, no. 2 (5), pp. 144-150.Klyachin A.A. Construction of Triangulation of Flat Regions by the Refinement Method. Vestnik Volgogradskogo gosudarstvennogo universiteta. Seriya 1: Matematika. Fizika [Bulletin of Volgograd State University. Series 1: Mathematics. Physics.], 2017, no. 2(39), pp. 18-28.Klyachin V.A. Triangulation Algorithm Based on the Empty Convex Set Condition. Vestnik Volgogradskogo gosudarstvennogo universiteta. Seriya 1. Matematika. Fizika [VolSU Bulletin. Series 1. Mathematics. Physics], 2015, no. 3 (28), pp. 27-33.Nemirovskiy Yu.V., Pyataev S.F. Automated Triangulation of Multi-Connected Regions with Node Densification and Sparseness. Vychislitelnye tekhnologii [Computing Technologies], 2000, no. 5 (2), pp. 82-91.Polyanskiy D.Yu. Triangulation of Planar Regions by the Finite Element Solution in Galerkin Form of the Dirichlet Problem. Izvestiya vysshikh uchebnykh zavedeniy. Povolzhskiy region. Fiziko-matematicheskie nauki [News of Higher Educational Institutions. Volga Region. Physical and Mathematical Sciences], 2012, no. 3, pp. 38-46.Skvortsov A.V. Overview of Delaunay Triangulation Construction Algorithms. Vychislitelnye metody i programmirovanie [Computational Methods and Programming], 2002, no. 3, pp. 14-39.Skvortsov A.V. Algorithms for Constructing Triangulation with Constraints. Vychislitelnye metody i programmirovanie [Computational Methods and Programming], 2002, no. 3, pp. 82-92.Shikin A.V., Boriskov A.V. Computer Graphics. Polygonal Models. Moscow, DIALOG - MIFI, 2001. 464 p.Labelle F., Shewchuk J. Isosurface Stuffing: Fast Tetrahedral Meshes with Good Dihedral Angles. ACM Transactions on Graphics, 2007, vol. 26, no. 3, pp. 1-10.Mandad M., Campen M. Guaranteed-Quality Higher-Order Triangular Meshing of 2D Domains. ACM Trans Graph, 2021, vol. 40, pp. 1—s14.