Rapid Delaunay triangulation for randomly distributed point cloud data using adaptive Hilbert curve

Given the enormous scale and diverse distribution of 2D point cloud data, an adaptive Hilbert curve insertion algorithm which has quasi-linear time complexity is proposed to improve the efficiency of Delaunay triangulation. First of all, a large number of conflicting elongated triangles, which have been created and deleted many times, can be reduced by adopting Hilbert curve traversing multi-grids. In addition, searching steps for point location can be reduced by adjusting Hilbert curve's opening direction in adjacent grids to avoid the "jumping" phenomenon. Lastly, the number of conflicting elongated triangles can be further decreased by adding control points during traversing grids. The experimental results show that the efficiency of Delaunay triangulation by the adaptive Hilbert curve insertion algorithm can be improved significantly for both uniformly and non-uniformly distributed point cloud data, compared with CGAL, regular grid insertion and multi-grid insertion algorithms. Graphical abstractDisplay Omitted HighlightsThe proposed algorithm optimizes the order of inserted points.The order is determined by adaptive Hilbert curve and control points.Conflicting elongated triangles and searching steps are reduced by optimized order.The efficiency of the proposed method is proved to be enhanced by detail experiment.The proposed algorithm is suitable for randomly distributed points.