{"version":3,"file":"index.umd.cjs","sources":["../src/earcut.ts","../src/index.ts"],"sourcesContent":["/**\r\n * Triangulate an outline.\r\n *\r\n * @param vertices A flat array of vertice coordinates like [x0,y0, x1,y1, x2,y2, ...].\r\n * @param holes An array of hole indices if any (e.g. [5, 8] for a 12-vertice input would mean one hole with vertices 5–7 and another with 8–11).\r\n * @param dimensions The number of coordinates per vertice in the input array (2 by default).\r\n * @return A flat array with each group of three numbers indexing a triangle in the `vertices` array.\r\n * @example earcut([10,0, 0,50, 60,60, 70,10]); // returns [1,0,3, 3,2,1]\r\n * @example with a hole: earcut([0,0, 100,0, 100,100, 0,100,  20,20, 80,20, 80,80, 20,80], [4]); // [3,0,4, 5,4,0, 3,4,7, 5,0,1, 2,3,7, 6,5,1, 2,7,6, 6,1,2]\r\n * @example with 3d coords: earcut([10,0,1, 0,50,2, 60,60,3, 70,10,4], null, 3); // [1,0,3, 3,2,1]\r\n */\r\nexport function earcut(vertices: ArrayLike<number>, holes?: ArrayLike<number>, dimensions?: number)\r\n{\r\n    dimensions = dimensions || 2;\r\n\r\n    const hasHoles = holes && holes.length;\r\n    const outerLen = hasHoles ? holes[0] * dimensions : vertices.length;\r\n    let outerNode = linkedList(vertices, 0, outerLen, dimensions, true);\r\n    const triangles: number[] = [];\r\n\r\n    if (!outerNode || outerNode.next === outerNode.prev) return triangles;\r\n\r\n    let minX: number;\r\n    let minY: number;\r\n    let maxX: number;\r\n    let maxY: number;\r\n    let x: number;\r\n    let y: number;\r\n    let invSize: number;\r\n\r\n    if (hasHoles) outerNode = eliminateHoles(vertices, holes, outerNode, dimensions);\r\n\r\n    // if the shape is not too simple, we'll use z-order curve hash later; calculate polygon bbox\r\n    if (vertices.length > 80 * dimensions)\r\n    {\r\n        minX = maxX = vertices[0];\r\n        minY = maxY = vertices[1];\r\n\r\n        for (let i = dimensions; i < outerLen; i += dimensions)\r\n        {\r\n            x = vertices[i];\r\n            y = vertices[i + 1];\r\n            if (x < minX) minX = x;\r\n            if (y < minY) minY = y;\r\n            if (x > maxX) maxX = x;\r\n            if (y > maxY) maxY = y;\r\n        }\r\n\r\n        // minX, minY and invSize are later used to transform coords into integers for z-order calculation\r\n        invSize = Math.max(maxX - minX, maxY - minY);\r\n        invSize = invSize !== 0 ? 32767 / invSize : 0;\r\n    }\r\n\r\n    earcutLinked(outerNode, triangles, dimensions, minX, minY, invSize, 0);\r\n\r\n    return triangles;\r\n}\r\n\r\n// create a circular doubly linked list from polygon points in the specified winding order\r\nfunction linkedList(data: ArrayLike<number>, start: number, end: number, dim: number, clockwise: boolean)\r\n{\r\n    let i: number;\r\n    let last: Node;\r\n\r\n    if (clockwise === (signedArea(data, start, end, dim) > 0))\r\n    {\r\n        for (i = start; i < end; i += dim) last = insertNode(i, data[i], data[i + 1], last);\r\n    }\r\n    else\r\n    {\r\n        for (i = end - dim; i >= start; i -= dim) last = insertNode(i, data[i], data[i + 1], last);\r\n    }\r\n\r\n    if (last && equals(last, last.next))\r\n    {\r\n        removeNode(last);\r\n        last = last.next;\r\n    }\r\n\r\n    return last;\r\n}\r\n\r\n// eliminate colinear or duplicate points\r\nfunction filterPoints(start: Node, end?: Node)\r\n{\r\n    if (!start) return start;\r\n    if (!end) end = start;\r\n\r\n    let p = start;\r\n    let again: boolean;\r\n    do\r\n    {\r\n        again = false;\r\n\r\n        if (!p.steiner && (equals(p, p.next) || area(p.prev, p, p.next) === 0))\r\n        {\r\n            removeNode(p);\r\n            p = end = p.prev;\r\n            if (p === p.next) break;\r\n            again = true;\r\n        }\r\n        else\r\n        {\r\n            p = p.next;\r\n        }\r\n    } while (again || p !== end);\r\n\r\n    return end;\r\n}\r\n\r\n// main ear slicing loop which triangulates a polygon (given as a linked list)\r\nfunction earcutLinked(ear: Node, triangles: number[], dim: number, minX: number, minY: number, invSize: number, pass?: number)\r\n{\r\n    if (!ear) return;\r\n\r\n    // interlink polygon nodes in z-order\r\n    if (!pass && invSize) indexCurve(ear, minX, minY, invSize);\r\n\r\n    let stop = ear;\r\n    let prev: Node;\r\n    let next: Node;\r\n\r\n    // iterate through ears, slicing them one by one\r\n    while (ear.prev !== ear.next)\r\n    {\r\n        prev = ear.prev;\r\n        next = ear.next;\r\n\r\n        if (invSize ? isEarHashed(ear, minX, minY, invSize) : isEar(ear))\r\n        {\r\n            // cut off the triangle\r\n            triangles.push(prev.i / dim | 0);\r\n            triangles.push(ear.i / dim | 0);\r\n            triangles.push(next.i / dim | 0);\r\n\r\n            removeNode(ear);\r\n\r\n            // skipping the next vertex leads to less sliver triangles\r\n            ear = next.next;\r\n            stop = next.next;\r\n\r\n            continue;\r\n        }\r\n\r\n        ear = next;\r\n\r\n        // if we looped through the whole remaining polygon and can't find any more ears\r\n        if (ear === stop)\r\n        {\r\n            // try filtering points and slicing again\r\n            if (!pass)\r\n            {\r\n                earcutLinked(filterPoints(ear), triangles, dim, minX, minY, invSize, 1);\r\n\r\n                // if this didn't work, try curing all small self-intersections locally\r\n            }\r\n            else if (pass === 1)\r\n            {\r\n                ear = cureLocalIntersections(filterPoints(ear), triangles, dim);\r\n                earcutLinked(ear, triangles, dim, minX, minY, invSize, 2);\r\n\r\n                // as a last resort, try splitting the remaining polygon into two\r\n            }\r\n            else if (pass === 2)\r\n            {\r\n                splitEarcut(ear, triangles, dim, minX, minY, invSize);\r\n            }\r\n\r\n            break;\r\n        }\r\n    }\r\n}\r\n\r\n// check whether a polygon node forms a valid ear with adjacent nodes\r\nfunction isEar(ear: Node)\r\n{\r\n    const a = ear.prev;\r\n    const b = ear;\r\n    const c = ear.next;\r\n\r\n    if (area(a, b, c) >= 0) return false; // reflex, can't be an ear\r\n\r\n    // now make sure we don't have other points inside the potential ear\r\n    const ax = a.x; const bx = b.x; const cx = c.x; const ay = a.y; const by = b.y; const\r\n        cy = c.y;\r\n\r\n    // triangle bbox; min & max are calculated like this for speed\r\n    const x0 = ax < bx ? (ax < cx ? ax : cx) : (bx < cx ? bx : cx);\r\n    const y0 = ay < by ? (ay < cy ? ay : cy) : (by < cy ? by : cy);\r\n    const x1 = ax > bx ? (ax > cx ? ax : cx) : (bx > cx ? bx : cx);\r\n    const y1 = ay > by ? (ay > cy ? ay : cy) : (by > cy ? by : cy);\r\n\r\n    let p = c.next;\r\n    while (p !== a)\r\n    {\r\n        if (p.x >= x0 && p.x <= x1 && p.y >= y0 && p.y <= y1\r\n            && pointInTriangle(ax, ay, bx, by, cx, cy, p.x, p.y)\r\n            && area(p.prev, p, p.next) >= 0) return false;\r\n        p = p.next;\r\n    }\r\n\r\n    return true;\r\n}\r\n\r\nfunction isEarHashed(ear: Node, minX: number, minY: number, invSize: number)\r\n{\r\n    const a = ear.prev;\r\n    const b = ear;\r\n    const c = ear.next;\r\n\r\n    if (area(a, b, c) >= 0) return false; // reflex, can't be an ear\r\n\r\n    const ax = a.x;\r\n    const bx = b.x;\r\n    const cx = c.x;\r\n    const ay = a.y;\r\n    const by = b.y;\r\n    const cy = c.y;\r\n\r\n    // triangle bbox; min & max are calculated like this for speed\r\n    const x0 = ax < bx ? (ax < cx ? ax : cx) : (bx < cx ? bx : cx);\r\n    const y0 = ay < by ? (ay < cy ? ay : cy) : (by < cy ? by : cy);\r\n    const x1 = ax > bx ? (ax > cx ? ax : cx) : (bx > cx ? bx : cx);\r\n    const y1 = ay > by ? (ay > cy ? ay : cy) : (by > cy ? by : cy);\r\n\r\n    // z-order range for the current triangle bbox;\r\n    const minZ = zOrder(x0, y0, minX, minY, invSize);\r\n    const maxZ = zOrder(x1, y1, minX, minY, invSize);\r\n\r\n    let p = ear.prevZ;\r\n    let n = ear.nextZ;\r\n\r\n    // look for points inside the triangle in both directions\r\n    while (p && p.z >= minZ && n && n.z <= maxZ)\r\n    {\r\n        if (p.x >= x0 && p.x <= x1 && p.y >= y0 && p.y <= y1 && p !== a && p !== c\r\n            && pointInTriangle(ax, ay, bx, by, cx, cy, p.x, p.y) && area(p.prev, p, p.next) >= 0) return false;\r\n        p = p.prevZ;\r\n\r\n        if (n.x >= x0 && n.x <= x1 && n.y >= y0 && n.y <= y1 && n !== a && n !== c\r\n            && pointInTriangle(ax, ay, bx, by, cx, cy, n.x, n.y) && area(n.prev, n, n.next) >= 0) return false;\r\n        n = n.nextZ;\r\n    }\r\n\r\n    // look for remaining points in decreasing z-order\r\n    while (p && p.z >= minZ)\r\n    {\r\n        if (p.x >= x0 && p.x <= x1 && p.y >= y0 && p.y <= y1 && p !== a && p !== c\r\n            && pointInTriangle(ax, ay, bx, by, cx, cy, p.x, p.y) && area(p.prev, p, p.next) >= 0) return false;\r\n        p = p.prevZ;\r\n    }\r\n\r\n    // look for remaining points in increasing z-order\r\n    while (n && n.z <= maxZ)\r\n    {\r\n        if (n.x >= x0 && n.x <= x1 && n.y >= y0 && n.y <= y1 && n !== a && n !== c\r\n            && pointInTriangle(ax, ay, bx, by, cx, cy, n.x, n.y) && area(n.prev, n, n.next) >= 0) return false;\r\n        n = n.nextZ;\r\n    }\r\n\r\n    return true;\r\n}\r\n\r\n// go through all polygon nodes and cure small local self-intersections\r\nfunction cureLocalIntersections(start: Node, triangles: number[], dim: number)\r\n{\r\n    let p = start;\r\n    do\r\n    {\r\n        const a = p.prev;\r\n        const b = p.next.next;\r\n\r\n        if (!equals(a, b) && intersects(a, p, p.next, b) && locallyInside(a, b) && locallyInside(b, a))\r\n        {\r\n            triangles.push(a.i / dim | 0);\r\n            triangles.push(p.i / dim | 0);\r\n            triangles.push(b.i / dim | 0);\r\n\r\n            // remove two nodes involved\r\n            removeNode(p);\r\n            removeNode(p.next);\r\n\r\n            p = start = b;\r\n        }\r\n        p = p.next;\r\n    } while (p !== start);\r\n\r\n    return filterPoints(p);\r\n}\r\n\r\n// try splitting polygon into two and triangulate them independently\r\nfunction splitEarcut(start: Node, triangles: number[], dim: number, minX: number, minY: number, invSize: number)\r\n{\r\n    // look for a valid diagonal that divides the polygon into two\r\n    let a = start;\r\n    do\r\n    {\r\n        let b = a.next.next;\r\n        while (b !== a.prev)\r\n        {\r\n            if (a.i !== b.i && isValidDiagonal(a, b))\r\n            {\r\n                // split the polygon in two by the diagonal\r\n                let c = splitPolygon(a, b);\r\n\r\n                // filter colinear points around the cuts\r\n                a = filterPoints(a, a.next);\r\n                c = filterPoints(c, c.next);\r\n\r\n                // run earcut on each half\r\n                earcutLinked(a, triangles, dim, minX, minY, invSize, 0);\r\n                earcutLinked(c, triangles, dim, minX, minY, invSize, 0);\r\n\r\n                return;\r\n            }\r\n            b = b.next;\r\n        }\r\n        a = a.next;\r\n    } while (a !== start);\r\n}\r\n\r\n// link every hole into the outer loop, producing a single-ring polygon without holes\r\nfunction eliminateHoles(data: ArrayLike<number>, holeIndices: ArrayLike<number>, outerNode: Node, dim: number)\r\n{\r\n    const queue: Node[] = [];\r\n    let i: number;\r\n    let len: number;\r\n    let start: number;\r\n    let end: number;\r\n    let list: Node;\r\n\r\n    for (i = 0, len = holeIndices.length; i < len; i++)\r\n    {\r\n        start = holeIndices[i] * dim;\r\n        end = i < len - 1 ? holeIndices[i + 1] * dim : data.length;\r\n        list = linkedList(data, start, end, dim, false);\r\n        if (list === list.next) list.steiner = true;\r\n        queue.push(getLeftmost(list));\r\n    }\r\n\r\n    queue.sort(compareX);\r\n\r\n    // process holes from left to right\r\n    for (i = 0; i < queue.length; i++)\r\n    {\r\n        outerNode = eliminateHole(queue[i], outerNode);\r\n    }\r\n\r\n    return outerNode;\r\n}\r\n\r\nfunction compareX(a: { x: number; }, b: { x: number; })\r\n{\r\n    return a.x - b.x;\r\n}\r\n\r\n// find a bridge between vertices that connects hole with an outer ring and and link it\r\nfunction eliminateHole(hole: Node, outerNode: Node)\r\n{\r\n    const bridge = findHoleBridge(hole, outerNode);\r\n    if (!bridge)\r\n    {\r\n        return outerNode;\r\n    }\r\n\r\n    const bridgeReverse = splitPolygon(bridge, hole);\r\n\r\n    // filter collinear points around the cuts\r\n    filterPoints(bridgeReverse, bridgeReverse.next);\r\n\r\n    return filterPoints(bridge, bridge.next);\r\n}\r\n\r\n// David Eberly's algorithm for finding a bridge between hole and outer polygon\r\nfunction findHoleBridge(hole: Node, outerNode: Node)\r\n{\r\n    let p = outerNode;\r\n    const hx = hole.x;\r\n    const hy = hole.y;\r\n    let qx = -Infinity;\r\n    let m: Node;\r\n\r\n    // find a segment intersected by a ray from the hole's leftmost point to the left;\r\n    // segment's endpoint with lesser x will be potential connection point\r\n    do\r\n    {\r\n        if (hy <= p.y && hy >= p.next.y && p.next.y !== p.y)\r\n        {\r\n            const x = p.x + (hy - p.y) * (p.next.x - p.x) / (p.next.y - p.y);\r\n            if (x <= hx && x > qx)\r\n            {\r\n                qx = x;\r\n                m = p.x < p.next.x ? p : p.next;\r\n                if (x === hx) return m; // hole touches outer segment; pick leftmost endpoint\r\n            }\r\n        }\r\n        p = p.next;\r\n    } while (p !== outerNode);\r\n\r\n    if (!m) return null;\r\n\r\n    // look for points inside the triangle of hole point, segment intersection and endpoint;\r\n    // if there are no points found, we have a valid connection;\r\n    // otherwise choose the point of the minimum angle with the ray as connection point\r\n\r\n    const stop = m;\r\n    const mx = m.x;\r\n    const my = m.y;\r\n    let tanMin = Infinity;\r\n    let tan: number;\r\n\r\n    p = m;\r\n\r\n    do\r\n    {\r\n        if (hx >= p.x && p.x >= mx && hx !== p.x\r\n            && pointInTriangle(hy < my ? hx : qx, hy, mx, my, hy < my ? qx : hx, hy, p.x, p.y))\r\n        {\r\n            tan = Math.abs(hy - p.y) / (hx - p.x); // tangential\r\n\r\n            if (locallyInside(p, hole)\r\n                && (tan < tanMin || (tan === tanMin && (p.x > m.x || (p.x === m.x && sectorContainsSector(m, p))))))\r\n            {\r\n                m = p;\r\n                tanMin = tan;\r\n            }\r\n        }\r\n\r\n        p = p.next;\r\n    } while (p !== stop);\r\n\r\n    return m;\r\n}\r\n\r\n// whether sector in vertex m contains sector in vertex p in the same coordinates\r\nfunction sectorContainsSector(m: Node, p: Node)\r\n{\r\n    return area(m.prev, m, p.prev) < 0 && area(p.next, m, m.next) < 0;\r\n}\r\n\r\n// interlink polygon nodes in z-order\r\nfunction indexCurve(start: Node, minX: number, minY: number, invSize: number)\r\n{\r\n    let p = start;\r\n    do\r\n    {\r\n        if (p.z === 0) p.z = zOrder(p.x, p.y, minX, minY, invSize);\r\n        p.prevZ = p.prev;\r\n        p.nextZ = p.next;\r\n        p = p.next;\r\n    } while (p !== start);\r\n\r\n    p.prevZ.nextZ = null;\r\n    p.prevZ = null;\r\n\r\n    sortLinked(p);\r\n}\r\n\r\n// Simon Tatham's linked list merge sort algorithm\r\n// http://www.chiark.greenend.org.uk/~sgtatham/algorithms/listsort.html\r\nfunction sortLinked(list: Node)\r\n{\r\n    let i: number;\r\n    let p: Node;\r\n    let q: Node;\r\n    let e: Node;\r\n    let tail: Node;\r\n    let numMerges: number;\r\n    let pSize: number;\r\n    let qSize: number;\r\n    let inSize = 1;\r\n\r\n    do\r\n    {\r\n        p = list;\r\n        list = null;\r\n        tail = null;\r\n        numMerges = 0;\r\n\r\n        while (p)\r\n        {\r\n            numMerges++;\r\n            q = p;\r\n            pSize = 0;\r\n            for (i = 0; i < inSize; i++)\r\n            {\r\n                pSize++;\r\n                q = q.nextZ;\r\n                if (!q) break;\r\n            }\r\n            qSize = inSize;\r\n\r\n            while (pSize > 0 || (qSize > 0 && q))\r\n            {\r\n                if (pSize !== 0 && (qSize === 0 || !q || p.z <= q.z))\r\n                {\r\n                    e = p;\r\n                    p = p.nextZ;\r\n                    pSize--;\r\n                }\r\n                else\r\n                {\r\n                    e = q;\r\n                    q = q.nextZ;\r\n                    qSize--;\r\n                }\r\n\r\n                if (tail) tail.nextZ = e;\r\n                else list = e;\r\n\r\n                e.prevZ = tail;\r\n                tail = e;\r\n            }\r\n\r\n            p = q;\r\n        }\r\n\r\n        tail.nextZ = null;\r\n        inSize *= 2;\r\n    } while (numMerges > 1);\r\n\r\n    return list;\r\n}\r\n\r\n// z-order of a point given coords and inverse of the longer side of data bbox\r\nfunction zOrder(x: number, y: number, minX: number, minY: number, invSize: number)\r\n{\r\n    // coords are transformed into non-negative 15-bit integer range\r\n    x = (x - minX) * invSize | 0;\r\n    y = (y - minY) * invSize | 0;\r\n\r\n    x = (x | (x << 8)) & 0x00FF00FF;\r\n    x = (x | (x << 4)) & 0x0F0F0F0F;\r\n    x = (x | (x << 2)) & 0x33333333;\r\n    x = (x | (x << 1)) & 0x55555555;\r\n\r\n    y = (y | (y << 8)) & 0x00FF00FF;\r\n    y = (y | (y << 4)) & 0x0F0F0F0F;\r\n    y = (y | (y << 2)) & 0x33333333;\r\n    y = (y | (y << 1)) & 0x55555555;\r\n\r\n    return x | (y << 1);\r\n}\r\n\r\n// find the leftmost node of a polygon ring\r\nfunction getLeftmost(start: Node)\r\n{\r\n    let p = start;\r\n    let leftmost = start;\r\n    do\r\n    {\r\n        if (p.x < leftmost.x || (p.x === leftmost.x && p.y < leftmost.y)) leftmost = p;\r\n        p = p.next;\r\n    } while (p !== start);\r\n\r\n    return leftmost;\r\n}\r\n\r\n// check if a point lies within a convex triangle\r\nfunction pointInTriangle(ax: number, ay: number, bx: number, by: number, cx: number, cy: number, px: number, py: number)\r\n{\r\n    return (cx - px) * (ay - py) >= (ax - px) * (cy - py)\r\n        && (ax - px) * (by - py) >= (bx - px) * (ay - py)\r\n        && (bx - px) * (cy - py) >= (cx - px) * (by - py);\r\n}\r\n\r\n// check if a diagonal between two polygon nodes is valid (lies in polygon interior)\r\nfunction isValidDiagonal(a: Node, b: Node)\r\n{\r\n    return a.next.i !== b.i && a.prev.i !== b.i && !intersectsPolygon(a, b) // dones't intersect other edges\r\n        && (locallyInside(a, b) && locallyInside(b, a) && middleInside(a, b) // locally visible\r\n            && (area(a.prev, a, b.prev) || area(a, b.prev, b)) // does not create opposite-facing sectors\r\n            || equals(a, b) && area(a.prev, a, a.next) > 0 && area(b.prev, b, b.next) > 0); // special zero-length case\r\n}\r\n\r\n// signed area of a triangle\r\nfunction area(p: { y: number; x: number; }, q: { y: number; x: number; }, r: { x: number; y: number; })\r\n{\r\n    return (q.y - p.y) * (r.x - q.x) - (q.x - p.x) * (r.y - q.y);\r\n}\r\n\r\n// check if two points are equal\r\nfunction equals(p1: { x: number; y: number; }, p2: { x: number; y: number; })\r\n{\r\n    return p1.x === p2.x && p1.y === p2.y;\r\n}\r\n\r\n// check if two segments intersect\r\nfunction intersects(p1: { x: number, y: number }, q1: { x: number, y: number }, p2: { x: number, y: number }, q2: { x: number, y: number })\r\n{\r\n    const o1 = sign(area(p1, q1, p2));\r\n    const o2 = sign(area(p1, q1, q2));\r\n    const o3 = sign(area(p2, q2, p1));\r\n    const o4 = sign(area(p2, q2, q1));\r\n\r\n    if (o1 !== o2 && o3 !== o4) return true; // general case\r\n\r\n    if (o1 === 0 && onSegment(p1, p2, q1)) return true; // p1, q1 and p2 are collinear and p2 lies on p1q1\r\n    if (o2 === 0 && onSegment(p1, q2, q1)) return true; // p1, q1 and q2 are collinear and q2 lies on p1q1\r\n    if (o3 === 0 && onSegment(p2, p1, q2)) return true; // p2, q2 and p1 are collinear and p1 lies on p2q2\r\n    if (o4 === 0 && onSegment(p2, q1, q2)) return true; // p2, q2 and q1 are collinear and q1 lies on p2q2\r\n\r\n    return false;\r\n}\r\n\r\n// for collinear points p, q, r, check if point q lies on segment pr\r\nfunction onSegment(p: { x: number; y: number; }, q: { x: number; y: number; }, r: { x: number; y: number; })\r\n{\r\n    return q.x <= Math.max(p.x, r.x) && q.x >= Math.min(p.x, r.x) && q.y <= Math.max(p.y, r.y) && q.y >= Math.min(p.y, r.y);\r\n}\r\n\r\nfunction sign(num: number)\r\n{\r\n    return num > 0 ? 1 : num < 0 ? -1 : 0;\r\n}\r\n\r\n// check if a polygon diagonal intersects any polygon segments\r\nfunction intersectsPolygon(a: Node, b: Node)\r\n{\r\n    let p = a;\r\n    do\r\n    {\r\n        if (p.i !== a.i && p.next.i !== a.i && p.i !== b.i && p.next.i !== b.i\r\n            && intersects(p, p.next, a, b)) return true;\r\n        p = p.next;\r\n    } while (p !== a);\r\n\r\n    return false;\r\n}\r\n\r\n// check if a polygon diagonal is locally inside the polygon\r\nfunction locallyInside(a: Node, b: Node)\r\n{\r\n    return area(a.prev, a, a.next) < 0\r\n        ? area(a, b, a.next) >= 0 && area(a, a.prev, b) >= 0\r\n        : area(a, b, a.prev) < 0 || area(a, a.next, b) < 0;\r\n}\r\n\r\n// check if the middle point of a polygon diagonal is inside the polygon\r\nfunction middleInside(a: Node, b: Node)\r\n{\r\n    let p = a;\r\n    let inside = false;\r\n    const px = (a.x + b.x) / 2;\r\n    const py = (a.y + b.y) / 2;\r\n    do\r\n    {\r\n        if (((p.y > py) !== (p.next.y > py)) && p.next.y !== p.y\r\n            && (px < (p.next.x - p.x) * (py - p.y) / (p.next.y - p.y) + p.x))\r\n        { inside = !inside; }\r\n        p = p.next;\r\n    } while (p !== a);\r\n\r\n    return inside;\r\n}\r\n\r\n// link two polygon vertices with a bridge; if the vertices belong to the same ring, it splits polygon into two;\r\n// if one belongs to the outer ring and another to a hole, it merges it into a single ring\r\nfunction splitPolygon(a: Node, b: Node)\r\n{\r\n    const a2 = new Node(a.i, a.x, a.y);\r\n    const b2 = new Node(b.i, b.x, b.y);\r\n    const an = a.next;\r\n    const bp = b.prev;\r\n\r\n    a.next = b;\r\n    b.prev = a;\r\n\r\n    a2.next = an;\r\n    an.prev = a2;\r\n\r\n    b2.next = a2;\r\n    a2.prev = b2;\r\n\r\n    bp.next = b2;\r\n    b2.prev = bp;\r\n\r\n    return b2;\r\n}\r\n\r\n// create a node and optionally link it with previous one (in a circular doubly linked list)\r\nfunction insertNode(i: number, x: number, y: number, last: Node)\r\n{\r\n    const p = new Node(i, x, y);\r\n\r\n    if (!last)\r\n    {\r\n        p.prev = p;\r\n        p.next = p;\r\n    }\r\n    else\r\n    {\r\n        p.next = last.next;\r\n        p.prev = last;\r\n        last.next.prev = p;\r\n        last.next = p;\r\n    }\r\n\r\n    return p;\r\n}\r\n\r\nfunction removeNode(p: Node)\r\n{\r\n    p.next.prev = p.prev;\r\n    p.prev.next = p.next;\r\n\r\n    if (p.prevZ) p.prevZ.nextZ = p.nextZ;\r\n    if (p.nextZ) p.nextZ.prevZ = p.prevZ;\r\n}\r\n\r\nclass Node\r\n{\r\n    i: number;\r\n    x: number;\r\n    y: number;\r\n    prev: Node;\r\n    next: Node;\r\n    z: number;\r\n    prevZ: Node;\r\n    nextZ: Node;\r\n    steiner: boolean;\r\n\r\n    constructor(i: number, x: number, y: number)\r\n    {\r\n        // vertex index in coordinates array\r\n        this.i = i;\r\n\r\n        // vertex coordinates\r\n        this.x = x;\r\n        this.y = y;\r\n\r\n        // previous and next vertex nodes in a polygon ring\r\n        this.prev = null;\r\n        this.next = null;\r\n\r\n        // z-order curve value\r\n        this.z = 0;\r\n\r\n        // previous and next nodes in z-order\r\n        this.prevZ = null;\r\n        this.nextZ = null;\r\n\r\n        // indicates whether this is a steiner point\r\n        this.steiner = false;\r\n    }\r\n}\r\n\r\n/**\r\n * Returns the relative difference between the total area of triangles and the area of the input polygon. 0 means the triangulation is fully correct.\r\n * @param vertices same as earcut\r\n * @param holes same as earcut\r\n * @param dimensions same as earcut\r\n * @param triangles see return value of earcut\r\n * @example\r\n *     const triangles = earcut(vertices, holes, dimensions);\r\n *  const deviation = earcut.deviation(vertices, holes, dimensions, triangles);\r\n */\r\n// return a percentage difference between the polygon area and its triangulation area;\r\n// used to verify correctness of triangulation\r\nexport function deviation(vertices: ArrayLike<number>, holes: ArrayLike<number>, dimensions: number, triangles: ArrayLike<number>)\r\n{\r\n    const hasHoles = holes && holes.length;\r\n    const outerLen = hasHoles ? holes[0] * dimensions : vertices.length;\r\n\r\n    let polygonArea = Math.abs(signedArea(vertices, 0, outerLen, dimensions));\r\n    if (hasHoles)\r\n    {\r\n        for (let i = 0, len = holes.length; i < len; i++)\r\n        {\r\n            const start = holes[i] * dimensions;\r\n            const end = i < len - 1 ? holes[i + 1] * dimensions : vertices.length;\r\n            polygonArea -= Math.abs(signedArea(vertices, start, end, dimensions));\r\n        }\r\n    }\r\n\r\n    let trianglesArea = 0;\r\n    for (let i = 0; i < triangles.length; i += 3)\r\n    {\r\n        const a = triangles[i] * dimensions;\r\n        const b = triangles[i + 1] * dimensions;\r\n        const c = triangles[i + 2] * dimensions;\r\n        trianglesArea += Math.abs(\r\n            (vertices[a] - vertices[c]) * (vertices[b + 1] - vertices[a + 1])\r\n            - (vertices[a] - vertices[b]) * (vertices[c + 1] - vertices[a + 1]));\r\n    }\r\n\r\n    return polygonArea === 0 && trianglesArea === 0 ? 0\r\n        : Math.abs((trianglesArea - polygonArea) / polygonArea);\r\n}\r\n\r\nfunction signedArea(data: ArrayLike<number>, start: number, end: number, dim: number)\r\n{\r\n    let sum = 0;\r\n    for (let i = start, j = end - dim; i < end; i += dim)\r\n    {\r\n        sum += (data[j] - data[i]) * (data[i + 1] + data[j + 1]);\r\n        j = i;\r\n    }\r\n\r\n    return sum;\r\n}\r\n\r\n/**\r\n * Transforms multi-dimensional array (e.g. GeoJSON Polygon) into the format expected by earcut.\r\n * @example Transforming GeoJSON data.\r\n *     const data = earcut.flatten(geojson.geometry.coordinates);\r\n *     const triangles = earcut(data.vertices, data.holes, data.dimensions);\r\n * @example Transforming simple triangle with hole:\r\n *     const data = earcut.flatten([[[0, 0], [100, 0], [0, 100]], [[10, 10], [0, 10], [10, 0]]]);\r\n *     const triangles = earcut(data.vertices, data.holes, data.dimensions);\r\n * @param data Arrays of rings, with the first being the outline and the rest holes. A ring is an array points, each point being an array of numbers.\r\n */\r\n// turn a polygon in a multi-dimensional array form (e.g. as in GeoJSON) into a form Earcut accepts\r\nexport function flatten(data: ArrayLike<ArrayLike<ArrayLike<number>>>)\r\n{\r\n    const dim = data[0][0].length;\r\n    const result: { vertices: number[], holes: number[], dimensions: number } = { vertices: [], holes: [], dimensions: dim };\r\n    let holeIndex = 0;\r\n\r\n    for (let i = 0; i < data.length; i++)\r\n    {\r\n        for (let j = 0; j < data[i].length; j++)\r\n        {\r\n            for (let d = 0; d < dim; d++) result.vertices.push(data[i][j][d]);\r\n        }\r\n        if (i > 0)\r\n        {\r\n            holeIndex += data[i - 1].length;\r\n            result.holes.push(holeIndex);\r\n        }\r\n    }\r\n\r\n    return result;\r\n}\r\n","import { earcut as earcut1, flatten, deviation } from './earcut';\r\n\r\nexport interface EarcutStatic\r\n{\r\n    /**\r\n     * Triangulate an outline.\r\n     *\r\n     * @param vertices A flat array of vertice coordinates like [x0,y0, x1,y1, x2,y2, ...].\r\n     * @param holes An array of hole indices if any (e.g. [5, 8] for a 12-vertice input would mean one hole with vertices 5–7 and another with 8–11).\r\n     * @param dimensions The number of coordinates per vertice in the input array (2 by default).\r\n     * @return A flat array with each group of three numbers indexing a triangle in the `vertices` array.\r\n     * @example earcut([10,0, 0,50, 60,60, 70,10]); // returns [1,0,3, 3,2,1]\r\n     * @example with a hole: earcut([0,0, 100,0, 100,100, 0,100,  20,20, 80,20, 80,80, 20,80], [4]); // [3,0,4, 5,4,0, 3,4,7, 5,0,1, 2,3,7, 6,5,1, 2,7,6, 6,1,2]\r\n     * @example with 3d coords: earcut([10,0,1, 0,50,2, 60,60,3, 70,10,4], null, 3); // [1,0,3, 3,2,1]\r\n     */\r\n    (vertices: ArrayLike<number>, holes?: ArrayLike<number>, dimensions?: number): number[];\r\n\r\n    /**\r\n     * Transforms multi-dimensional array (e.g. GeoJSON Polygon) into the format expected by earcut.\r\n     * @example Transforming GeoJSON data.\r\n     *     const data = earcut.flatten(geojson.geometry.coordinates);\r\n     *     const triangles = earcut(data.vertices, data.holes, data.dimensions);\r\n     * @example Transforming simple triangle with hole:\r\n     *     const data = earcut.flatten([[[0, 0], [100, 0], [0, 100]], [[10, 10], [0, 10], [10, 0]]]);\r\n     *     const triangles = earcut(data.vertices, data.holes, data.dimensions);\r\n     * @param data Arrays of rings, with the first being the outline and the rest holes. A ring is an array points, each point being an array of numbers.\r\n     */\r\n    flatten(data: ArrayLike<ArrayLike<ArrayLike<number>>>): { vertices: number[], holes: number[], dimensions: number };\r\n\r\n    /**\r\n     * Returns the relative difference between the total area of triangles and the area of the input polygon. 0 means the triangulation is fully correct.\r\n     * @param vertices same as earcut\r\n     * @param holes same as earcut\r\n     * @param dimensions same as earcut\r\n     * @param triangles see return value of earcut\r\n     * @example\r\n     *     const triangles = earcut(vertices, holes, dimensions);\r\n     *  const deviation = earcut.deviation(vertices, holes, dimensions, triangles);\r\n     */\r\n    deviation(vertices: ArrayLike<number>, holes: ArrayLike<number> | undefined, dimensions: number, triangles: ArrayLike<number>): number;\r\n}\r\n\r\nexport const earcut: EarcutStatic = earcut1 as any;\r\nearcut.flatten = flatten;\r\nearcut.deviation = deviation;\r\n"],"names":["earcut","earcut1"],"mappings":";;;;AAWgB,WAAAA,SAAO,UAA6B,OAA2B,YAC/E;AACI,iBAAa,cAAc;AAErB,UAAA,WAAW,SAAS,MAAM;AAChC,UAAM,WAAW,WAAW,MAAM,CAAC,IAAI,aAAa,SAAS;AAC7D,QAAI,YAAY,WAAW,UAAU,GAAG,UAAU,YAAY,IAAI;AAClE,UAAM,YAAsB,CAAA;AAE5B,QAAI,CAAC,aAAa,UAAU,SAAS,UAAU;AAAa,aAAA;AAExD,QAAA;AACA,QAAA;AACA,QAAA;AACA,QAAA;AACA,QAAA;AACA,QAAA;AACA,QAAA;AAEA,QAAA;AAAU,kBAAY,eAAe,UAAU,OAAO,WAAW,UAAU;AAG3E,QAAA,SAAS,SAAS,KAAK,YAC3B;AACW,aAAA,OAAO,SAAS,CAAC;AACjB,aAAA,OAAO,SAAS,CAAC;AAExB,eAAS,IAAI,YAAY,IAAI,UAAU,KAAK,YAC5C;AACI,YAAI,SAAS,CAAC;AACV,YAAA,SAAS,IAAI,CAAC;AAClB,YAAI,IAAI;AAAa,iBAAA;AACrB,YAAI,IAAI;AAAa,iBAAA;AACrB,YAAI,IAAI;AAAa,iBAAA;AACrB,YAAI,IAAI;AAAa,iBAAA;AAAA,MACzB;AAGA,gBAAU,KAAK,IAAI,OAAO,MAAM,OAAO,IAAI;AACjC,gBAAA,YAAY,IAAI,QAAQ,UAAU;AAAA,IAChD;AAEA,iBAAa,WAAW,WAAW,YAAY,MAAM,MAAM,SAAS,CAAC;AAE9D,WAAA;AAAA,EACX;AAGA,WAAS,WAAW,MAAyB,OAAe,KAAa,KAAa,WACtF;AACQ,QAAA;AACA,QAAA;AAEJ,QAAI,cAAe,WAAW,MAAM,OAAO,KAAK,GAAG,IAAI,GACvD;AACI,WAAK,IAAI,OAAO,IAAI,KAAK,KAAK;AAAY,eAAA,WAAW,GAAG,KAAK,CAAC,GAAG,KAAK,IAAI,CAAC,GAAG,IAAI;AAAA,IAAA,OAGtF;AACI,WAAK,IAAI,MAAM,KAAK,KAAK,OAAO,KAAK;AAAY,eAAA,WAAW,GAAG,KAAK,CAAC,GAAG,KAAK,IAAI,CAAC,GAAG,IAAI;AAAA,IAC7F;AAEA,QAAI,QAAQ,OAAO,MAAM,KAAK,IAAI,GAClC;AACI,iBAAW,IAAI;AACf,aAAO,KAAK;AAAA,IAChB;AAEO,WAAA;AAAA,EACX;AAGA,WAAS,aAAa,OAAa,KACnC;AACI,QAAI,CAAC;AAAc,aAAA;AACnB,QAAI,CAAC;AAAW,YAAA;AAEhB,QAAI,IAAI;AACJ,QAAA;AAEJ,OAAA;AACY,cAAA;AAER,UAAI,CAAC,EAAE,YAAY,OAAO,GAAG,EAAE,IAAI,KAAK,KAAK,EAAE,MAAM,GAAG,EAAE,IAAI,MAAM,IACpE;AACI,mBAAW,CAAC;AACZ,YAAI,MAAM,EAAE;AACZ,YAAI,MAAM,EAAE;AAAM;AACV,gBAAA;AAAA,MAAA,OAGZ;AACI,YAAI,EAAE;AAAA,MACV;AAAA,IAAA,SACK,SAAS,MAAM;AAEjB,WAAA;AAAA,EACX;AAGA,WAAS,aAAa,KAAW,WAAqB,KAAa,MAAc,MAAc,SAAiB,MAChH;AACI,QAAI,CAAC;AAAK;AAGV,QAAI,CAAC,QAAQ;AAAoB,iBAAA,KAAK,MAAM,MAAM,OAAO;AAEzD,QAAI,OAAO;AACP,QAAA;AACA,QAAA;AAGG,WAAA,IAAI,SAAS,IAAI,MACxB;AACI,aAAO,IAAI;AACX,aAAO,IAAI;AAEP,UAAA,UAAU,YAAY,KAAK,MAAM,MAAM,OAAO,IAAI,MAAM,GAAG,GAC/D;AAEI,kBAAU,KAAK,KAAK,IAAI,MAAM,CAAC;AAC/B,kBAAU,KAAK,IAAI,IAAI,MAAM,CAAC;AAC9B,kBAAU,KAAK,KAAK,IAAI,MAAM,CAAC;AAE/B,mBAAW,GAAG;AAGd,cAAM,KAAK;AACX,eAAO,KAAK;AAEZ;AAAA,MACJ;AAEM,YAAA;AAGN,UAAI,QAAQ,MACZ;AAEI,YAAI,CAAC,MACL;AACiB,uBAAA,aAAa,GAAG,GAAG,WAAW,KAAK,MAAM,MAAM,SAAS,CAAC;AAAA,QAAA,WAIjE,SAAS,GAClB;AACI,gBAAM,uBAAuB,aAAa,GAAG,GAAG,WAAW,GAAG;AAC9D,uBAAa,KAAK,WAAW,KAAK,MAAM,MAAM,SAAS,CAAC;AAAA,QAAA,WAInD,SAAS,GAClB;AACI,sBAAY,KAAK,WAAW,KAAK,MAAM,MAAM,OAAO;AAAA,QACxD;AAEA;AAAA,MACJ;AAAA,IACJ;AAAA,EACJ;AAGA,WAAS,MAAM,KACf;AACI,UAAM,IAAI,IAAI;AACd,UAAM,IAAI;AACV,UAAM,IAAI,IAAI;AAEd,QAAI,KAAK,GAAG,GAAG,CAAC,KAAK;AAAU,aAAA;AAG/B,UAAM,KAAK,EAAE;AAAG,UAAM,KAAK,EAAE;AAAG,UAAM,KAAK,EAAE;AAAG,UAAM,KAAK,EAAE;AAAG,UAAM,KAAK,EAAE;AAAG,UAC5E,KAAK,EAAE;AAGL,UAAA,KAAK,KAAK,KAAM,KAAK,KAAK,KAAK,KAAO,KAAK,KAAK,KAAK;AACrD,UAAA,KAAK,KAAK,KAAM,KAAK,KAAK,KAAK,KAAO,KAAK,KAAK,KAAK;AACrD,UAAA,KAAK,KAAK,KAAM,KAAK,KAAK,KAAK,KAAO,KAAK,KAAK,KAAK;AACrD,UAAA,KAAK,KAAK,KAAM,KAAK,KAAK,KAAK,KAAO,KAAK,KAAK,KAAK;AAE3D,QAAI,IAAI,EAAE;AACV,WAAO,MAAM,GACb;AACI,UAAI,EAAE,KAAK,MAAM,EAAE,KAAK,MAAM,EAAE,KAAK,MAAM,EAAE,KAAK,MAC3C,gBAAgB,IAAI,IAAI,IAAI,IAAI,IAAI,IAAI,EAAE,GAAG,EAAE,CAAC,KAChD,KAAK,EAAE,MAAM,GAAG,EAAE,IAAI,KAAK;AAAU,eAAA;AAC5C,UAAI,EAAE;AAAA,IACV;AAEO,WAAA;AAAA,EACX;AAEA,WAAS,YAAY,KAAW,MAAc,MAAc,SAC5D;AACI,UAAM,IAAI,IAAI;AACd,UAAM,IAAI;AACV,UAAM,IAAI,IAAI;AAEd,QAAI,KAAK,GAAG,GAAG,CAAC,KAAK;AAAU,aAAA;AAE/B,UAAM,KAAK,EAAE;AACb,UAAM,KAAK,EAAE;AACb,UAAM,KAAK,EAAE;AACb,UAAM,KAAK,EAAE;AACb,UAAM,KAAK,EAAE;AACb,UAAM,KAAK,EAAE;AAGP,UAAA,KAAK,KAAK,KAAM,KAAK,KAAK,KAAK,KAAO,KAAK,KAAK,KAAK;AACrD,UAAA,KAAK,KAAK,KAAM,KAAK,KAAK,KAAK,KAAO,KAAK,KAAK,KAAK;AACrD,UAAA,KAAK,KAAK,KAAM,KAAK,KAAK,KAAK,KAAO,KAAK,KAAK,KAAK;AACrD,UAAA,KAAK,KAAK,KAAM,KAAK,KAAK,KAAK,KAAO,KAAK,KAAK,KAAK;AAG3D,UAAM,OAAO,OAAO,IAAI,IAAI,MAAM,MAAM,OAAO;AAC/C,UAAM,OAAO,OAAO,IAAI,IAAI,MAAM,MAAM,OAAO;AAE/C,QAAI,IAAI,IAAI;AACZ,QAAI,IAAI,IAAI;AAGZ,WAAO,KAAK,EAAE,KAAK,QAAQ,KAAK,EAAE,KAAK,MACvC;AACI,UAAI,EAAE,KAAK,MAAM,EAAE,KAAK,MAAM,EAAE,KAAK,MAAM,EAAE,KAAK,MAAM,MAAM,KAAK,MAAM,KAClE,gBAAgB,IAAI,IAAI,IAAI,IAAI,IAAI,IAAI,EAAE,GAAG,EAAE,CAAC,KAAK,KAAK,EAAE,MAAM,GAAG,EAAE,IAAI,KAAK;AAAU,eAAA;AACjG,UAAI,EAAE;AAEN,UAAI,EAAE,KAAK,MAAM,EAAE,KAAK,MAAM,EAAE,KAAK,MAAM,EAAE,KAAK,MAAM,MAAM,KAAK,MAAM,KAClE,gBAAgB,IAAI,IAAI,IAAI,IAAI,IAAI,IAAI,EAAE,GAAG,EAAE,CAAC,KAAK,KAAK,EAAE,MAAM,GAAG,EAAE,IAAI,KAAK;AAAU,eAAA;AACjG,UAAI,EAAE;AAAA,IACV;AAGO,WAAA,KAAK,EAAE,KAAK,MACnB;AACI,UAAI,EAAE,KAAK,MAAM,EAAE,KAAK,MAAM,EAAE,KAAK,MAAM,EAAE,KAAK,MAAM,MAAM,KAAK,MAAM,KAClE,gBAAgB,IAAI,IAAI,IAAI,IAAI,IAAI,IAAI,EAAE,GAAG,EAAE,CAAC,KAAK,KAAK,EAAE,MAAM,GAAG,EAAE,IAAI,KAAK;AAAU,eAAA;AACjG,UAAI,EAAE;AAAA,IACV;AAGO,WAAA,KAAK,EAAE,KAAK,MACnB;AACI,UAAI,EAAE,KAAK,MAAM,EAAE,KAAK,MAAM,EAAE,KAAK,MAAM,EAAE,KAAK,MAAM,MAAM,KAAK,MAAM,KAClE,gBAAgB,IAAI,IAAI,IAAI,IAAI,IAAI,IAAI,EAAE,GAAG,EAAE,CAAC,KAAK,KAAK,EAAE,MAAM,GAAG,EAAE,IAAI,KAAK;AAAU,eAAA;AACjG,UAAI,EAAE;AAAA,IACV;AAEO,WAAA;AAAA,EACX;AAGA,WAAS,uBAAuB,OAAa,WAAqB,KAClE;AACI,QAAI,IAAI;AAER,OAAA;AACI,YAAM,IAAI,EAAE;AACN,YAAA,IAAI,EAAE,KAAK;AAEjB,UAAI,CAAC,OAAO,GAAG,CAAC,KAAK,WAAW,GAAG,GAAG,EAAE,MAAM,CAAC,KAAK,cAAc,GAAG,CAAC,KAAK,cAAc,GAAG,CAAC,GAC7F;AACI,kBAAU,KAAK,EAAE,IAAI,MAAM,CAAC;AAC5B,kBAAU,KAAK,EAAE,IAAI,MAAM,CAAC;AAC5B,kBAAU,KAAK,EAAE,IAAI,MAAM,CAAC;AAG5B,mBAAW,CAAC;AACZ,mBAAW,EAAE,IAAI;AAEjB,YAAI,QAAQ;AAAA,MAChB;AACA,UAAI,EAAE;AAAA,IAAA,SACD,MAAM;AAEf,WAAO,aAAa,CAAC;AAAA,EACzB;AAGA,WAAS,YAAY,OAAa,WAAqB,KAAa,MAAc,MAAc,SAChG;AAEI,QAAI,IAAI;AAER,OAAA;AACQ,UAAA,IAAI,EAAE,KAAK;AACR,aAAA,MAAM,EAAE,MACf;AACI,YAAI,EAAE,MAAM,EAAE,KAAK,gBAAgB,GAAG,CAAC,GACvC;AAEQ,cAAA,IAAI,aAAa,GAAG,CAAC;AAGrB,cAAA,aAAa,GAAG,EAAE,IAAI;AACtB,cAAA,aAAa,GAAG,EAAE,IAAI;AAG1B,uBAAa,GAAG,WAAW,KAAK,MAAM,MAAM,SAAS,CAAC;AACtD,uBAAa,GAAG,WAAW,KAAK,MAAM,MAAM,SAAS,CAAC;AAEtD;AAAA,QACJ;AACA,YAAI,EAAE;AAAA,MACV;AACA,UAAI,EAAE;AAAA,IAAA,SACD,MAAM;AAAA,EACnB;AAGA,WAAS,eAAe,MAAyB,aAAgC,WAAiB,KAClG;AACI,UAAM,QAAgB,CAAA;AAClB,QAAA;AACA,QAAA;AACA,QAAA;AACA,QAAA;AACA,QAAA;AAEJ,SAAK,IAAI,GAAG,MAAM,YAAY,QAAQ,IAAI,KAAK,KAC/C;AACY,cAAA,YAAY,CAAC,IAAI;AACnB,YAAA,IAAI,MAAM,IAAI,YAAY,IAAI,CAAC,IAAI,MAAM,KAAK;AACpD,aAAO,WAAW,MAAM,OAAO,KAAK,KAAK,KAAK;AAC9C,UAAI,SAAS,KAAK;AAAM,aAAK,UAAU;AACjC,YAAA,KAAK,YAAY,IAAI,CAAC;AAAA,IAChC;AAEA,UAAM,KAAK,QAAQ;AAGnB,SAAK,IAAI,GAAG,IAAI,MAAM,QAAQ,KAC9B;AACI,kBAAY,cAAc,MAAM,CAAC,GAAG,SAAS;AAAA,IACjD;AAEO,WAAA;AAAA,EACX;AAEA,WAAS,SAAS,GAAmB,GACrC;AACW,WAAA,EAAE,IAAI,EAAE;AAAA,EACnB;AAGA,WAAS,cAAc,MAAY,WACnC;AACU,UAAA,SAAS,eAAe,MAAM,SAAS;AAC7C,QAAI,CAAC,QACL;AACW,aAAA;AAAA,IACX;AAEM,UAAA,gBAAgB,aAAa,QAAQ,IAAI;AAGlC,iBAAA,eAAe,cAAc,IAAI;AAEvC,WAAA,aAAa,QAAQ,OAAO,IAAI;AAAA,EAC3C;AAGA,WAAS,eAAe,MAAY,WACpC;AACI,QAAI,IAAI;AACR,UAAM,KAAK,KAAK;AAChB,UAAM,KAAK,KAAK;AAChB,QAAI,KAAK;AACL,QAAA;AAKJ,OAAA;AACQ,UAAA,MAAM,EAAE,KAAK,MAAM,EAAE,KAAK,KAAK,EAAE,KAAK,MAAM,EAAE,GAClD;AACI,cAAM,IAAI,EAAE,KAAK,KAAK,EAAE,MAAM,EAAE,KAAK,IAAI,EAAE,MAAM,EAAE,KAAK,IAAI,EAAE;AAC1D,YAAA,KAAK,MAAM,IAAI,IACnB;AACS,eAAA;AACL,cAAI,EAAE,IAAI,EAAE,KAAK,IAAI,IAAI,EAAE;AAC3B,cAAI,MAAM;AAAW,mBAAA;AAAA,QACzB;AAAA,MACJ;AACA,UAAI,EAAE;AAAA,IAAA,SACD,MAAM;AAEf,QAAI,CAAC;AAAU,aAAA;AAMf,UAAM,OAAO;AACb,UAAM,KAAK,EAAE;AACb,UAAM,KAAK,EAAE;AACb,QAAI,SAAS;AACT,QAAA;AAEA,QAAA;AAGJ,OAAA;AACQ,UAAA,MAAM,EAAE,KAAK,EAAE,KAAK,MAAM,OAAO,EAAE,KAChC,gBAAgB,KAAK,KAAK,KAAK,IAAI,IAAI,IAAI,IAAI,KAAK,KAAK,KAAK,IAAI,IAAI,EAAE,GAAG,EAAE,CAAC,GACrF;AACI,cAAM,KAAK,IAAI,KAAK,EAAE,CAAC,KAAK,KAAK,EAAE;AAEnC,YAAI,cAAc,GAAG,IAAI,MACjB,MAAM,UAAW,QAAQ,WAAW,EAAE,IAAI,EAAE,KAAM,EAAE,MAAM,EAAE,KAAK,qBAAqB,GAAG,CAAC,KAClG;AACQ,cAAA;AACK,mBAAA;AAAA,QACb;AAAA,MACJ;AAEA,UAAI,EAAE;AAAA,IAAA,SACD,MAAM;AAER,WAAA;AAAA,EACX;AAGA,WAAS,qBAAqB,GAAS,GACvC;AACI,WAAO,KAAK,EAAE,MAAM,GAAG,EAAE,IAAI,IAAI,KAAK,KAAK,EAAE,MAAM,GAAG,EAAE,IAAI,IAAI;AAAA,EACpE;AAGA,WAAS,WAAW,OAAa,MAAc,MAAc,SAC7D;AACI,QAAI,IAAI;AAER,OAAA;AACI,UAAI,EAAE,MAAM;AAAK,UAAA,IAAI,OAAO,EAAE,GAAG,EAAE,GAAG,MAAM,MAAM,OAAO;AACzD,QAAE,QAAQ,EAAE;AACZ,QAAE,QAAQ,EAAE;AACZ,UAAI,EAAE;AAAA,IAAA,SACD,MAAM;AAEf,MAAE,MAAM,QAAQ;AAChB,MAAE,QAAQ;AAEV,eAAW,CAAC;AAAA,EAChB;AAIA,WAAS,WAAW,MACpB;AACQ,QAAA;AACA,QAAA;AACA,QAAA;AACA,QAAA;AACA,QAAA;AACA,QAAA;AACA,QAAA;AACA,QAAA;AACJ,QAAI,SAAS;AAGb,OAAA;AACQ,UAAA;AACG,aAAA;AACA,aAAA;AACK,kBAAA;AAEZ,aAAO,GACP;AACI;AACI,YAAA;AACI,gBAAA;AACR,aAAK,IAAI,GAAG,IAAI,QAAQ,KACxB;AACI;AACA,cAAI,EAAE;AACN,cAAI,CAAC;AAAG;AAAA,QACZ;AACQ,gBAAA;AAER,eAAO,QAAQ,KAAM,QAAQ,KAAK,GAClC;AACQ,cAAA,UAAU,MAAM,UAAU,KAAK,CAAC,KAAK,EAAE,KAAK,EAAE,IAClD;AACQ,gBAAA;AACJ,gBAAI,EAAE;AACN;AAAA,UAAA,OAGJ;AACQ,gBAAA;AACJ,gBAAI,EAAE;AACN;AAAA,UACJ;AAEI,cAAA;AAAM,iBAAK,QAAQ;AAAA;AACX,mBAAA;AAEZ,YAAE,QAAQ;AACH,iBAAA;AAAA,QACX;AAEI,YAAA;AAAA,MACR;AAEA,WAAK,QAAQ;AACH,gBAAA;AAAA,IAAA,SACL,YAAY;AAEd,WAAA;AAAA,EACX;AAGA,WAAS,OAAO,GAAW,GAAW,MAAc,MAAc,SAClE;AAES,SAAA,IAAI,QAAQ,UAAU;AACtB,SAAA,IAAI,QAAQ,UAAU;AAEtB,SAAA,IAAK,KAAK,KAAM;AAChB,SAAA,IAAK,KAAK,KAAM;AAChB,SAAA,IAAK,KAAK,KAAM;AAChB,SAAA,IAAK,KAAK,KAAM;AAEhB,SAAA,IAAK,KAAK,KAAM;AAChB,SAAA,IAAK,KAAK,KAAM;AAChB,SAAA,IAAK,KAAK,KAAM;AAChB,SAAA,IAAK,KAAK,KAAM;AAErB,WAAO,IAAK,KAAK;AAAA,EACrB;AAGA,WAAS,YAAY,OACrB;AACI,QAAI,IAAI;AACR,QAAI,WAAW;AAEf,OAAA;AACQ,UAAA,EAAE,IAAI,SAAS,KAAM,EAAE,MAAM,SAAS,KAAK,EAAE,IAAI,SAAS;AAAe,mBAAA;AAC7E,UAAI,EAAE;AAAA,IAAA,SACD,MAAM;AAER,WAAA;AAAA,EACX;AAGA,WAAS,gBAAgB,IAAY,IAAY,IAAY,IAAY,IAAY,IAAY,IAAY,IAC7G;AACY,YAAA,KAAK,OAAO,KAAK,QAAQ,KAAK,OAAO,KAAK,QAC1C,KAAK,OAAO,KAAK,QAAQ,KAAK,OAAO,KAAK,QAC1C,KAAK,OAAO,KAAK,QAAQ,KAAK,OAAO,KAAK;AAAA,EACtD;AAGA,WAAS,gBAAgB,GAAS,GAClC;AACW,WAAA,EAAE,KAAK,MAAM,EAAE,KAAK,EAAE,KAAK,MAAM,EAAE,KAAK,CAAC,kBAAkB,GAAG,CAAC,MAC9D,cAAc,GAAG,CAAC,KAAK,cAAc,GAAG,CAAC,KAAK,aAAa,GAAG,CAAC,MAC3D,KAAK,EAAE,MAAM,GAAG,EAAE,IAAI,KAAK,KAAK,GAAG,EAAE,MAAM,CAAC,MAC7C,OAAO,GAAG,CAAC,KAAK,KAAK,EAAE,MAAM,GAAG,EAAE,IAAI,IAAI,KAAK,KAAK,EAAE,MAAM,GAAG,EAAE,IAAI,IAAI;AAAA,EACxF;AAGA,WAAS,KAAK,GAA8B,GAA8B,GAC1E;AACI,YAAQ,EAAE,IAAI,EAAE,MAAM,EAAE,IAAI,EAAE,MAAM,EAAE,IAAI,EAAE,MAAM,EAAE,IAAI,EAAE;AAAA,EAC9D;AAGA,WAAS,OAAO,IAA+B,IAC/C;AACI,WAAO,GAAG,MAAM,GAAG,KAAK,GAAG,MAAM,GAAG;AAAA,EACxC;AAGA,WAAS,WAAW,IAA8B,IAA8B,IAA8B,IAC9G;AACI,UAAM,KAAK,KAAK,KAAK,IAAI,IAAI,EAAE,CAAC;AAChC,UAAM,KAAK,KAAK,KAAK,IAAI,IAAI,EAAE,CAAC;AAChC,UAAM,KAAK,KAAK,KAAK,IAAI,IAAI,EAAE,CAAC;AAChC,UAAM,KAAK,KAAK,KAAK,IAAI,IAAI,EAAE,CAAC;AAE5B,QAAA,OAAO,MAAM,OAAO;AAAW,aAAA;AAEnC,QAAI,OAAO,KAAK,UAAU,IAAI,IAAI,EAAE;AAAU,aAAA;AAC9C,QAAI,OAAO,KAAK,UAAU,IAAI,IAAI,EAAE;AAAU,aAAA;AAC9C,QAAI,OAAO,KAAK,UAAU,IAAI,IAAI,EAAE;AAAU,aAAA;AAC9C,QAAI,OAAO,KAAK,UAAU,IAAI,IAAI,EAAE;AAAU,aAAA;AAEvC,WAAA;AAAA,EACX;AAGA,WAAS,UAAU,GAA8B,GAA8B,GAC/E;AACI,WAAO,EAAE,KAAK,KAAK,IAAI,EAAE,GAAG,EAAE,CAAC,KAAK,EAAE,KAAK,KAAK,IAAI,EAAE,GAAG,EAAE,CAAC,KAAK,EAAE,KAAK,KAAK,IAAI,EAAE,GAAG,EAAE,CAAC,KAAK,EAAE,KAAK,KAAK,IAAI,EAAE,GAAG,EAAE,CAAC;AAAA,EAC1H;AAEA,WAAS,KAAK,KACd;AACI,WAAO,MAAM,IAAI,IAAI,MAAM,IAAI,KAAK;AAAA,EACxC;AAGA,WAAS,kBAAkB,GAAS,GACpC;AACI,QAAI,IAAI;AAER,OAAA;AACQ,UAAA,EAAE,MAAM,EAAE,KAAK,EAAE,KAAK,MAAM,EAAE,KAAK,EAAE,MAAM,EAAE,KAAK,EAAE,KAAK,MAAM,EAAE,KAC9D,WAAW,GAAG,EAAE,MAAM,GAAG,CAAC;AAAU,eAAA;AAC3C,UAAI,EAAE;AAAA,IAAA,SACD,MAAM;AAER,WAAA;AAAA,EACX;AAGA,WAAS,cAAc,GAAS,GAChC;AACI,WAAO,KAAK,EAAE,MAAM,GAAG,EAAE,IAAI,IAAI,IAC3B,KAAK,GAAG,GAAG,EAAE,IAAI,KAAK,KAAK,KAAK,GAAG,EAAE,MAAM,CAAC,KAAK,IACjD,KAAK,GAAG,GAAG,EAAE,IAAI,IAAI,KAAK,KAAK,GAAG,EAAE,MAAM,CAAC,IAAI;AAAA,EACzD;AAGA,WAAS,aAAa,GAAS,GAC/B;AACI,QAAI,IAAI;AACR,QAAI,SAAS;AACb,UAAM,MAAM,EAAE,IAAI,EAAE,KAAK;AACzB,UAAM,MAAM,EAAE,IAAI,EAAE,KAAK;AAEzB,OAAA;AACU,UAAA,EAAE,IAAI,OAAS,EAAE,KAAK,IAAI,MAAQ,EAAE,KAAK,MAAM,EAAE,KAC/C,MAAM,EAAE,KAAK,IAAI,EAAE,MAAM,KAAK,EAAE,MAAM,EAAE,KAAK,IAAI,EAAE,KAAK,EAAE,GAClE;AAAE,iBAAS,CAAC;AAAA,MAAQ;AACpB,UAAI,EAAE;AAAA,IAAA,SACD,MAAM;AAER,WAAA;AAAA,EACX;AAIA,WAAS,aAAa,GAAS,GAC/B;AACU,UAAA,KAAK,IAAI,KAAK,EAAE,GAAG,EAAE,GAAG,EAAE,CAAC;AAC3B,UAAA,KAAK,IAAI,KAAK,EAAE,GAAG,EAAE,GAAG,EAAE,CAAC;AACjC,UAAM,KAAK,EAAE;AACb,UAAM,KAAK,EAAE;AAEb,MAAE,OAAO;AACT,MAAE,OAAO;AAET,OAAG,OAAO;AACV,OAAG,OAAO;AAEV,OAAG,OAAO;AACV,OAAG,OAAO;AAEV,OAAG,OAAO;AACV,OAAG,OAAO;AAEH,WAAA;AAAA,EACX;AAGA,WAAS,WAAW,GAAW,GAAW,GAAW,MACrD;AACI,UAAM,IAAI,IAAI,KAAK,GAAG,GAAG,CAAC;AAE1B,QAAI,CAAC,MACL;AACI,QAAE,OAAO;AACT,QAAE,OAAO;AAAA,IAAA,OAGb;AACI,QAAE,OAAO,KAAK;AACd,QAAE,OAAO;AACT,WAAK,KAAK,OAAO;AACjB,WAAK,OAAO;AAAA,IAChB;AAEO,WAAA;AAAA,EACX;AAEA,WAAS,WAAW,GACpB;AACM,MAAA,KAAK,OAAO,EAAE;AACd,MAAA,KAAK,OAAO,EAAE;AAEhB,QAAI,EAAE;AAAS,QAAA,MAAM,QAAQ,EAAE;AAC/B,QAAI,EAAE;AAAS,QAAA,MAAM,QAAQ,EAAE;AAAA,EACnC;AAEA,QAAM,KACN;AAAA,IAWI,YAAY,GAAW,GAAW,GAClC;AAEI,WAAK,IAAI;AAGT,WAAK,IAAI;AACT,WAAK,IAAI;AAGT,WAAK,OAAO;AACZ,WAAK,OAAO;AAGZ,WAAK,IAAI;AAGT,WAAK,QAAQ;AACb,WAAK,QAAQ;AAGb,WAAK,UAAU;AAAA,IACnB;AAAA,EACJ;AAcO,WAAS,UAAU,UAA6B,OAA0B,YAAoB,WACrG;AACU,UAAA,WAAW,SAAS,MAAM;AAChC,UAAM,WAAW,WAAW,MAAM,CAAC,IAAI,aAAa,SAAS;AAEzD,QAAA,cAAc,KAAK,IAAI,WAAW,UAAU,GAAG,UAAU,UAAU,CAAC;AACxE,QAAI,UACJ;AACI,eAAS,IAAI,GAAG,MAAM,MAAM,QAAQ,IAAI,KAAK,KAC7C;AACU,cAAA,QAAQ,MAAM,CAAC,IAAI;AACnB,cAAA,MAAM,IAAI,MAAM,IAAI,MAAM,IAAI,CAAC,IAAI,aAAa,SAAS;AAC/D,uBAAe,KAAK,IAAI,WAAW,UAAU,OAAO,KAAK,UAAU,CAAC;AAAA,MACxE;AAAA,IACJ;AAEA,QAAI,gBAAgB;AACpB,aAAS,IAAI,GAAG,IAAI,UAAU,QAAQ,KAAK,GAC3C;AACU,YAAA,IAAI,UAAU,CAAC,IAAI;AACzB,YAAM,IAAI,UAAU,IAAI,CAAC,IAAI;AAC7B,YAAM,IAAI,UAAU,IAAI,CAAC,IAAI;AAC7B,uBAAiB,KAAK;AAAA,SACjB,SAAS,CAAC,IAAI,SAAS,CAAC,MAAM,SAAS,IAAI,CAAC,IAAI,SAAS,IAAI,CAAC,MAC5D,SAAS,CAAC,IAAI,SAAS,CAAC,MAAM,SAAS,IAAI,CAAC,IAAI,SAAS,IAAI,CAAC;AAAA,MAAA;AAAA,IACzE;AAEO,WAAA,gBAAgB,KAAK,kBAAkB,IAAI,IAC5C,KAAK,KAAK,gBAAgB,eAAe,WAAW;AAAA,EAC9D;AAEA,WAAS,WAAW,MAAyB,OAAe,KAAa,KACzE;AACI,QAAI,MAAM;AACD,aAAA,IAAI,OAAO,IAAI,MAAM,KAAK,IAAI,KAAK,KAAK,KACjD;AACI,cAAQ,KAAK,CAAC,IAAI,KAAK,CAAC,MAAM,KAAK,IAAI,CAAC,IAAI,KAAK,IAAI,CAAC;AAClD,UAAA;AAAA,IACR;AAEO,WAAA;AAAA,EACX;AAaO,WAAS,QAAQ,MACxB;AACI,UAAM,MAAM,KAAK,CAAC,EAAE,CAAC,EAAE;AACjB,UAAA,SAAsE,EAAE,UAAU,IAAI,OAAO,IAAI,YAAY;AACnH,QAAI,YAAY;AAEhB,aAAS,IAAI,GAAG,IAAI,KAAK,QAAQ,KACjC;AACI,eAAS,IAAI,GAAG,IAAI,KAAK,CAAC,EAAE,QAAQ,KACpC;AACa,iBAAA,IAAI,GAAG,IAAI,KAAK;AAAY,iBAAA,SAAS,KAAK,KAAK,CAAC,EAAE,CAAC,EAAE,CAAC,CAAC;AAAA,MACpE;AACA,UAAI,IAAI,GACR;AACiB,qBAAA,KAAK,IAAI,CAAC,EAAE;AAClB,eAAA,MAAM,KAAK,SAAS;AAAA,MAC/B;AAAA,IACJ;AAEO,WAAA;AAAA,EACX;ACvxBa,QAAA,SAAuBC;AACpC,SAAO,UAAU;AACjB,SAAO,YAAY;;;;"}