Repository files navigation

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

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

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

#include<earcut.hpp>

// The number type to use for tessellationusing 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 arrayusing 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.gCGAL).

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

// struct IntPoint {//     int64_t X, Y;// };namespacemapbox {namespaceutil {template<>structnth<0, IntPoint> {inlinestaticautoget(const IntPoint &t) {return t.X;    };};template<>structnth<1, IntPoint> {inlinestaticautoget(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 ofContainer, in particularsize(),empty() andoperator[].

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 sectionUsage.

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:

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

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

git clone --recursive https://github.com/mapbox/earcut.hpp.gitcd earcut.hppmkdir buildcd buildcmake ..make# ./tests# ./bench# ./viz

git clone --recursive https://github.com/mapbox/earcut.hpp.gitcd earcut.hppmkdir projectcd projectcmake .. -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.

Import the project fromhttps://github.com/mapbox/earcut.hpp.git and you should be good to go!

This is currently based onearcut 2.2.4.