Triangulation of Polygons

Triangulation is the process of breaking down a shape into a set of triangles. It is often necessary to draw something using GPU, which speaks only to triangles. There are already many great libs and different algorithms for achieving it, but I am going to describe it here anyway. Just for the sake of showing how simple yet powerful it can be.

Ear cut

The funny name of the algorithm has surprisingly a lot in common with the core idea since it's all about cutting ears until there are none left. Before proceeding, here is a bit of terminology:

polygon – shape defined by a sequence of points. Every two consecutive points define a line segment. It is assumed that the last point is connected with the first one, given enclosing the whole thing. So precisely, what we are expecting to see is actually a polygonal chain.

simple polygon – one where no edges intersect.

reflex – a triangle is reflex when it has an angle greater than 180 degrees. It cannot be an ear.

ear – a set of three consecutive vertices of the polygon that form a triangle containing no other vertex than those three.

The algorithm goes as follows:

For a simple polygon, find an ear, remove it from the shape and proceed until there is only one final triangle left.

The process of finding ears requires comparing each point with all the others (to check whether some vertex is inside the triangle). The algorithm is complete after one pass (or the shape is more complicated than we thought and we are doomed). It means the computational complexity is O(n^2).

The basic (stripped) implementation

Below you will find an explanation of the algorithm. It is by far the most concise and the closest to the optimal way of executing it. The code is based on the mapbox/earcut which features a perfect and elegant JS version handling all the edge cases happening in real-world usages. I've studied the code carefully and can confirm that it's absolutely dope.

We will be working on Nodes of the following shape:

type Node {
  x: Number
  y: Number
  prev: Node
  next: Node
}

Which will be chained into doubly-linked lists. Utils for creating the list, removing elements and inserting nodes look like the following:

function insertNode(i, x, y, last) {
  const p = { i, x, y };
  if (!last) {
    p.prev = p;
    p.next = p;
  } else {
    p.next = last.next;
    p.prev = last;
    last.next.prev = p;
    last.next = p;
  }
  return p;
}

function removeNode(p) {
  p.next.prev = p.prev;
  p.prev.next = p.next;
}

function linkedList(data) {
  let i, last;
  for (i = 0; i < data.length; i += 2) {
    last = insertNode(i / 2, data[i], data[i + 1], last);
  }
  return last;
}

Next is a helper for figuring out whether a point is inside a triangle. It is not the only way (and definitely not the easiest to grasp just by looking at the code) but is by far the fastest method. The calculations below are all about checking if a given point is on the correct side of an edge, for each edge of the triangle. You can find more explanation and another approach in this article.

function isInTriangle(a, b, c, p) {
  return (
    (c.x - p.x) * (a.y - p.y) - (a.x - p.x) * (c.y - p.y) >= 0 &&
    (a.x - p.x) * (b.y - p.y) - (b.x - p.x) * (a.y - p.y) >= 0 &&
    (b.x - p.x) * (c.y - p.y) - (c.x - p.x) * (b.y - p.y) >= 0
  );
}

The tool for determining if a given set of points forms a reflex triangle is calculating its area in a way that is sign-sensitive. If the result is negative, the triangle is reflex.

function area(a, b, c) {
  return (b.y - a.y) * (c.x - b.x) - (b.x - a.x) * (c.y - b.y);
}

The most important of those helpers: checking if given three consecutive points form an ear. As I explained before, it's a matter of taking a triangle and checking if any other vertex is placed inside. If not – we've got an ear to cut.

function isEar(ear) {
  const a = ear.prev,
    b = ear,
    c = ear.next;

  // Reflex found.
  if (area(a, b, c) >= 0) return false;

  // Now make sure we don't have other points inside the potential 
  // ear. 
  let p = ear.next.next;

  while (p !== ear.prev) {
    const inTriangle = isInTriangle(a, b, c, p);
    if (inTriangle && area(p.prev, p, p.next) >= 0) return false;
    p = p.next;
  }
  return true;
}

