earcut.hpp: A C repository from okkez

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

// Run tessellation
// Returns array of indices that refer to the vertices of the input polygon.
// Three subsequent indices form a triangle.
std::vector<N> indices = mapbox::earcut<N>(polygon);

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

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/Other)
cmake 3.2+ (Ubuntu/Windows/Other)
OpenGL SDK (Ubuntu/Windows/Apple)
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

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

okkez/earcut.hpp