Triangulation of polygons
Triangulation is the process of breaking down a shape into set of triangles. It is often necessary in order to draw something using GPU, which speaks only 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. Each two consecutive point 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 optimal way of executing it. The code is based on the mapbox/earcut which features perfect and elegant JS version handling all the edge cases happening in the 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:
const 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
}
const removeNode = p => {
p.next.prev = p.prev
p.prev.next = p.next
}
const 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 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.
const isInTriangle = (a, b, c, p) =>
(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 form a reflex triangle is calculating its area with a way that is sign sensitive. If the result is negative, the triangle is reflex.
const area = (a, b, c) => (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.
const 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 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.
const 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 some 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 with you with following function (credits go to the mapbox/earcut authors):
const 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 good place for making a cut (i.e. adds an edge) that allows to treat 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. It's 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 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 arbitrary limit of 80 points until the algorithm starts with the reordering.
Cool resources
David Eberly – Triangulation by ear clipping – the original (I believe?) article about Ear Cut algorithm. Features 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 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.
