Meandering Triangles

Contour lines, also known as isolines, are lines drawn along along paths of constant elevation. They are often used when drawing maps to indicate the slope of hills and mountains:

A contour map

But they can also be used to visualize functions that map (x,y) values to z values, or to find the boundaries of implicit surfaces. One of the common algorithms for finding contour lines is Marching Squares. The algorithm assumes that you have a set of elevation data points spaced out at regular intervals on a grid, and generates contour lines for each square of the grid. A simpler algorithm exists, called Meandering Triangles, and it divides the data points into triangles, rather than squares, to reduce the number of cases the algorithm has to handle. Here, I'll give a full explanation of how the Meandering Triangles algorithm works, with some examples to show it in action.

Meandering Triangles in Action

First, let's see how the meandering triangles algorithm looks:

Step 0: Get Some Data

In order to generate contour lines, we need some data whose contours we want to find.

Step 1: Triangulate

The first step is to divide the regularly spaced grid of elevation data into triangles. In this example, I divide each set of 4 adjacent points into the top-left and bottom-right halves of a square, which forms two triangles.

Step 2: Find Triangles That Intersect Contour Lines

If we assume the elevation data is sampled at a high enough resolution, then each triangle is pretty close to a small, nearly-flat bit of terrain. If we're drawing a contour line at elevation = 0.5, then the triangle will have a contour line going through it if some part of that triangle is below 0.5, and some part of it is above 0.5. The same is true for any threshold, but let's assume we want to draw the contour line for 0.5 in this example. There are four possible cases here:

Here's the code:

Step 3: Find the Contour Line Segments

Once we know that a contour line passes through a triangle, we also know that it passes between the vertices that are above the threshold and those that are below the threshold. Since it's a triangle, we have 1 vertex on one side, and 2 on the other side, and the contour line will pass through 2 of the 3 edges of the triangle. Where along that edge the contour line will cross can be determined by linearly interpolating between the triangle vertices to find where the threshold's exact value should fall.

Step 4: Joining Up

All that's left to do is join up all the adjacent line segments into lines. My implementation builds up contour lines by adding segments to the head and tail of a line until it runs out of connected segments.

And that's it! The example code I've shown here assumes a single fixed threshold, but it's easy to run multiple passes to find contour lines at multiple different thresholds. I think this algorithm is quite elegant in its simplicity, and it runs quickly on arbitrary data. There are certainly better algorithms if you care about the level of detail and have an elevation function that is slow to compute, but this algorithm makes an excellent first draft for finding contour lines.

You can get the full code here.