An Improved Algorithm for the Rapid Localization of Non-Delaunay Triangles through Point-by-Point Insertion

The incremental insertion algorithm is a commonly used Delaunay triangulation method for constructing complex surfaces in computer graphics. However, inserting nodes requires traversing the entire global triangular mesh, which leads to low time efficiency. To optimize the time complexity, a fast method for locating non-Delaunay triangles in incremental insertion algorithms is proposed. Based on the fundamental properties of Delaunay triangles, the “Adjacent Non-Delaunay Triangle Theorem” and the “Nearest Point as Suspect Theorem” are introduced and proven, which facilitate the rapid identification of non-Delaunay triangles. Furthermore, the issue of local necrosis occurring in scenarios with large node scales and uneven distribution density is analyzed and resolved, introducing an improved incremental insertion algorithm that does not require updating the traversal threshold. Tests conducted on two-dimensional point sets with various distribution characteristics and sizes show that the time complexity can ideally reach O(NlogN). For randomly generated point sets, compared to traditional optimized algorithms, the proposed algorithm achieves a 46.96% improvement in time efficiency for triangulating one million points, and the time usage is closer to a linear relationship with the number of points. Experimental results indicate that the proposed algorithm significantly enhances time efficiency while maintaining identical triangulation outcomes compared to the Bowyer-Watson algorithm and traditional optimized algorithms. It also demonstrates good adaptability and robustness across datasets of varying scales and distribution characteristics.