polytri

polytri is a polygon triangulator for simple polygons without holes based on Raimund Seidel's algorithm [1].

Usage

/* Define this in a single compilation unit. */
#define POLYTRI_IMPLEMENTATION
#include "polytri/polytri.hpp"

/* Any type goes if they have public x / y attributes. */
template<typename T>
struct Vertex_t {
  T x{};
  T y{};
};

/* The vertices list is expect to be a Container-type. */
template<typename T>
using Contour_t = std::vector<Vertex_t<T>>;

int main(int argc, char *argv[])
{
  /* Contour must be in counter clockwise order. */
  std::vector<Contour_t<float>> polygons = {
    { {-10.0, -9.0}, {11.0, -12.0}, {0.0, 8.0}, {-5.0, 11.0} }
  };

  auto indices = PolyTri::Triangulate( polygons );

  for (auto const& i : indices) {
    std::cerr << i << " ";
  }
  std::cerr << "\n";

  return 0;
}

Limitations

Triangulating polygons with holes is technically possible but not currently supported. You can check those libraries for alternatives :

• Triangle, A Two-Dimensional Quality Mesh Generator and Delaunay Triangulator.
• mapbox/earcut.hpp, A C++ port of earcut.js, a fast, header-only polygon triangulation library.

---

References

1. R. Seidel. A simple and fast incremental randomized algorithm for computing trapezoidal decompositions and for triangulating polygons. Comput. Geom. Theory Appl., 1:51–64, 1991.
2. A. Narkhede and D. Manocha, Fast Polygon Triangulation Based on Seidel's Algorithm, Department of Computer Science, UNC Chapel Hill.
3. Fournier, Alain & Montuno, Delfin. (1984). Triangulating Simple Polygons and Equivalent Problems. ACM Trans. Graph.. 3. 153-174. 10.1145/357337.357341.
4. M. de Berg, O. Cheong, M. van Kreveld, M. Overmars. Computational Geometry, Algorithms and Applications, Third Edition, Chap. 3 Polygon Triangulation, Springer, 2008.