In this brief article, I will discuss the preliminaries of polygon triangulation using the APL programming language. Triangulation is an important concept in computational geometry, and it has applications in various fields, such as computer graphics, mesh generation, and finite element analysis. Triangular meshes are often used to represent surfaces in computer graphics, and they are also used in finite element analysis to approximate the solution of partial differential equations.


A convex polygon is a polygon in which all its interior angles are less than 180 degrees with vertices defined by V=(x1,y1),(x2,y2),,(xn,yn)V = {(x_1, y_1), (x_2, y_2), \ldots, (x_n, y_n)}, where nn is the number of vertices. Triangulation is the partitioning of a polygon with nn vertices into n2n-2 triangles by adding n3n-3 non-intersecting diagonals, which connect non-adjacent vertices.

Due to Euler, the total amount of ways to triangulate a nn-gon is given by the (n2)(n-2)-th Catalan number:

Cn=1n+1(2nn)C_n = \frac{1}{n+1}\binom{2n}{n}

Asymptotically, Catalan numbers grow as:

Cn4nn3/2πC_n \sim \frac{4^n}{n^{3/2}\sqrt{\pi}}

Consequently, the algorithm enumerating all possible triangulations of a polygon is exponential in time complexity.

Unconstrainted triangulation

If we wish to triangulate a polygon without any constraints, the fan triangulation of any polynomial can be computed in linear time:

Fan triangulation of a septagon

Once we pick a starting vertex v0v_0, we can connect it to all other vertices v1,v2,,vn1v_1, v_2, \ldots, v_{n-1}, creating n2n-2 triangles.

Another method of unconstrained triangulation is the ear-clipping algorithm, which is computed in O(n2)\mathcal O(n^2) time. The algorithm iteratively removes “ears” from the polygon, where an ear is a triangle with two consecutive edges of the polygon and the third edge inside the polygon. We begin the implementation with a function that given three points determines if they form a convex angle:

Sign{a b c(b-a)-.×c-a}
Convex0 Sign

The next step is to determine, given a point pp, whether it lies inside the triangle abcabc. For this purpose, we could make use of barycentric coordinates, but the naive method (checking on which side of the half-plane created by the edges the point resides) is sufficient for our purposes:

InTriangle{a b c0 (~.<.>) Sign¨ ( a b) ( b c) ( c a)}

The method for finding the ears is then straightforward. We return the ear and the rest of the polygon in a tuple. We implement checks in order to determine if the polygon is large enough, then iterate over the consecutive 3-triplets of vertices, to then determine if they form an ear. The first ear found is returned and its vertex is removed from the polygon.

  3>: 3=: 
    ~Convex :1

The triangulation function successively removes ears from the polygon until only three vertices remain and returns the resulting triangulation:

Triangulate{3>:e rEar(,e)r}

To test our code, we will use the following polygon:

polygon(1 2) (3 5) (¯2 5) (¯6 2) (¯5 ¯2) (¯2 ¯1)

We will also plot it using Desmos:

The polygon

The resulting triangulation is given by:

  Triangulate polygon
││¯2 ¯11 23 5│││¯2 ¯13 5¯2 5│││¯2 ¯1¯2 5¯6 2│││¯6 2¯5 ¯2¯2 ¯1││
The resulting triangulation

Constrained triangulation

Suppose that we wish to triangulate a nn-gon into n2n-2 triangles T=t1,t2,,tn2T = {t_1, t_2, \ldots, t_{n-2}}, where each triangle tit_i is defined by the vertices vi=vi1,vi2,vi3v_i = {v_{i1}, v_{i2}, v_{i3}}. We can then define a cost function f:TRf : T \to \mathbb R that assigns a cost to each triangle. The cost function can be defined in various ways, such as the area of the triangle, the length of the edges, or the angle between the edges. The constrained triangulation problem is then to find the cost of the triangulation that minimizes the cost function.

Suppose that we have the following cost function, which assigns the cost of a triangle to be the sum of the lengths of its edges:

Cost{1(1×-)/¨0 1 2(2)¨}

The naive solution to this problem runs in exponential time through testing all possible triangulations:

  1,i jj<i+2:¯1
  /{(i  MTC )+( j MTC )+Cost[i j ]}¨i+j-i+1}

Nonetheless, for small polygons, it’s rather fast:

  MTC polygon
  cmpx 'MTC polygon'

We can improve upon this solution making use of Dynamic Programming: Many recursive calls in the naive solution are repeated, so we can store the results of these calls in a table and use them to avoid recomputation. We accomplish it via the use of the memo operator from the dfns workspace:

    i jj<i+2:¯1
    /{(f i )+(f  j)+Cost P[i j ]}¨i+j-i+1
  f 1,P}