2D Triangulation

Recently I was trying to convert geojson polygons into meshes. The geojson polygon data is an array of latitude- longitude coordinates. These coordinates form a clockwise loop. But how do I create a mesh from a loop where everything inside the loop is filled?

The search for an existing answer

To compartmentalize the problem of creating a mesh from geojson, the latitude- and longitude coordinates are placed into 2D tiles. This means the coordinates are now points and can be treated as having an x- and y coordinate. Now it is possible to just focus on the triangulation of a closed loop.

When searching how to triangulate, you'll probably find something like Delaunay triangulation. When using this algorithm, it was too common to have wrong facing triangles, missing triangles, or triangles outside the loop. Wrong facing triangles are easily fixed using a cross product check, but the other two problems are harder to solve. This algorithm did not suit my needs, and I needed to continue my search.

A too common answer I found was: use this massive library to do triangulation. Besides the cost of learning the library and hoping it even works. The complexity of the software raises to an unnecessary height. This too was not a viable option, and thus, assuming the time investment of finding an answer opposed to create one myself was too high.

Dissecting the problem

The first thing when solving a problem -given that there is a clear goal in mind- is knowing what data you have. The points are in a clockwise rotating closed loop. This means when forming a triangle, the third point should always be on the right hand side of the segment created by the first two points. Additionally, a mesh should not have overlapping triangles. This information gave me a comfortable starting point solving problem.

The first obvious thing that came in to my mind is to create triangles along the edge. This means we already have two point. But there are three points needed to create a triangle. The third one has to be on the right side of the segment created by the first two points. And the created triangle should not intersect any previously created triangles.

There are two options: the first one is iterating over the loop until a valid third point comes along. The second one is only look at three consecutive points, and if it isn't valid just move to the next point. I chose for the latter option, as it seemed less complex and not needing another loop (and possibly avoiding jumping all around memory).

After the first loop, all the triangles are created along the edge of the loop. The next thing to do is to fill in the triangles inside the loop. This means needing to track the points that are already visited. Or rather, what indices need yet to be connected to a triangle. When visualizing the algorithm in Microsoft Paint. I found that the second index cannot be connected to any further triangle. But the first and third can be. So every time a triangle is created, the second index is removed from the list of indices needing to be visited.

When doing this until no new triangles have been created, a mesh has been formed.

int triangulate(int points_length, double2* points, int* out_indices, int* open_indices)
{
	var length = 0;
	
	// Create an open list for points that need to be visited
	// and able to form a triangle from.
	var open_length = points_length;
	for (var i = 0; i < points_length; i++)
		open_indices[i] = i;

	// Repeatedly loop through the points to create triangles
	// until no triangle is created.
	var count = -1;
	while (count != open_length && open_length >= 3)
	{
		count = open_length;
		for (var i = 0; i < open_length; i++)
		{
			// Getting three consecutive points to form a triangle.
			var middle = (i + 1) % open_length;
			var i0 = open_indices[i];
			var i1 = open_indices[middle];
			var i2 = open_indices[(i + 2) % open_length];
			var v0 = points[i0];
			var v1 = points[i1];
			var v2 = points[i2];

			// Do a crossproduct to determine wheather the third point
			// is left or right of the segment created by the
			// first and second point.
			var d0 = v1 - v0;
			var d1 = v2 - v0;
			if ((d0.y * d1.x - d0.x * d1.y) < 0)
				continue;

			// Make sure the possible triangle does not intersect with
			// any previously created triangle.
			if (intersects(i0, i2, points_length, points, length, indices) ||
				intersects(i1, i2, points_length, points, length, indices))
				continue;

			// Create the triangle
			indices[length + 0] = i0;
			indices[length + 1] = i1;
			indices[length + 2] = i2;
			length += 3;

			// Remove the middle/second point from the open list
			open_length--;
			for (var j = middle; j < open_length; j++)
				open_indices[j] = open_indices[j + 1];
		}
	}

	return length;
}