mapbox / Earcut.hpp

Earcut

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

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.

Usage

#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[].

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:

Dependencies

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

• git (Ubuntu/Windows/macOS)
• cmake 3.2+ (Ubuntu/Windows/macOS)
• OpenGL SDK (Ubuntu/Windows/macOS)
• Compiler such as GCC 4.9+, Clang 3.4+, MSVC12+

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 https://github.com/mapbox/earcut.hpp.git
cd earcut.hpp
mkdir build
cd build
cmake ..
make
# ./tests
# ./bench
# ./viz

Visual Studio, Eclipse, XCode, ...

git clone --recursive https://github.com/mapbox/earcut.hpp.git
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 https://github.com/mapbox/earcut.hpp.git and you should be good to go!

Status

This is currently based on earcut 2.2.2.