Fast implementation of a non-convex stripe merging algorithm for Delaunay triangulation

The paper presents a fast implementation of a Stripe Merging algorithm for Delaunay triangulation of a set of points in the plane. Initially, the area containing the points is divided into stripes of a specified width, and the points within each stripe are sorted. Subsequently, a separate non-convex triangulation is constructed in each stripe using the Sweep Line algorithm. Neighboring stripes are then merged together, and upon obtaining a triangulation of the entire area, the triangles are rebuilt according to the Delaunay criterion. The performance of the algorithm is demonstrated on both uniform and non-uniform (fractal) point distributions within the domain. The execution time of the proposed algorithm turned out to be 1,7 times faster than that of the most efficient iterative algorithm with dynamic hashing for triangle searches. This improvement can be attributed to the significantly reduced number of Delaunay criterion checks and triangles rebuilds performed by the proposed method.