DELAUNAY TRIANGULATION

The Delaunay Triangulation, developed by Boris Delaunay in 1934, is a way of triangulating a set of points in a way that generally avoids long, thin triangles. Its use is seen throughout engineering and computer science, whenever we need to generate a mesh from a set of points.

CONTROLS

Click to add a point
Click and drag to move a point
Click a point to remove it

HOW IT WORKS

There are many algorithms to create a Delaunay triangulation. Here, I implemented the Bowyer-Watson algorithm, which isn't the fastest, but it's much more intuitive than the competition. But before going into the algorithm, we must first understand what a Delaunay Triangulation is.

WHAT IS A DELAUNAY TRIANGULATION

It's pretty common to want to connect a bunch of points with triangles, whether we're making a 3D model or trying to create a stable structure. As you can imagine, there are many, many ways to draw these triangles, but some of them are more preferable than others. Ideally, we would want nice, big triangles, not long, thin ones. The Delaunay Triangulation ensures that we get as few thin triangles as possible.

In particular, Delaunay Triangulations maximize the smallest angle out of all the triangles. Small angles lead to long, thin triangles, so by maximizing the smallest angle, we can avoid these problematic triangles. If a triangulation does not follow this property of maximizing the smallest angle, we say it is no longer Delaunay.

THE BOWYER-WATSON ALGORITHM

The Bowyer-Watson algorithm is the most well-known and easily understood way of generating a Delaunay Triangulation. The algorithm itself is not especially interesting, but the principles behind it are applicable to a wide range of problems.

The basic idea behind the algorithm is that we start with one triangle, and successively add points until the triangulation is no longer Delaunay. At this point, we remove the points violating the constraint, and add them back around our new point to make sure everything is in order. This concept of building a solution by removing the parts that don't work and adding them back later is seen everywhere in computer science. It's related to backtracking, a common way to solve sudoku puzzles.