After those, the main algorithm is quite obvious. I am traversing the list, checking if the current node forms an ear. If it does, I remove it and move on. It all continues until it doesn't make much sense to loop more or we've made a full circle.

In this simplified version I give up, but there are many ways to deal with encountered problems.

function earCut(ear) {
  const triangles = [];
  let next = ear.next,
    prev = ear.prev,
    stop = ear;

  while (prev !== next) {
    prev = ear.prev;
    next = ear.next;

    if (isEar(ear)) {
      triangles.push(prev.i, ear.i, next.i);
      removeNode(ear);
      ear = next;
      stop = next;
      continue;
    }

    ear = next;
    if (ear === stop) {
      throw new Error("This triangulation was a disaster");
    }
  }
  return triangles;
}

Checking if it works

The shape I've used in the previous post was generated using the exact code above. Here is example of usage:

const data = [
  0, 80, 100, 0, 190, 85, 270, 35, 345, 140, 255, 130, 215, 210, 140, 70, 45,
  95, 50, 185,
];

const node = linkedList(data);
if (!node || node.next === node.prev) return;
const triangles = earCut(node);
const vertices = triangles.flatMap((i) => [data[2 * i], data[2 * i + 1]]);

console.log("linked list", node);
console.log("triangles", triangles);
console.log("vertices", vertices);

You can check it on your own on any polygon you want. But be warned that it might (and it will) break for more complicated polygons messing with the shapes.

Further advancements

There are some aspects of the algorithm that can be improved.

How to deal with messy data?

There is no easy answer to this question since data can be broken in unlimited ways. One common and easy to fix problem is duplicated vertices. If it is the case, I can help you with the following function (credits go to the mapbox/earcut authors):

function filterPoints(start, end) {
  if (!start) return start;
  if (!end) end = start;
  let p = start,
    again;
  do {
    again = false;
    if (equals(p, p.next) || area(p.prev, p, p.next) === 0) {
      removeNode(p);
      p = end = p.prev;
      if (p === p.next) break;
      again = true;
    } else {
      p = p.next;
    }
  } while (again || p !== end);
  return end;
}

And simply wrap return last in the linkedList function, like that: return filterPoints(last).

What about non-simple polygons?

Check out the first *.pdf listed below. It includes a method for finding a good place for making a cut (i.e. adds an edge) that allows treating the polygon as if it was simple (it just has two edges overlapping).

What about computational complexity?

While O(n^2) is not tragic, it is also far from perfect for bigger shapes. The guys from Mapbox came up with a very clever idea to use Z-order curve. Its best feature here is that it preserves locality, which means that points that are close to each other on 2D surface will remain close in the sorted array. It is a perfect fit for the isEar function since the only way to check whether the given triangle is an ear is to check against all the other points. So if we can start the comparisons against the points that are close to our candidate, it greatly increases our chances to disprove that a given triangle is an ear early on in the loop, therefore saving precious CPU cycles.

But as usual, the reality is harsh and computing the Z-order curve turned out to have not much sense for simpler shapes. The guys at Mapbox chose an arbitrary limit of 80 points until the algorithm started with the reordering.

Cool resources

David Eberly – Triangulation by ear clipping – the original (I believe?) paper about the Ear Cut algorithm. Features an explanation of the algorithm and describes a method for dealing with polygons that are not simple.

mapbox/earcut – great implementation of the Ear Cut algorithm. Uses optimization with z-order curve to more effectively detect ears in shapes having big numbers of triangles.

blackpawn.com/texts/pointinpoly – features a good explanation of the topic of determining whether a point is inside a given triangle.

tchayen/triangolatte – my implementation of Ear Cut in Go. Features examples of triangulating buildings imported from Open Street Map, *.gpx files, rendering triangulated polygons in the browser using WebGL and on desktop using go-gl package.