Delaunay Triangulation - Algorithms

Algorithms

Many algorithms for computing Delaunay triangulations rely on fast operations for detecting when a point is within a triangle's circumcircle and an efficient data structure for storing triangles and edges. In two dimensions, one way to detect if point D lies in the circumcircle of A, B, C is to evaluate the determinant:

\begin{vmatrix} A_x & A_y, & A_x^2 + A_y^2, & 1\\ B_x & B_y, & B_x^2 + B_y^2, & 1\\ C_x & C_y, & C_x^2 + C_y^2, & 1\\ D_x & D_y, & D_x^2 + D_y^2, & 1 \end{vmatrix} = \begin{vmatrix} A_x - D_x, & A_y - D_y, & (A_x^2 - D_x^2) + (A_y^2 - D_y^2) \\ B_x - D_x, & B_y - D_y, & (B_x^2 - D_x^2) + (B_y^2 - D_y^2) \\ C_x - D_x, & C_y - D_y, & (C_x^2 - D_x^2) + (C_y^2 - D_y^2) \end{vmatrix} > 0

When A, B and C are sorted in a counterclockwise order, this determinant is positive if and only if D lies inside the circumcircle.

Read more about this topic:  Delaunay Triangulation