Improving the shape of triangular elements of polygonal domain triangulation

Abstract

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.