What are the best practices for ensuring Delaunay triangulation quality?

1 Point distributions

One of the main factors that affect the quality of Delaunay triangulation is the distribution of the input points. Ideally, the points should be uniformly spaced and randomly sampled, to avoid creating clusters or gaps that can lead to poor triangle shapes. However, in some applications, such as terrain modeling or image processing, the points may be given or derived from existing data, and may not follow a uniform or random pattern. In these cases, you may need to preprocess the points, for example, by applying smoothing, thinning, or resampling techniques, to improve their distribution and reduce noise.

2 Refinement techniques

Another way to improve the quality of Delaunay triangulation is to use refinement techniques, which modify the existing triangulation by adding or removing points or edges, to achieve a desired quality criterion. There are different types of refinement techniques, such as edge flipping, point insertion, point deletion, and edge contraction, each with its own advantages and disadvantages. For example, edge flipping can improve the angle quality of the triangles, but may not reduce the number of triangles or the aspect ratio. Point insertion can create more uniform and isotropic triangles, but may increase the complexity of the triangulation and introduce new skinny triangles. Point deletion can simplify the triangulation and eliminate unwanted points, but may create holes or gaps in the boundary. Edge contraction can merge adjacent triangles and reduce the number of edges, but may distort the shape of the triangulation and violate the Delaunay property.

3 Quality criteria

The last best practice for ensuring Delaunay triangulation quality is to apply quality criteria, which measure the shape or size of the triangles and compare them to a predefined threshold or target. There are different quality criteria, such as the minimum angle, the maximum angle, the aspect ratio, the area, the circumradius, and the radius ratio, each with its own interpretation and implication. For example, the minimum angle criterion aims to avoid skinny triangles, which can cause numerical instability and interpolation errors. The maximum angle criterion aims to avoid obtuse triangles, which can reduce the accuracy and convergence of finite element methods. The aspect ratio criterion aims to avoid elongated triangles, which can affect the mesh quality and the speed of algorithms. The area criterion aims to avoid too small or too large triangles, which can cause discretization errors and computational overhead. The circumradius criterion aims to avoid triangles with large circumcircles, which can indicate poor point distribution and sampling. The radius ratio criterion aims to avoid triangles with small inscribed circles, which can indicate poor angle quality and aspect ratio.