Awesome Open Source
Awesome Open Source

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

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:

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.

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