Earcut.hpp 2.2.4: A Lightweight and High-Performance Polygon Triangulation Library
Triangulation: From Polygon to Triangle
In computer graphics, geographic information systems (GIS), and game development, we often need to handle polygons. However, whether for rendering or physical calculations, the underlying hardware and standard graphics pipelines (such as OpenGL and Vulkan) are best suited for processing triangles. Therefore, the process of decomposing an arbitrary polygon into a set of non-overlapping triangles—known as triangulation—becomes a fundamental and critical task.
The Earcut algorithm was created to solve this problem. Its core idea is very intuitive: for a polygon, repeatedly “cut off” (i.e., triangulate) its “ears.” An “ear” is defined as a convex vertex whose corresponding triangle does not contain any other vertices of the polygon.
earcut.hpp is a C++ port of the famous earcut.js JavaScript library from Mapbox. It is well-received in the C++ community for its efficiency, simplicity, and single-header nature.
Core Features of Earcut.hpp
- Single-header library: Simply include one
earcut.hppheader file to use it in your project, without the need to compile complex third-party libraries, greatly facilitating integration. - High performance: The algorithm implementation is highly optimized, capable of quickly processing complex polygons with hundreds or thousands of vertices, even those with holes.
- Easy to use: The API is extremely simple, usually requiring just one function call.
- Handles complex polygons: Natively supports polygons with any number of holes.
- Robustness: Capable of handling various odd polygon inputs, although extreme degenerate cases (such as self-intersections) still require preprocessing.
Core Concepts and Code Examples
The core function of earcut.hpp is mapbox::earcut<T>. It accepts a nested data structure (such as std::vector<std::vector<std::array<T, 2>>>) and returns a list of triangle indices.
Example 1: Basic Usage – Triangulating a Simple Quadrilateral
Let’s start with the simplest polygon: a rectangle.
// filename: basic_earcut.cpp
#include <iostream>
#include <vector>
#include "earcut.hpp" // Ensure earcut.hpp is in the include path
// Using the mapbox namespace
namespace mapbox {
namespace util {
template <> struct nth<0, std::array<int, 2>> {
inline static auto get(const std::array<int, 2> &t) { return t[0]; };
};
template <> struct nth<1, std::array<int, 2>> {
inline static auto get(const std::array<int, 2> &t) { return t[1]; };
};
}
}
int main() {
// 1. Define the vertices of the polygon.
// Vertices must be ordered (clockwise or counterclockwise, but all contour directions must be consistent).
// Here we use std::array<int, 2> to represent a point [x, y].
// The first element of the outer vector represents the outer contour of the polygon.
std::vector<std::vector<std::array<int, 2>>> polygon;
// Define the four vertices of a rectangle (clockwise or counterclockwise)
std::vector<std::array<int, 2>> exterior = {
{0, 0}, // Bottom left
{100, 0}, // Bottom right
{100, 100}, // Top right
{0, 100} // Top left
};
polygon.push_back(exterior); // Add the outer contour to the polygon
// 2. Perform triangulation!
// The returned indices are a one-dimensional array, with every three elements forming a triangle.
// For example: [0, 1, 2, 0, 2, 3] represents two triangles: (0,1,2) and (0,2,3)
std::vector<uint32_t> indices = mapbox::earcut<uint32_t>(polygon);
// 3. Output the result
std::cout << "Triangulation indices: ";
for (auto i : indices) {
std::cout << i << " ";
}
std::cout << std::endl;
// Explanation of the result:
// We obtained 6 indices: 0, 1, 2, 0, 2, 3
// This corresponds to two triangles:
// Triangle 1: Vertex 0(0,0), Vertex 1(100,0), Vertex 2(100,100)
// Triangle 2: Vertex 0(0,0), Vertex 2(100,100), Vertex 3(0,100)
// This is exactly what we want, dividing the rectangle into two right triangles.
return 0;
}Compilation and Execution: Since it is a header-only library, compilation is very simple:
g++ -std=c++11 -O2 basic_earcut.cpp -o basic_earcutExample 2: Handling Polygons with Holes
This is where earcut.hpp truly shines. Suppose we have an external rectangle with an internal triangular hole that needs to be cut out.
// filename: polygon_with_hole.cpp
#include <iostream>
#include <vector>
#include "earcut.hpp"
// Using double as the coordinate type
namespace mapbox {
namespace util {
template <> struct nth<0, std::array<double, 2>> {
inline static auto get(const std::array<double, 2> &t) { return t[0]; };
};
template <> struct nth<1, std::array<double, 2>> {
inline static auto get(const std::array<double, 2> &t) { return t[1]; };
};
}
}
int main() {
std::vector<std::vector<std::array<double, 2>>> polygon;
// Outer contour - large rectangle (counterclockwise)
std::vector<std::array<double, 2>> exterior = {
{0.0, 0.0},
{10.0, 0.0},
{10.0, 10.0},
{0.0, 10.0}
};
// Inner contour - hole, a triangle (Note: the vertex order of the hole must be opposite to that of the outer contour! Here it is clockwise)
std::vector<std::array<double, 2>> interior = {
{4.0, 4.0},
{6.0, 6.0}, // Note the order: for holes, it is usually clockwise
{2.0, 6.0}
};
polygon.push_back(exterior);
polygon.push_back(interior); // The second vector represents the first hole
// Perform triangulation
auto indices = mapbox::earcut<uint32_t>(polygon);
std::cout << "Indices for polygon with hole: ";
for (auto i : indices) {
std::cout << i << " ";
}
std::cout << std::endl;
std::cout << "Number of triangles: " << indices.size() / 3 << std::endl;
return 0;
}Key Points:
- Vertex Order: The direction of the outer contour and polygon can be arbitrary (clockwise or counterclockwise), but the vertex order of the hole must be opposite to that of the outer contour. This is key to distinguishing between “solid” and “void.”
- Results: The triangulated triangle indices will automatically avoid the hole area, generating triangles that only fill the area between the outer contour and the hole.
Example 3: Using Custom Point Structures
You do not necessarily have to use std::array<T, 2>. earcut.hpp is very flexible and can adapt to any point type by specializing the nth template.
// filename: custom_point.cpp
#include <iostream>
#include <vector>
#include "earcut.hpp"
// Custom point structure
struct MyPoint {
double x;
double y;
// ... can also have other fields, such as color, normals, etc., which earcut will ignore
};
// Specialize the nth template to tell earcut how to get x and y from MyPoint.
namespace mapbox {
namespace util {
template <> struct nth<0, MyPoint> {
inline static double get(const MyPoint &p) { return p.x; };
};
template <> struct nth<1, MyPoint> {
inline static double get(const MyPoint &p) { return p.y; };
};
}
}
int main() {
std::vector<std::vector<MyPoint>> polygon;
std::vector<MyPoint> exterior = {
{0.0, 0.0},
{50.5, 0.0},
{50.5, 30.2},
{0.0, 30.2}
};
polygon.push_back(exterior);
// Now you can directly use MyPoint vectors for triangulation
auto indices = mapbox::earcut<uint32_t>(polygon);
std::cout << "Indices with custom point struct: ";
for (auto i : indices) {
std::cout << i << " ";
}
std::cout << std::endl;
return 0;
}This feature is very powerful, meaning you can directly use existing data structures in your project without the costly data conversion to fit the library API.
Conclusion
earcut.hpp 2.2.4 is a well-designed and powerful triangulation library. Its “single-header” feature minimizes integration costs, while its performance and robustness meet the needs of most production environments. Whether handling simple UI shapes or complex geographic fence data, earcut.hpp is an excellent choice.