Implementation Details

Edge operations form the basis of the incremental algorithm. Therefore, it is convenient to describe triangulation with edge-oriented data structures Guibas and Stolfi (1985). I have followed the idea of Hansen and Levin (1992) of associating with each edge two pointers to the end points and two pointers to the adjacent triangles. The triangle structure is defined by three pointers to the edges of a triangle. Additionally, as required by the point location algorithm, each triangle has a pointer to its ``children.'' This pointer is NULL when the triangle belongs to the current Delaunay triangulation.

Many researchers have pointed out that the geometric primitives used in triangulation must be robust with respect to round-off errors of finite-precision calculation. To assure the robustness of the code, I used the adaptive-precision predicates of Shewchuk (1996), available as a separate package from the netlib public-domain archive.