Awesome Open Source
Awesome Open Source


A C++ port of earcut.js, a fast, header-only polygon triangulation library.

Travis AppVeyor Coverage Coverity Scan Average time to resolve an issue Percentage of issues still open Mourner

The library implements a modified ear slicing algorithm, optimized by z-order curve hashing and extended to handle holes, twisted polygons, degeneracies and self-intersections in a way that doesn't guarantee correctness of triangulation, but attempts to always produce acceptable results for practical data like geographical shapes.

It's based on ideas from FIST: Fast Industrial-Strength Triangulation of Polygons by Martin Held and Triangulation by Ear Clipping by David Eberly.


#include <earcut.hpp>
// The number type to use for tessellation
using Coord = double;

// The index type. Defaults to uint32_t, but you can also pass uint16_t if you know that your
// data won't have more than 65536 vertices.
using N = uint32_t;

// Create array
using Point = std::array<Coord, 2>;
std::vector<std::vector<Point>> polygon;

// Fill polygon structure with actual data. Any winding order works.
// The first polyline defines the main polygon.
polygon.push_back({{100, 0}, {100, 100}, {0, 100}, {0, 0}});
// Following polylines define holes.
polygon.push_back({{75, 25}, {75, 75}, {25, 75}, {25, 25}});

// Run tessellation
// Returns array of indices that refer to the vertices of the input polygon.
// e.g: the index 6 would refer to {25, 75} in this example.
// Three subsequent indices form a triangle. Output triangles are clockwise.
std::vector<N> indices = mapbox::earcut<N>(polygon);

Earcut can triangulate a simple, planar polygon of any winding order including holes. It will even return a robust, acceptable solution for non-simple poygons. Earcut works on a 2D plane. If you have three or more dimensions, you can project them onto a 2D surface before triangulation, or use a more suitable library for the task (e.g CGAL).

It is also possible to use your custom point type as input. There are default accessors defined for std::tuple, std::pair, and std::array. For a custom type (like Clipper's IntPoint type), do this:

// struct IntPoint {
//     int64_t X, Y;
// };

namespace mapbox {
namespace util {

template <>
struct nth<0, IntPoint> {
    inline static auto get(const IntPoint &t) {
        return t.X;
template <>
struct nth<1, IntPoint> {
    inline static auto get(const IntPoint &t) {
        return t.Y;

} // namespace util
} // namespace mapbox

You can also use a custom container type for your polygon. Similar to std::vector, it has to meet the requirements of Container, in particular size(), empty() and operator[].

example triangulation

Additional build instructions

In case you just want to use the earcut triangulation library; copy and include the header file <earcut.hpp> in your project and follow the steps documented in the section Usage.

If you want to build the test, benchmark and visualization programs instead, follow these instructions:


Before you continue, make sure to have the following tools and libraries installed:

Note: On some operating systems such as Windows, manual steps are required to add cmake and git to your PATH environment variable.

Manual compilation

git clone --recursive
cd earcut.hpp
mkdir build
cd build
cmake ..
# ./tests
# ./bench
# ./viz

Visual Studio, Eclipse, XCode, ...

git clone --recursive
cd earcut.hpp
mkdir project
cd project
cmake .. -G "Visual Studio 14 2015"
::you can also generate projects for "Visual Studio 12 2013", "XCode", "Eclipse CDT4 - Unix Makefiles"

After completion, open the generated project with your IDE.

CLion, Visual Studio 2017

Import the project from and you should be good to go!


This is currently based on earcut 2.2.2.

Get A Weekly Email With Trending Projects For These Topics
No Spam. Unsubscribe easily at any time.
c (15,504
cpp (1,334
algorithm (507
rendering (173
header-only (156
geometry (115
polygon (37
triangulation (29