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.
#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 mapboxYou 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:
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.
git clone --recursive https://github.com/mapbox/earcut.hpp.git
cd earcut.hpp
mkdir build
cd build
cmake ..
make
# ./tests
# ./bench
# ./vizVisual 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.
Import the project from https://github.com/mapbox/earcut.hpp.git and you should be good to go!
This is currently based on earcut 2.2.4.
React
Typescript
Django
Laravel
Facebook
Microsoft
Google
Alibaba
D3
Tencent