This module 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.
const triangles = Phaser.Geom.Polygon.Earcut([10,0, 0,50, 60,60, 70,10]); // returns [1,0,3, 3,2,1]
Each group of three vertex indices in the resulting array forms a triangle.
// triangulating a polygon with a hole earcut([0,0, 100,0, 100,100, 0,100, 20,20, 80,20, 80,80, 20,80], ); // [3,0,4, 5,4,0, 3,4,7, 5,0,1, 2,3,7, 6,5,1, 2,7,6, 6,1,2] // triangulating a polygon with 3d coords earcut([10,0,1, 0,50,2, 60,60,3, 70,10,4], null, 3); // [1,0,3, 3,2,1]
If you pass a single vertex as a hole, Earcut treats it as a Steiner point.
If your input is a multi-dimensional array (e.g. GeoJSON Polygon), you can convert it to the format
expected by Earcut with
var data = earcut.flatten(geojson.geometry.coordinates); var triangles = earcut(data.vertices, data.holes, data.dimensions);
After getting a triangulation, you can verify its correctness with
var deviation = earcut.deviation(vertices, holes, dimensions, triangles);
Returns the relative difference between the total area of triangles and the area of the input polygon. 0 means the triangulation is fully correct.
For more information see https://github.com/mapbox/earcut
A flat array of vertex coordinate, like [x0,y0, x1,y1, x2,y2, ...]
An array of hole indices if any (e.g. [5, 8] for a 12-vertex input would mean one hole with vertices 5–7 and another with 8–11).
The number of coordinates per vertex in the input array (2 by default).
An array of triangulated data.