Another popular DEM is the triangulated irregular network, or TIN, in which the terrain is represented as a triangulated xy-monotone surface. Typically the heights of the vertices in the TIN are directly obtained from the input terrain data, while linear interpolation is used for points inside a triangular face. Compared with the grid model, a TIN has the advantage of being flexible, because the vertices need not be at fixed locations, and edges can be connected arbitrarily provided that they form a triangulation. Thus it tends to be more accurate than the grid model of the same size. However, this irregularity also presents more difficulty in constructing and analyzing TINs, and algorithms on TINs are usually less efficient than their counterparts in the grid model.

One popular method to generate a TIN from elevation data is to project the points onto the xy-plane, compute the Delaunay triangulation of the projected points, and then lift the triangulation back to 3D. We designed and implemented an I/O-efficient algorithm for constructing TINs by computing the Delaunay triangulation. In addition, if there are certain linear features on the terrain, such as rivers and road networks, we can preserve these features by representing them as edges in the TIN. For this purpose we extended our algorithm to computing the so-called constrained Delaunay triangulation — one that has all the prescribed edges while is as close to the Delaunay triangulation as possible.

Publication

P. K. Agarwal, L. Arge, and K. Yi. I/O-Efficient Construction of Constrained Delaunay Triangulations. In Proceedings of the 13th European Symposium on Algorithms (ESA'05), Mallorca, Spain, October 2005. pdf: proceedings abstract | pdf: full version