Triangulation: Introduction

In this post, we will move away from the abstract mathematics of the last several posts, and onto a very practical problem: point set triangulation.

Point set triangulation, like every interesting problem in computer science, is actually quite straightforward at first glance. The problem starts with a set of distinct points on a two-dimensional plane, like so:

One note before we continue: there is a restriction on the points, and that is that they are not all colinear. If they all lie on a single, common line, you would not be able to draw a triangle between three of the points. For the rest of this article, we will assume that the input point set is not degenerate. We will also assume that the input point set contains at least three points: otherwise, you couldn't draw a triangle at all!.

A solution to the problem is a set of straight edges connecting the points in the point set, with the following requirements:

• The edges of the convex hull of the point set must be included
• The graph must be connected (ie, there must be a path between every pair of points) and planar (ie, lines cannot cross, but may meet at one of the points)
• Every face (except the outer face) must be a triangle (hence, you are 'triangulating' the points)

Here is a solution for the point set above:

As I said, this is straightforward at first glance. If I drew a bunch of dots on a piece of paper, and gave you a pencil and a ruler, I have no doubt that you could solve the problem with no mathematical or programming training. (Give it a try!)

I can assure you, however, that the problem is richer if you give it a second glance. For instance, if I gave the same set of points to two different people, it is quite likely that I would get back two different solutions:

Which solution is correct? They both are. In general, point sets do not have unique triangulations, although there are exceptional cases that do.^[1]

Before we examine the problem more closely, we should first answer that most pivotal of philosophical questions, "who cares?" Specifically, why would anyone want to triangulate a point set? Like almost everything on this blog, we find an application in video game development: height maps. Here, we have a regular grid of X,Y sample points (although regularity is not required), and each sample point has an associated height value Z. If we triangulate the points based off of their X,Y coordinates, and then draw triangles corresponding to the full X,Y,Z triple, we get a 3D model of terrain suitable for the ground of, say, an outdoor 3D game. As an example, the ground of World of Warcraft is a height map.

We will now transition from the realm of theory to that of practice. In theory, any triangulation of the point set is as good as any other: each meets the criterion specified. In applications, however, we sometimes find that one triangulation is 'better' than another. For instance, consider the following two triangulations of the same point set:

Now, consider if those points were assigned a Z value equal to their distance from the center of the diagram. In the first triangulation, the resulting terrain mesh would be a crater-shaped depression. In the second triangulation, the same points would have produced a pair of depressions more closely resembling a wall socket. Which solution is correct in this case? It depends on your application, but I believe that most people would consider the first triangulation to more correctly match the terrain if we are considering height maps.

There are numerous strategies for selecting a 'best' triangulation for an application. Maybe you want to make sure that your triangles do not have small angles; this is the case in 3D engines, where 'skinny' triangles tend to lead to numerical instability during rendering. Maybe you want to minimize the sum of the lengths of the edges; this is the case if your points represent cities on a map and you want to build roads between them. Maybe you just want to compute the triangulation quickly and are willing to trade speed for optimality and settle for an answer that only approximately meets your other criteria.

There are two things you can't come up with strategies for, however: the number of triangles or the number of edges. Every triangulation of a given point set has the same number of triangles and edges; these are both specified as a function of the number of vertices and the number of vertices which are part of the convex hull of the point set. Specifically, you will have 2(v - 1) - h triangles, and 3(v - 1) - h edges. (A handy mnemonic for remembering these formulas is to note the formulas are the same except for the constant 2 or 3, and that E and 3 are similar in shape.)

In the next post, we will look at a seemingly unrelated geometry problem which will turn out to have a very useful side effect for the problem of point set triangulation.

---

[1] One configuration of points that admits a unique triangulation is N points, where N-1 of those points are collinear. The resulting triangulation will have a fan shape, where every collinear point is connected to the 'outlier' point:

As a special case, note that if you have N = 3 points, you always satisfy this criterion: pick any two points, and they give you a line, and the third point won't be on that line. Thus, the triangulation of three points is unique. (It is exactly the triangle formed with those three points as vertices.)

It is important to note, however, that as soon as you have a second 'outlier', the uniqueness of the solution is lost, as can be seen with the 'crater height map' example, above.

There may be other configurations; but off hand I do not know them, and I suspect they do not exist.