Hello !

This is the second part to my series of posts describing the 2D vector graphics system behind Top's user interface. This one will focus on the triangulation of polygons, an essential operation when filling user-defined paths.

As we saw in the previous post, the user can describe a path using line segments and cubic Bezier curves. But as we can approximate those curves with series of line segments, the paths we have to fill are really polygons. Currently, my implementation of the fill function imposes the constraint that those polygons must not self-intersect and don't have holes. That's a reasonable assumption for a gui, and if we ever needed a self intersecting polygon it could be achieved by splitting the path at the intersections to create a set of non intersecting polygons. Except for this limitation, paths can represent any polygon, convex or concave, in any winding convention.

We want to triangulate said polygon, which means split it in no overlapping triangles to be sent to the GPU for rendering. Such a triangulation always exists and the number of triangles for n-gon is n-2. This theorem can be proved by a simple induction :

- Base case : n = 3. Obviously we can triangulate a triangle and the number of triangles in that triangulation is one.
- Now consider a
*n*-gon **P** and suppose we know the theorem holds for all m < n. We chose a convex vertex p of **P** and q and r the previous and next vertices in a given winding order.
- If [
*q;r*] is a diagonal, split **P** along [*q;r*]. It gives us a triangle and a (*n-1*)-gon. We now have a triangulation of **P** with (*n-1*)*-2+1 = n-2* triangles.
- If [
*q;r*] is not a diagonal, let s be the concave vertex inside triangle (*p,q,r*) which is farthest form (*q;r*). [*p;s*] is a diagonal, so we can split **P** in two polygons with j and k vertices, and we know they can be triangulated with j-2 and k-2 triangles. Furthermore, we now that n = j + k - 2. So **P** can be triangulated with j-2+k-2 = n-2 triangles.

This demonstration also gives us a first approach to implement the triangulation, which is called ear-clipping (at each step we can find a diagonal and clip one “ear”, ie one triangle). This approach is in O(*n*^{2}) time, because we recursively find diagonals in O(*n*) time. But there are better approach performance-wise, one good compromise in terms of simplicity vs performance being in O(*n*.log(*n*)), which I will describe here.

Fig. 1 : Triangulating a monotone polygon. Green lines are valid diagonals. Red dotted lines are invalid diagonals. Red dots are vertices on the stack.

(...)

Read more →