How to triangulate any 2D polygon in O(nlogn) time

This write-up was heavily influenced by the slides from UC Irvine: https://www.ics.uci.edu/~goodrich/teach/geom/notes/Triangulation-slides-notes.pdf.

This write-up exists to clarify my understanding of how the algorithms work and to put these slides into actual complete sentences.

To introduce the topic in question, let’s go over some very basic ideas in computational geometry, a subfield of both computer science and mathematics.

• A 2-dimensional (2D) simple polygon is a polygon that has edges that do not intersect with each other. A polygon consists of polygon curves, a finite number of line segments.

For example, the shape that is configured when an octagon is completely inside another octagon is a simple polygon with 16 vertices and 16 edges.

• A triangulation of a polygon P is a decomposition of P into triangles whose vertices are vertices of P.

<image>

We can say that a simple polygon P with n vertices can be broken into a triangulation with n-2 triangles. In the base case of a triangle, this is inherently true — a triangle has three vertices and it itself is a single triangle. In the case of a square, we can draw a line between either of the two diagonals to get two triangles. This identity can be intuitively proven with induction.

A question that arises from these definitions is “how can we triangulate any simple polygon?” It’s rather simple to do so when given a pen and a simple polygon on a piece of paper — just draw lines until you have n-2 triangles for a simple polygon with n sides. However, when it comes to computers, the task becomes a little more difficult. How would a computer decide when to connect two vertices together to make a triangle? We can try to take a greedy approach by first creating a triangle then connecting an adjacent vertex to the existing triangulation but when this algorithm is given to a computer, it would struggle to find a triangulation given a weird simple polygon.

<image> w/ caption “it would struggle with this simple polygon”

A greedy approach is to compare vertices to other vertices to find valid triangulations, but this comes at a great cost — time efficiency. This algorithm would run in the order of O(n²). Computational geometrists solved the problem of triangulating a simple polygon with great time efficiency, resulting in algorithms that do so in O(nlogn) time and O(n) time. In this write-up we’ll go over the O(nlogn) algorithm because according to UCI and MIT professors, the O(n) algorithm is very complex and I’ll take their word for it.

This algorithm can be broken into two different parts:

1. Split the simple polygon into x-monotone polygons. O(nlogn) time.
2. Triangulate the x-monotone polygons. O(n) time.

An x-monotone polygon is x-monotone if and only if a vertical line (a line parallel to the y-axis) can “sweep” through the polygon and only encounter connected components. These components can consist of either just points or two line segments.

