Point deletion for dynamic update of CD-TIN

Constrained Delaunay triangular irregular network (CD-TIN) is a basic data structure widely used in GIS, 3D reconstruction, computer geometry and geosciences. Traditional researches on Delaunay triangular irregular networks (D-TIN) paid more attention to the insertion algorithms for points and edges, while little to the deletion algorithms for points and edges. The present algorithms for D-TIN are far insufficient for the dynamic updating of CD-TIN, which demands for not only the insertion for points and edges, but also the deletion for points and constrained edges. Based on the improvements to the present insertion and deletion algorithms for D-TIN, an algorithm for point deletion in CD-TIN, namely integral ear elimination (IEE), which improved from the EE algorithm for D-TIN, is presented. Some examples are demonstrated that the presented algorithms in this paper for the updating of CD-TIN are efficient.