Triangulating polygons with Ear-Clipping

This is a part of the triangulation series.

Picture made by John Law

Introduction

Ear-Clipping is one of the techniques to triangulate polygons. In the scope of this article, I’ll show you examples of **simple polygons** in 2D space and implement an Ear-Clipping algorithm in python. Our task for the current article is: Having a set of points and a path of how the points are connected, building a set of triangles inside the polygon. As always, I’ll stick to a real example of why we need it.

In the end, we need to get a function which triangulates a polygon.

What is a polygon?

A polygon is a two-dimensional geometric shape defined by a set of vertices (points) connected by straight-line segments. The line segments form the sides of the polygon, and the vertices are the points where the sides meet. Polygons can be classified based on the number of sides they have. For example, a polygon with three sides is called a triangle, a polygon with four sides is called a quadrilateral, and a polygon with more than four sides is called an n-gon. We are going to deal only with simple polygons.

Let’s generate a couple of simple polygons.

Example of simple polygons. Link to Jupyter

Why do we need to triangulate a polygon? Or, how many cans of paint do I need to draw a picture on the wall?

Imagine a real task. We want to draw a picture on the wall in the form of a polygon, but we don’t know how much paint we need in the end. However, we know that one can of paint covers three sq m of an area. We just need to find an area of the desired polygon to calculate the number of cans. How to do this? In this case, we would need to split the polygon into simplest polygons (triangles) that never intersect and compute the area of each triangle, which is an easy task. Then summarise all triangle areas, and we get the common area of the polygon.

One of the ways to split polygons into collections of triangles is using the Ear-Clipping algorithm. It works by iteratively selecting an “ear,” a triangle formed by three consecutive vertices of the polygon, and removing it from the polygon. And an “ear” cannot contain any other vertices of the polygon inside it. The algorithm continues until the polygon is wholly triangulated.

Triangulation with Ear-Clipping

In our example above, we have a collection of points and paths by which we want the points to be connected. What we need to do now is to iterate through all neighbour points and check if they form a triangle inside of the polygon. When three vertices form an “ear”, — register it and remove the “ear” point from the collection of vertices.

Algorithm in details

1 We need to agree on which winding order we are working. I prefer counter-clockwise order. That is why, before starting triangulation, I go by the path and check the direction. If I get the path in clockwise order, I just flip the path. The function is named **orient_path.** You can check the implementation and use it.

    # make sure that the direction is counter-clockwise
    path = orient_path(vertices, path)

2Of course, you want to check boundaries. And if the polygon has only two or fewer points, well, it is not a polygon. If the polygon contains only 3 points — we have a single triangle.

3We make a loop till we have only 3 points left in the polygon. And inside the loop, we need the go through three consecutive vertices. I always choose a current point and its two neighbours from left and right. It is a matter of your choice. You can improvise here.

while len(rest) > 3:
    # length of the residual path
    rest_len = len(rest)
    for i in range(rest_len):
        id0 = rest[(i - 1) % rest_len]
        id1 = rest[i]
        id2 = rest[(i + 1) % rest_len]

4 Next, we check if the polygon is convex or concave in the current angle. If it is convex, we have a potential “Ear”. Up to this moment, we must be sure that we know in which direction we are going by the path. Therefore the first step should be done up to this moment. Again, you can have different ways of checking, like taking a centroid and checking if it is inside the polygon. Then winding direction is not necessary.

# skipping the iteration if the polygon is concave in the current angle
if not is_convex(p0, p1, p2):
    continue

5 When step 4 says it is our potential “Ear”, we need to check if all other points from the polygon stay outside the triangle. In case any of the points are inside the triangle — it is not an “Ear”, and we can go to the next vertex.

  is_ear = True
  for j in rest_points:
      if is_point_in_triangle(vertices[j], p0, p1, p2):
          is_ear = False
          break

6 Well, the last step is pure enjoinment because we know that we have found our “Ear”. We just need to register the triangle, and one more important step is to extract the current vertex from the path. As it already contributed to the triangulation and can rest for now (-:

if is_ear:
    triangles.append([id0, id1, id2])
    del rest[i]
    break

Of course, we still miss additional checks if the polygon is simple and doesn’t contain intersections. Also, some of the provided iterations are not optimised and were done only for better explanation. If you want to improve the implementation, I’d suggest reading about Euler’s characteristics and vectorising the computations. Other than that, it is quite a working solution.

Triangulation process with Ear-Clipping

Solving our task about paint.

Well, I like linear algebra, so I’ll solve it by taking the cross product of the edges of triangles. You can find an explanation of how I get area on the math is fun website.

coords = points[triangles]
# it is also twice the area of the triangles
crosses = np.cross(coords[:,1] - coords[:,0], coords[:,2] - coords[:,0],)
common_area = np.sum(crosses) / 2
print(common_area)

And the result is 13. Assuming we have coordinates in the metric system, we can say 13 sq m. Do you remember which area you can cover with one can of paint? Right, 3 sq m. Now question for you, how many cans do you need? My suggestion: “Always buy a bit more paint than needed so kids can play as well 😇”

Conclusion

I’ll skip an extensive conclusion for now, as it’ll be reasonable to have a conclusion when we compare different triangulation techniques.

So far, we got what a polygon is. We know why we would need to triangulate it. And we know how to triangulate a simple polygon with Ear-clipping. As for me, it is a good start.

You can see the results of the triangulation in a notebook https://github.com/DPSoftware/triangulation_articles/blob/main/ear_clipping.ipynb