// main ear slicing loop which triangulates a polygon (given as a linked list) function earcutLinked( ear, triangles, dim, minX, minY, invSize, pass ) { if ( ! ear ) return; // interlink polygon nodes in z-order if ( ! pass && invSize ) indexCurve( ear, minX, minY, invSize ); let stop = ear, prev, next; // iterate through ears, slicing them one by one while ( ear.prev !== ear.next ) { prev = ear.prev; next = ear.next; if ( invSize ? isEarHashed( ear, minX, minY, invSize ) : isEar( ear ) ) { // cut off the triangle triangles.push( prev.i / dim | 0 ); triangles.push( ear.i / dim | 0 ); triangles.push( next.i / dim | 0 ); removeNode( ear ); // skipping the next vertex leads to less sliver triangles ear = next.next; stop = next.next; continue; } ear = next; // if we looped through the whole remaining polygon and can't find any more ears if ( ear === stop ) { // try filtering points and slicing again if ( ! pass ) { earcutLinked( filterPoints( ear ), triangles, dim, minX, minY, invSize, 1 ); // if this didn't work, try curing all small self-intersections locally } else if ( pass === 1 ) { ear = cureLocalIntersections( filterPoints( ear ), triangles, dim ); earcutLinked( ear, triangles, dim, minX, minY, invSize, 2 ); // as a last resort, try splitting the remaining polygon into two } else if ( pass === 2 ) { splitEarcut( ear, triangles, dim, minX, minY, invSize ); } break; } } } // check whether a polygon node forms a valid ear with adjacent nodes function isEar( ear ) { const a = ear.prev, b = ear, c = ear.next; if ( area( a, b, c ) >= 0 ) return false; // reflex, can't be an ear // now make sure we don't have other points inside the potential ear const ax = a.x, bx = b.x, cx = c.x, ay = a.y, by = b.y, cy = c.y; // triangle bbox; min & max are calculated like this for speed const x0 = ax < bx ? ( ax < cx ? ax : cx ) : ( bx < cx ? bx : cx ), y0 = ay < by ? ( ay < cy ? ay : cy ) : ( by < cy ? by : cy ), x1 = ax > bx ? ( ax > cx ? ax : cx ) : ( bx > cx ? bx : cx ), y1 = ay > by ? ( ay > cy ? ay : cy ) : ( by > cy ? by : cy ); let p = c.next; while ( p !== a ) { if ( p.x >= x0 && p.x <= x1 && p.y >= y0 && p.y <= y1 && pointInTriangle( ax, ay, bx, by, cx, cy, p.x, p.y ) && area( p.prev, p, p.next ) >= 0 ) return false; p = p.next; } return true; } function isEarHashed( ear, minX, minY, invSize ) { const a = ear.prev, b = ear, c = ear.next; if ( area( a, b, c ) >= 0 ) return false; // reflex, can't be an ear const ax = a.x, bx = b.x, cx = c.x, ay = a.y, by = b.y, cy = c.y; // triangle bbox; min & max are calculated like this for speed const x0 = ax < bx ? ( ax < cx ? ax : cx ) : ( bx < cx ? bx : cx ), y0 = ay < by ? ( ay < cy ? ay : cy ) : ( by < cy ? by : cy ), x1 = ax > bx ? ( ax > cx ? ax : cx ) : ( bx > cx ? bx : cx ), y1 = ay > by ? ( ay > cy ? ay : cy ) : ( by > cy ? by : cy ); // z-order range for the current triangle bbox; const minZ = zOrder( x0, y0, minX, minY, invSize ), maxZ = zOrder( x1, y1, minX, minY, invSize ); let p = ear.prevZ, n = ear.nextZ; // look for points inside the triangle in both directions while ( p && p.z >= minZ && n && n.z <= maxZ ) { if ( p.x >= x0 && p.x <= x1 && p.y >= y0 && p.y <= y1 && p !== a && p !== c && pointInTriangle( ax, ay, bx, by, cx, cy, p.x, p.y ) && area( p.prev, p, p.next ) >= 0 ) return false; p = p.prevZ; if ( n.x >= x0 && n.x <= x1 && n.y >= y0 && n.y <= y1 && n !== a && n !== c && pointInTriangle( ax, ay, bx, by, cx, cy, n.x, n.y ) && area( n.prev, n, n.next ) >= 0 ) return false; n = n.nextZ; } // look for remaining points in decreasing z-order while ( p && p.z >= minZ ) { if ( p.x >= x0 && p.x <= x1 && p.y >= y0 && p.y <= y1 && p !== a && p !== c && pointInTriangle( ax, ay, bx, by, cx, cy, p.x, p.y ) && area( p.prev, p, p.next ) >= 0 ) return false; p = p.prevZ; } // look for remaining points in increasing z-order while ( n && n.z <= maxZ ) { if ( n.x >= x0 && n.x <= x1 && n.y >= y0 && n.y <= y1 && n !== a && n !== c && pointInTriangle( ax, ay, bx, by, cx, cy, n.x, n.y ) && area( n.prev, n, n.next ) >= 0 ) return false; n = n.nextZ; } return true; } // go through all polygon nodes and cure small local self-intersections function cureLocalIntersections( start, triangles, dim ) { let p = start; do { const a = p.prev, b = p.next.next; if ( ! equals( a, b ) && intersects( a, p, p.next, b ) && locallyInside( a, b ) && locallyInside( b, a ) ) { triangles.push( a.i / dim | 0 ); triangles.push( p.i / dim | 0 ); triangles.push( b.i / dim | 0 ); // remove two nodes involved removeNode( p ); removeNode( p.next ); p = start = b; } p = p.next; } while ( p !== start ); return filterPoints( p ); } // try splitting polygon into two and triangulate them independe