Triangulate3DPolygon is a header-only file offering a template-based solution for triangulating three-dimensional, non-complex polygons. This solution is self-contained, requiring no external libraries except for the inclusion of <vector> and <cmath>.
- C++ 11 Standard and above
- Standard Template Library (STL)
The solution works for all kinds of 3D non-complex polygons, concave or convex, open or closed. The routine does not produce new vertices to triangulate the polygon.
- Windows
- Linux
- macOS
The solution uses two techniques for triangulation:
Convex Polygons: Fan triangulation method is utilized for convex polygons, efficiently dividing the polygon into triangles originating from a central point.
Concave Polygons: Earcut triangulation algorithm is used for concave polygons. This method identifies and cuts triangles from the inward-curving parts of the polygon, resulting in a triangulated mesh.
Copy TriangulatePolygon.h to your project and include the file.
#include <iostream>
#include "TriangulatePolygon.h"
int main()
{
std::vector<triangulate::Point> polygon;
polygon.emplace_back(0.0f, 0.0f, 0.0f);
polygon.emplace_back(2.0f, 0.0f, 0.0f);
polygon.emplace_back(2.0f, 2.0f, 0.0f);
polygon.emplace_back(0.0f, 2.0f, 0.0f);
const auto triangles = triangulate::triangulate(polygon);
std::cout << "Triangles " << triangles.size() << std::endl;
}The following sources have been utilized in the development of this solution.
Paul Bourke: The shortest line between two lines in 3D
OpenGL Wiki: Calculating a Surface Normal - Newell's Method
This software is released under the MIT License terms.