Take a look at this:
This is a triangulation of a set of random points, such that all the points are connected to one another, all of the faces are triangles, and the edges include the convex hull of the points.
I would like to claim that this is not a very “good” triangulation. This algorithm tends to produce lots of long, slivery triangles, and a really uneven distribution of edge counts across different vertices – some vertices have way more edges than they need to.
Here’s a different triangulation. These are the exact same points, but I triangulated them smarter:
Isn’t that better? (Click to compare!)
Depending on your dice rolls you might still have a few slivers, usually around the outer perimeter, but I’m willing to bet that it’s a noticeable improvement over the first attempt.
This triangulation is called the Delaunay triangulation, and I would like to claim that it is a very good triangulation. It is, in fact, the best possible triangulation, for some definitions of “best.”
Why should I, a busy person with important responsibilities, care about triangles?
Okay, right, good question. You’ve made it this far in life without triangulating anything; why should you start now?
There are some obvious applications of triangulation algorithms in computer graphics, where everything is made out of triangles, but you knew that already and you are still unmoved.
Let’s try something else.
One textbook example of a non-graphics application of the Delaunay triangulation is interpolating spatial data.
Pretend, for a moment, that you’re a surveyor, and you’ve just finished measuring the elevation of a bunch of discrete points in some area. You sling your weird tripod thingy over your shoulder, and get ready to leave for the first vacation you’ve been able to take with your son since Terence left – when your boss appears at your door.
“What’s the elevation three clicks south of the north ridge, or however surveyors talk?” she asks.
You glance down at the oversized roll of mapping paper (?) on your desk, but you already know what you’ll find: you didn’t take a measurement three clicks south of the north ridge. But you did measure a few points nearby. Perhaps, you think, I can construct a triangulation of these points, and then map it to a three-dimensional mesh, and use that to interpolate the elevations between nearby points.
You call your son to tell him that you’ll be a little late – it’s 1998 in this situation; texting isn’t a thing yet – and get to work.
But after the montage ends, you look upon your work, and find… oh.
Well that’s not going to work.