Side note: Sweep line algorithms (https://en.wikipedia.org/wiki/Sweep_line_algorithm) are why I started writing this article and why I wrote the code for it. In our minds imagining a line sweeping through a polygon is easy to do but writing the code to have a line literally sweep through the entire polygon is both difficult and inefficient. This duality allowed me to have even more respect for researchers in computer science and mathematics.

<image> cap: x-monotone

<image> cap: not x-monotone

The first part of the algorithm involves something called trapezoidal decomposition. We sweep through all the vertices with a line parallel to the y-axis from the leftmost vertex to the rightmost vertex. Doing this creates trapezoids because the shapes that are left behind look like trapezoids (sometimes… kind of). These trapezoids will have one or two vertices that are shared with the original simple polygon. When hitting any vertex, we draw a vertical line that crosses the vertex and connects to the polygon curves above and below.

<image>

When performing the sweep line algorithm, we try to find special vertices called split and merge vertices. Split vertices are the first vertices that we encounter in the sweep line algorithm that creates an interior in the simple polygon.

<image>

Merge vertices are the last vertices that we encounter in the sweep line algorithm that ends the interior created from split vertices in the simple polygon.

<image>

These vertices are the reasons we can have non x-monotone polygons, so finding these vertices are essential to being able to split the simple polygon to x-monotone polygons.

After the sweep line algorithm is finished, we are left with a simple polygon that was split into trapezoids with a potential list of split and merge vertices. In the case where there is no list of split and merge vertices, we can simply move on to the next step of the algorithm since the whole polygon is already x-monotone. However, in the case where the list is nonempty, we need to manipulate the split and merge vertices. For any split vertices, there has to be a trapezoid to the left of it. Before, we declared that a trapezoid will always have one or two vertices that are shared with the original simple polygon and in this case, it will always have two vertices. What we do here is connect the two vertices in the original polygon, the split vertex and the other vertex. We do the same thing for a merge vertex but for the trapezoid to the right.

<image>

What we just did was we found the potential reasons why the polygon may have been non x-monotone and patched it. This trapezoidal decomposition takes O(nlogn) time because in order to perform this sweep line algorithm, we had to sort all of the vertices by their x-coordinates from smallest to greatest (assuming the leftmost vertex has the smallest x-coordinate value). Performing the sweep shortly after is a simple iteration via for loop and does not affect the larger big-O time complexity.

In order to triangulate these brand new x-monotone polygons, we need to break them into upper and lower chains. A chain of a polygon is the set of vertices that connect the left and rightmost vertices. The names of the upper and lower chains are rather intuitive — the upper chain is the one that exists above the lower chain. After separating these x-monotone polygons into their upper and lower chains, we can now triangulate these polygons.

You can see my implementation for this section on my GitHub account: <link>. As a brief digression, I had a GitHub account (victorzhen117) but I used my school’s email account as the username (is that a bad thing to publicly say?). However, I don’t have access to that email account anymore because the school deleted it on account of me graduating so I can’t use that GitHub account anymore. I created a new account so I could publicize some things I’ve been working on on the side.

Triangulating an x-monotone polygon is fairly straightforward. In the previous algorithm, we obtained a list of x-monotone polygons via their upper and lower chains. We will use these later, but we can combine these chains into the list of vertices that make up the x-monotone polygons, sorted by x-coordinate values, into a new list. Given this list, we can now perform the triangulation algorithm.

First, keep a stack called a reflex chain that will store vertices. This chain refers to a group of points that create reflex angles (interior angles of > 180 degrees).

<image>

We perform a sweep line algorithm that begins with the leftmost x-coordinate and moves rightward. Push the first two vertices into the reflex chain. When sweeping into a new vertex, consider the following conditions:

1. The new vertex is opposite of the reflex chain. In other words, the new vertex is not in the same (upper vs. lower) chain. In this case, keep the topmost value in the stack and connect all the vertices in the reflex chain to the new vertex into triangles. Redefine the reflex chain as the old topmost value in the stack and the new vertex.

<image>

1. The new vertex is not opposite of the reflex chain and the new vertex creates a reflex angle with the top two elements in the reflex chain. When this happens, push the new vertex into the reflex chain.

<image>

1. The new vertex is not opposite of the reflex chain and the new vertex creates an angle that is less than 180 degrees. While the topmost value and the second topmost value create a 180 degree angle with the new vertex, connect the three points to make triangles and pop the topmost value in the reflex chain. After the while condition no longer holds true, push the new vertex into the reflex chain.

<image>

One of the difficulties that I encountered when writing the code for this was trying to define what a reflex angle is. As I previously mentioned, it is rather easy to look at an angle in a polygon on a piece of paper and determine whether or not it is a reflex angle or not. Programmatically, this is very different and non-intuitive. If you’d like, you can try this problem out: given three vertices, determine if the angle created by these three vertices is greater than 180 degrees.

Hopefully, you didn’t take too much time and skipped right to this explanation because it turns out that that problem is impossible to solve. How do you know where the polygon exists, above or below the three vertices? What formula would you use to compute the angle? It’s these kinds of questions that stay under the radar that computational geometrists have to solve that makes the field so interesting. It turns out that the upper and lower chains come into play here because they dictate where the polygon exists, and the formula used to compute the angle comes from the manipulation of the cross and dot products of two vectors.

<image>

With these three conditions paved out, an x-monotone polygon will be triangulated, and after this algorithm is implemented on all the x-monotone polygons, we have a triangulated 2D simple polygon. :)