В статье рассматривается проблема повышения вычислительной надежности треугольных сеток, используемых в численных методах и геометрическом моделировании, на примере триангуляции плоской многоугольной области. Обосновано, что точность приближений в треугольных элементах определяется не только характерным размером ячеек, но и их формой: появление вытянутых треугольников с малыми углами приводит к росту погрешности при сгущении сетки, вплоть до неограниченного. В качестве идеализированного ориентира вводится функционал, равный минимальному углу по всем элементам триангуляции, и обсуждается его максимизация за счет перемещения внутренних узлов, однако отмечаются вычислительная трудоемкость и сложность прямой реализации. Для практического улучшения сетки предложены два локальных критерия качества, определяемые в окрестности каждого внутреннего узла через многоугольник соседства, образованный смежными вершинами. Первый критерий основан на минимизации «разброса» углов при внутренней вершине относительно равномерного значения 2π/r, что приводит к выравниванию углов и, в предельном случае, к положению узла вблизи центра многоугольника соседства. Второй критерий использует минимизацию дисперсии квадратов расстояний от узла до сторон многоугольника соседства, обеспечивая более равномерное положение точки относительно границ локальной конфигурации. Для обоих критериев представлены итерационные процедуры переноса узла с оценкой производной по конечным разностям и последовательной коррекцией координат до стабилизации. Эффективность методик продемонстрирована на триангуляции Делоне для прямоугольника с 80 точками (граничными и случайными внутренними): среднее значение углового функционала уменьшается более чем на 22%, а функционала расстояний – более чем на 18%. На модельной задаче вычисления интегрального функционала для u(x,y)=x²+y² показано снижение ошибки приближения: после оптимизации по угловому критерию – на 18%, по критерию расстояний – на 6%. Отмечена программная реализация в среде Python, включающая построение триангуляции Делоне и процедуры улучшения формы элементов.
The article discusses the problem of increasing the computational reliability of triangular grids used in numerical methods and geometric modeling, using the example of triangulation of a flat polygonal area. It is proved that the accuracy of approximations in triangular elements is determined not only by the characteristic size of the cells, but also by their shape: the appearance of elongated triangles with small angles leads to an increase in the error when thickening the grid, up to unlimited. As an idealized guideline, a functional equal to the minimum angle for all elements of the triangulation is introduced, and its maximization by moving internal nodes is discussed, however, computational complexity and complexity of direct implementation are noted. For practical improvement of the grid, two local quality criteria are proposed, determined in the neighborhood of each internal node through a neighborhood polygon formed by adjacent vertices. The first criterion is based on minimizing the «spread» of angles at the inner vertex with a relatively uniform value of 2π/r, which leads to the alignment of the angles and, in the extreme case, to the position of the node near the center of the neighborhood polygon. The second criterion uses minimizing the variance of the squared distances from the node to the sides of the neighborhood polygon, ensuring a more uniform position of the point relative to the boundaries of the local configuration. For both criteria, iterative node transfer procedures are presented with an estimate of the derivative with respect to finite differences and sequential correction of coordinates until stabilization. The effectiveness of the techniques is demonstrated by the Delaunay triangulation for a rectangle with 80 points (boundary and random interior): the average value of the angular functional decreases by more than 22%, and the distance functional by more than 18%. The model problem of calculating the integral functional for u(x,y)=x2+y2 shows a decrease in the approximation error: after optimization by the angular criterion – by 18%, by the distance criterion – by 6%. A software implementation in the Python environment is noted, including the construction of Delaunay triangulation and procedures for improving the shape of elements.