A triangulation T(P) is a mapping from a set of points P to a set of triangles T such that:

1. T only contains vertices at points in P
2. T fills the convex hull of P
3. T does not contain overlapping triangles.

FIXME: Add more illustrative Pictures.
A halfedge mesh is a data structure for efficiently storing the connectivity information defined for a manifold polyhedral mesh with possible boundaries. Manifold just means that every neighborhood for ever vertex looks roughly like a circle which prevents certain degeneracies such as edges contained in more than 2 possible faces. A sweep line refers to a common class of computational geometry algorithms that sort the data in space and then gradualy solve the problem from in spacial order. For instance, in the computation of triangulations we will compute the triangulation for the leftmost 3 points and then compute the triangulation for the leftmost 4, 5, 6, etc points, therebye solving the problem successively in left to right spatial order.

A point is said to be an exterior point with regards to T if and only if it is not contained within any triangles in T.

A exterior point e is said to be visible with regards to a vertex v within T if and only if the ray from e through v does not intersect any triangles in T

addExteriorPointToTriangulation()

Here is an algorithm for adding an exterior point e to a well formed half edge mesh.

1. Find a half edge on the border of the triangulation originating at a vertex v such that is visible from e.
2. Transverse the halfedge boundary from v to find the first and last points in the external face that are visible from e. Call them p0 and p1
3. Add the fan of triangles formed by the the endpoints of the halfedges from p0 and p1 and the third point e to the half edge mesh.
4. Link up all of the half edge mesh connectivity information to restore the half edge mesh invariants.

An implementation of this algorithm may be found here.

initTriangulation()

Here is naive algorithm to compute T(P) based on my function found here. It forms and uses a halfedge mesh structure in addition to the concept of a sweep line.

1. Sort P by y coordinate, then sort in place by x coordinate.
2. Instantiate a Half Edge mesh representation H.
3. Initialize H with the trivial triangulation for the first 2 points.
4. In order, add each point to the triangulation. Since they are sorted they are all exterior points relative to their respective states of H. Therefore we can simply use the algorithm stated above.

We now have a naive triangulation that looks something like the following image for a rectangularly bounded set of randomly chosen points:

A triangulation T(P) is said to be delauney if for every triangle s, the circumcircle of s contains no points in p beyond those in s.

Thankfully we can narrow down delauneyness to a local property of edges. An edge is delauney if its exterior triangle angles sum up to less than 180 degrees.

A function may be written as follows to determine this for an edge in a half edge mesh:

// Assumes that this is a triangle mesh.
public boolean isDelauney(Edge edge)
{
	// Find the relevant 4 vertices.
	HEdge he1 = edge.edge;
	HEdge he2 = he1.twin;
		
	// Inner vertices on the edge.
	Vertex i1 = he1.vertex;
	Vertex i2 = he2.vertex;
		
	// outer vertices.
	Vertex o1 = he1.prev.vertex;
	Vertex o2 = he2.prev.vertex;
		
	// We don't really care about the orientation, because the problem is symmetrical.
				
	// An edge is delauney if its exterior triangle angles sum up to less than 180 degrees.
	return GeometricQueries.angle(i1, o1, i2) +
	       GeometricQueries.angle(i1, o2, i2)  <= Math.PI; 
}

Please note that the definition for GeometricQueries.angle may be found here.

If an edge is shared by two triangles, then it may be flipped by connecting it to the two end points of the two triangles that it was not previously connected to as shown in the following figure: We can then convert any triangulation, including our naive triangulation into a delauney triangulation by randomly flipping any edges which are not currently delauney. Eventually after a random number of flips (around N log N in expectation), all edges will be delauny and therefore the entire triangulation will be delauney. An implementation of this algorithm may be found here. We now have a delauny triangulation which will look something like the following for another set of random points.

The convex hull C(P) of a set of points includes the region formed by the union of all possible triangles that may be constructed from the set of points. In other words, if you were to stretch a rubber band around the set of points, the convex hull would be defined by the points the rubber band sticks to when it tightens. If you are in the mood, you can easily retrieve the convex hull of the triangulation by starting at an exterior half edge or a triangulation and walking around the exterior face. Convex hulls are held in high esteem within the field of computational geometry.