NonDelaunay

nonDelaunay refers to a triangulation of a set of points that does not satisfy the Delaunay condition. The Delaunay triangulation is a specific type of triangulation that maximizes the minimum angle of all triangles in the triangulation, avoiding "skinny" triangles as much as possible. A key property of a Delaunay triangulation is that the circumcircle of any triangle in the triangulation does not contain any other input points in its interior.

A nonDelaunay triangulation, therefore, is one where at least one triangle's circumcircle contains another input point. This can occur for various reasons, such as using a simple incremental insertion algorithm without a mechanism to enforce the Delaunay property, or if the algorithm prioritizes other criteria.

The consequences of using a nonDelaunay triangulation can be significant depending on the application. In fields like finite element analysis, mesh quality is crucial for numerical accuracy and stability. NonDelaunay meshes can lead to larger errors and slower convergence. In computer graphics, poor mesh quality can result in visual artifacts.

Algorithms exist to convert a nonDelaunay triangulation into a Delaunay triangulation. A common technique is edge flipping, where a nonDelaunay edge is identified and "flipped" to potentially improve the triangulation's Delaunay property. This process is repeated until the Delaunay condition is satisfied for all edges. While generating a nonDelaunay triangulation might be simpler or faster in some initial steps, the subsequent need for correction or the degradation in application performance often makes aiming for a Delaunay triangulation more desirable.