{"version":3,"sources":["jsdelivr-header.js","/npm/concaveman@2.0.0/index.js"],"names":[],"mappings":"AAAA;AACA;AACA;AACA;AACA;AACA;AACA,OCLO,UAAW,eACX,UAAW,mBACX,mBAAoB,0BACnB,aAAe,mCAER,SAAS,WAAW,EAAQ,EAAW,GAElD,EAAY,KAAK,IAAI,OAAiB,IAAd,EAA0B,EAAI,GAGtD,EAAkB,GAAmB,EAGrC,MAAM,EAAO,eAAe,GAGtB,EAAO,IAAI,MAAM,IACvB,EAAK,OAAS,SAAU,GACpB,MAAO,CACH,KAAM,EAAE,GACR,KAAM,EAAE,GACR,KAAM,EAAE,GACR,KAAM,EAAE,GAEhB,EACA,EAAK,YAAc,SAAU,EAAG,GAAK,OAAO,EAAE,GAAK,EAAE,EAAI,EACzD,EAAK,YAAc,SAAU,EAAG,GAAK,OAAO,EAAE,GAAK,EAAE,EAAI,EAEzD,EAAK,KAAK,GAGV,MAAM,EAAQ,GACd,IAAI,EACJ,IAAK,IAAI,EAAI,EAAG,EAAI,EAAK,OAAQ,IAAK,CAClC,MAAM,EAAI,EAAK,GACf,EAAK,OAAO,GACZ,EAAO,WAAW,EAAG,GACrB,EAAM,KAAK,EACf,CAGA,MAAM,EAAU,IAAI,MAAM,IAC1B,IAAK,IAAI,EAAI,EAAG,EAAI,EAAM,OAAQ,IAAK,EAAQ,OAAO,WAAW,EAAM,KAEvE,MAAM,EAAc,EAAY,EAC1B,EAAiB,EAAkB,EAGzC,KAAO,EAAM,QAAQ,CACjB,MAAM,EAAO,EAAM,QACb,EAAI,EAAK,EACT,EAAI,EAAK,KAAK,EAGd,EAAQ,UAAU,EAAG,GAC3B,GAAI,EAAQ,EAAgB,SAE5B,MAAM,EAAW,EAAQ,EAGnB,EAAI,cAAc,EAAM,EAAK,KAAK,EAAG,EAAG,EAAG,EAAK,KAAK,KAAK,EAAG,EAAU,GAGzE,GAAK,KAAK,IAAI,UAAU,EAAG,GAAI,UAAU,EAAG,KAAO,IAEnD,EAAM,KAAK,GACX,EAAM,KAAK,WAAW,EAAG,IAGzB,EAAK,OAAO,GACZ,EAAQ,OAAO,GACf,EAAQ,OAAO,WAAW,IAC1B,EAAQ,OAAO,WAAW,EAAK,OAEvC,CAGA,IAAI,EAAO,EACX,MAAM,EAAU,GAChB,GACI,EAAQ,KAAK,EAAK,GAClB,EAAO,EAAK,WACP,IAAS,GAIlB,OAFA,EAAQ,KAAK,EAAK,GAEX,CACX,CAEA,SAAS,cAAc,EAAM,EAAG,EAAG,EAAG,EAAG,EAAS,GAC9C,MAAM,EAAQ,IAAI,MAAM,GAAI,aAC5B,IAAI,EAAO,EAAK,KAIhB,KAAO,GAAM,CACT,IAAK,IAAI,EAAI,EAAG,EAAI,EAAK,SAAS,OAAQ,IAAK,CAC3C,MAAM,EAAQ,EAAK,SAAS,GAEtB,EAAO,EAAK,KAAO,UAAU,EAAO,EAAG,GAAK,aAAa,EAAG,EAAG,GACjE,EAAO,GAEX,EAAM,KAAK,CACP,KAAM,EACN,QAER,CAEA,KAAO,EAAM,SAAW,EAAM,OAAO,KAAK,UAAU,CAChD,MAAM,EAAO,EAAM,MACb,EAAI,EAAK,KAIT,EAAK,UAAU,EAAG,EAAG,GACrB,EAAK,UAAU,EAAG,EAAG,GAC3B,GAAI,EAAK,KAAO,GAAM,EAAK,KAAO,GAC9B,gBAAgB,EAAG,EAAG,IACtB,gBAAgB,EAAG,EAAG,GAAU,OAAO,CAC/C,CAEA,EAAO,EAAM,MACT,IAAM,EAAO,EAAK,KAC1B,CAEA,OAAO,IACX,CAEA,SAAS,YAAY,EAAG,GACpB,OAAO,EAAE,KAAO,EAAE,IACtB,CAGA,SAAS,aAAa,EAAG,EAAG,GACxB,GAAI,OAAO,EAAG,IAAS,OAAO,EAAG,GAAO,OAAO,EAC/C,MAAM,EAAK,aAAa,EAAE,GAAI,EAAE,GAAI,EAAE,GAAI,EAAE,GAAI,EAAK,KAAM,EAAK,KAAM,EAAK,KAAM,EAAK,MACtF,GAAW,IAAP,EAAU,OAAO,EACrB,MAAM,EAAK,aAAa,EAAE,GAAI,EAAE,GAAI,EAAE,GAAI,EAAE,GAAI,EAAK,KAAM,EAAK,KAAM,EAAK,KAAM,EAAK,MACtF,GAAW,IAAP,EAAU,OAAO,EACrB,MAAM,EAAK,aAAa,EAAE,GAAI,EAAE,GAAI,EAAE,GAAI,EAAE,GAAI,EAAK,KAAM,EAAK,KAAM,EAAK,KAAM,EAAK,MACtF,GAAW,IAAP,EAAU,OAAO,EACrB,MAAM,EAAK,aAAa,EAAE,GAAI,EAAE,GAAI,EAAE,GAAI,EAAE,GAAI,EAAK,KAAM,EAAK,KAAM,EAAK,KAAM,EAAK,MACtF,OAAW,IAAP,EAAiB,EACd,KAAK,IAAI,EAAI,EAAI,EAAI,EAChC,CAEA,SAAS,OAAO,EAAG,GACf,OAAO,EAAE,IAAM,EAAK,MACb,EAAE,IAAM,EAAK,MACb,EAAE,IAAM,EAAK,MACb,EAAE,IAAM,EAAK,IACxB,CAGA,SAAS,gBAAgB,EAAG,EAAG,GAC3B,MAAM,EAAO,KAAK,IAAI,EAAE,GAAI,EAAE,IACxB,EAAO,KAAK,IAAI,EAAE,GAAI,EAAE,IACxB,EAAO,KAAK,IAAI,EAAE,GAAI,EAAE,IACxB,EAAO,KAAK,IAAI,EAAE,GAAI,EAAE,IAExB,EAAQ,EAAQ,OAAO,CAAC,OAAM,OAAM,OAAM,SAChD,IAAK,IAAI,EAAI,EAAG,EAAI,EAAM,OAAQ,IAC9B,GAAI,WAAW,EAAM,GAAG,EAAG,EAAM,GAAG,KAAK,EAAG,EAAG,GAAI,OAAO,EAE9D,OAAO,CACX,CAEA,SAAS,MAAM,EAAI,EAAI,GACnB,OAAO,SAAS,EAAG,GAAI,EAAG,GAAI,EAAG,GAAI,EAAG,GAAI,EAAG,GAAI,EAAG,GAC1D,CAGA,SAAS,WAAW,EAAI,EAAI,EAAI,GAC5B,OAAO,IAAO,GAAM,IAAO,GACvB,MAAM,EAAI,EAAI,GAAM,GAAM,MAAM,EAAI,EAAI,GAAM,GAC9C,MAAM,EAAI,EAAI,GAAM,GAAM,MAAM,EAAI,EAAI,GAAM,CACtD,CAGA,SAAS,WAAW,GAChB,MAAM,EAAK,EAAK,EACV,EAAK,EAAK,KAAK,EAKrB,OAJA,EAAK,KAAO,KAAK,IAAI,EAAG,GAAI,EAAG,IAC/B,EAAK,KAAO,KAAK,IAAI,EAAG,GAAI,EAAG,IAC/B,EAAK,KAAO,KAAK,IAAI,EAAG,GAAI,EAAG,IAC/B,EAAK,KAAO,KAAK,IAAI,EAAG,GAAI,EAAG,IACxB,CACX,CAGA,SAAS,eAAe,GACpB,IAAI,EAAO,EAAO,GACd,EAAM,EAAO,GACb,EAAQ,EAAO,GACf,EAAS,EAAO,GAGpB,IAAK,IAAI,EAAI,EAAG,EAAI,EAAO,OAAQ,IAAK,CACpC,MAAM,EAAI,EAAO,GACb,EAAE,GAAK,EAAK,KAAI,EAAO,GACvB,EAAE,GAAK,EAAM,KAAI,EAAQ,GACzB,EAAE,GAAK,EAAI,KAAI,EAAM,GACrB,EAAE,GAAK,EAAO,KAAI,EAAS,EACnC,CAGA,MAAM,EAAO,CAAC,EAAM,EAAK,EAAO,GAC1B,EAAW,EAAK,QACtB,IAAK,IAAI,EAAI,EAAG,EAAI,EAAO,OAAQ,IAC1B,eAAe,EAAO,GAAI,IAAO,EAAS,KAAK,EAAO,IAI/D,OAAO,WAAW,EACtB,CAGA,SAAS,WAAW,EAAG,GACnB,MAAM,EAAO,CACT,IACA,KAAM,KACN,KAAM,KACN,KAAM,EACN,KAAM,EACN,KAAM,EACN,KAAM,GAaV,OAVK,GAKD,EAAK,KAAO,EAAK,KACjB,EAAK,KAAO,EACZ,EAAK,KAAK,KAAO,EACjB,EAAK,KAAO,IAPZ,EAAK,KAAO,EACZ,EAAK,KAAO,GAQT,CACX,CAGA,SAAS,UAAU,EAAI,GAEnB,MAAM,EAAK,EAAG,GAAK,EAAG,GAClB,EAAK,EAAG,GAAK,EAAG,GAEpB,OAAO,EAAK,EAAK,EAAK,CAC1B,CAGA,SAAS,UAAU,EAAG,EAAI,GAEtB,IAAI,EAAI,EAAG,GACP,EAAI,EAAG,GACP,EAAK,EAAG,GAAK,EACb,EAAK,EAAG,GAAK,EAEjB,GAAW,IAAP,GAAmB,IAAP,EAAU,CAEtB,MAAM,IAAM,EAAE,GAAK,GAAK,GAAM,EAAE,GAAK,GAAK,IAAO,EAAK,EAAK,EAAK,GAE5D,EAAI,GACJ,EAAI,EAAG,GACP,EAAI,EAAG,IAEA,EAAI,IACX,GAAK,EAAK,EACV,GAAK,EAAK,EAElB,CAKA,OAHA,EAAK,EAAE,GAAK,EACZ,EAAK,EAAE,GAAK,EAEL,EAAK,EAAK,EAAK,CAC1B,CAGA,SAAS,aAAa,EAAI,EAAI,EAAI,EAAI,EAAI,EAAI,EAAI,GAC9C,MAAM,EAAK,EAAK,EACV,EAAK,EAAK,EACV,EAAK,EAAK,EACV,EAAK,EAAK,EACV,EAAK,EAAK,EACV,EAAK,EAAK,EACV,EAAI,EAAK,EAAK,EAAK,EACnB,EAAI,EAAK,EAAK,EAAK,EACnB,EAAI,EAAK,EAAK,EAAK,EACnB,EAAI,EAAK,EAAK,EAAK,EACnB,EAAI,EAAK,EAAK,EAAK,EACnB,EAAI,EAAI,EAAI,EAAI,EAEtB,IAAI,EAAI,EACJ,EAAK,EACL,EAAK,EAEC,IAAN,GACA,EAAK,EACL,EAAK,EACL,EAAK,EACL,EAAK,IAEL,EAAK,EAAI,EAAI,EAAI,EACjB,EAAK,EAAI,EAAI,EAAI,EACb,EAAK,GACL,EAAK,EACL,EAAK,EACL,EAAK,GACE,EAAK,IACZ,EAAK,EACL,EAAK,EAAI,EACT,EAAK,IAIT,EAAK,GACL,EAAK,GACA,EAAI,EAAK,EAAK,GACT,EAAI,EAAG,EAAK,GAElB,GAAM,EACN,EAAK,IAEF,EAAK,IACZ,EAAK,GACC,EAAI,EAAK,EAAK,EAAK,GACf,EAAI,EAAI,EAAG,EAAK,GAEtB,GAAM,EAAI,EACV,EAAK,IAIb,MAAM,EAAY,IAAP,EAAW,EAAI,EAAK,EACzB,EAAY,IAAP,EAAW,EAAI,EAAK,EAMzB,GAFO,EAAI,GAAM,EAAK,EAAK,IAFrB,EAAI,GAAM,EAAK,EAAK,GAK1B,GAFO,EAAI,GAAM,EAAK,EAAK,IAFrB,EAAI,GAAM,EAAK,EAAK,GAMhC,OAAO,EAAK,EAAK,EAAK,CAC1B,CAEA,SAAS,WAAW,EAAG,GACnB,OAAO,EAAE,KAAO,EAAE,GAAK,EAAE,GAAK,EAAE,GAAK,EAAE,GAAK,EAAE,EAClD,CAEA,SAAS,WAAW,GAChB,EAAO,KAAK,YAEZ,MAAM,EAAQ,GACd,IAAK,IAAI,EAAI,EAAG,EAAI,EAAO,OAAQ,IAAK,CACpC,KAAO,EAAM,QAAU,GAAK,MAAM,EAAM,EAAM,OAAS,GAAI,EAAM,EAAM,OAAS,GAAI,EAAO,KAAO,GAC9F,EAAM,MAEV,EAAM,KAAK,EAAO,GACtB,CAEA,MAAM,EAAQ,GACd,IAAK,IAAI,EAAK,EAAO,OAAS,EAAG,GAAM,EAAG,IAAM,CAC5C,KAAO,EAAM,QAAU,GAAK,MAAM,EAAM,EAAM,OAAS,GAAI,EAAM,EAAM,OAAS,GAAI,EAAO,KAAQ,GAC/F,EAAM,MAEV,EAAM,KAAK,EAAO,GACtB,CAIA,OAFA,EAAM,MACN,EAAM,MACC,EAAM,OAAO,EACxB","file":"/npm/concaveman@2.0.0/index.js","sourceRoot":"","sourcesContent":["/**\n * Minified by jsDelivr using Terser v5.39.0.\n * Original file: /npm/concaveman@2.0.0/index.js\n *\n * Do NOT use SRI with dynamically generated files! More information: https://www.jsdelivr.com/using-sri-with-dynamic-files\n */\n","\nimport RBush from 'rbush';\nimport Queue from 'tinyqueue';\nimport pointInPolygon from 'point-in-polygon';\nimport {orient2d} from 'robust-predicates';\n\nexport default function concaveman(points, concavity, lengthThreshold) {\n    // a relative measure of concavity; higher value means simpler hull\n    concavity = Math.max(0, concavity === undefined ? 2 : concavity);\n\n    // when a segment goes below this length threshold, it won't be drilled down further\n    lengthThreshold = lengthThreshold || 0;\n\n    // start with a convex hull of the points\n    const hull = fastConvexHull(points);\n\n    // index the points with an R-tree\n    const tree = new RBush(16);\n    tree.toBBox = function (a) {\n        return {\n            minX: a[0],\n            minY: a[1],\n            maxX: a[0],\n            maxY: a[1]\n        };\n    };\n    tree.compareMinX = function (a, b) { return a[0] - b[0]; };\n    tree.compareMinY = function (a, b) { return a[1] - b[1]; };\n\n    tree.load(points);\n\n    // turn the convex hull into a linked list and populate the initial edge queue with the nodes\n    const queue = [];\n    let last;\n    for (let i = 0; i < hull.length; i++) {\n        const p = hull[i];\n        tree.remove(p);\n        last = insertNode(p, last);\n        queue.push(last);\n    }\n\n    // index the segments with an R-tree (for intersection checks)\n    const segTree = new RBush(16);\n    for (let i = 0; i < queue.length; i++) segTree.insert(updateBBox(queue[i]));\n\n    const sqConcavity = concavity * concavity;\n    const sqLenThreshold = lengthThreshold * lengthThreshold;\n\n    // process edges one by one\n    while (queue.length) {\n        const node = queue.shift();\n        const a = node.p;\n        const b = node.next.p;\n\n        // skip the edge if it's already short enough\n        const sqLen = getSqDist(a, b);\n        if (sqLen < sqLenThreshold) continue;\n\n        const maxSqLen = sqLen / sqConcavity;\n\n        // find the best connection point for the current edge to flex inward to\n        const p = findCandidate(tree, node.prev.p, a, b, node.next.next.p, maxSqLen, segTree);\n\n        // if we found a connection and it satisfies our concavity measure\n        if (p && Math.min(getSqDist(p, a), getSqDist(p, b)) <= maxSqLen) {\n            // connect the edge endpoints through this point and add 2 new edges to the queue\n            queue.push(node);\n            queue.push(insertNode(p, node));\n\n            // update point and segment indexes\n            tree.remove(p);\n            segTree.remove(node);\n            segTree.insert(updateBBox(node));\n            segTree.insert(updateBBox(node.next));\n        }\n    }\n\n    // convert the resulting hull linked list to an array of points\n    let node = last;\n    const concave = [];\n    do {\n        concave.push(node.p);\n        node = node.next;\n    } while (node !== last);\n\n    concave.push(node.p);\n\n    return concave;\n}\n\nfunction findCandidate(tree, a, b, c, d, maxDist, segTree) {\n    const queue = new Queue([], compareDist);\n    let node = tree.data;\n\n    // search through the point R-tree with a depth-first search using a priority queue\n    // in the order of distance to the edge (b, c)\n    while (node) {\n        for (let i = 0; i < node.children.length; i++) {\n            const child = node.children[i];\n\n            const dist = node.leaf ? sqSegDist(child, b, c) : sqSegBoxDist(b, c, child);\n            if (dist > maxDist) continue; // skip the node if it's farther than we ever need\n\n            queue.push({\n                node: child,\n                dist\n            });\n        }\n\n        while (queue.length && !queue.peek().node.children) {\n            const item = queue.pop();\n            const p = item.node;\n\n            // skip all points that are as close to adjacent edges (a,b) and (c,d),\n            // and points that would introduce self-intersections when connected\n            const d0 = sqSegDist(p, a, b);\n            const d1 = sqSegDist(p, c, d);\n            if (item.dist < d0 && item.dist < d1 &&\n                noIntersections(b, p, segTree) &&\n                noIntersections(c, p, segTree)) return p;\n        }\n\n        node = queue.pop();\n        if (node) node = node.node;\n    }\n\n    return null;\n}\n\nfunction compareDist(a, b) {\n    return a.dist - b.dist;\n}\n\n// square distance from a segment bounding box to the given one\nfunction sqSegBoxDist(a, b, bbox) {\n    if (inside(a, bbox) || inside(b, bbox)) return 0;\n    const d1 = sqSegSegDist(a[0], a[1], b[0], b[1], bbox.minX, bbox.minY, bbox.maxX, bbox.minY);\n    if (d1 === 0) return 0;\n    const d2 = sqSegSegDist(a[0], a[1], b[0], b[1], bbox.minX, bbox.minY, bbox.minX, bbox.maxY);\n    if (d2 === 0) return 0;\n    const d3 = sqSegSegDist(a[0], a[1], b[0], b[1], bbox.maxX, bbox.minY, bbox.maxX, bbox.maxY);\n    if (d3 === 0) return 0;\n    const d4 = sqSegSegDist(a[0], a[1], b[0], b[1], bbox.minX, bbox.maxY, bbox.maxX, bbox.maxY);\n    if (d4 === 0) return 0;\n    return Math.min(d1, d2, d3, d4);\n}\n\nfunction inside(a, bbox) {\n    return a[0] >= bbox.minX &&\n           a[0] <= bbox.maxX &&\n           a[1] >= bbox.minY &&\n           a[1] <= bbox.maxY;\n}\n\n// check if the edge (a,b) doesn't intersect any other edges\nfunction noIntersections(a, b, segTree) {\n    const minX = Math.min(a[0], b[0]);\n    const minY = Math.min(a[1], b[1]);\n    const maxX = Math.max(a[0], b[0]);\n    const maxY = Math.max(a[1], b[1]);\n\n    const edges = segTree.search({minX, minY, maxX, maxY});\n    for (let i = 0; i < edges.length; i++) {\n        if (intersects(edges[i].p, edges[i].next.p, a, b)) return false;\n    }\n    return true;\n}\n\nfunction cross(p1, p2, p3) {\n    return orient2d(p1[0], p1[1], p2[0], p2[1], p3[0], p3[1]);\n}\n\n// check if the edges (p1,q1) and (p2,q2) intersect\nfunction intersects(p1, q1, p2, q2) {\n    return p1 !== q2 && q1 !== p2 &&\n        cross(p1, q1, p2) > 0 !== cross(p1, q1, q2) > 0 &&\n        cross(p2, q2, p1) > 0 !== cross(p2, q2, q1) > 0;\n}\n\n// update the bounding box of a node's edge\nfunction updateBBox(node) {\n    const p1 = node.p;\n    const p2 = node.next.p;\n    node.minX = Math.min(p1[0], p2[0]);\n    node.minY = Math.min(p1[1], p2[1]);\n    node.maxX = Math.max(p1[0], p2[0]);\n    node.maxY = Math.max(p1[1], p2[1]);\n    return node;\n}\n\n// speed up convex hull by filtering out points inside quadrilateral formed by 4 extreme points\nfunction fastConvexHull(points) {\n    let left = points[0];\n    let top = points[0];\n    let right = points[0];\n    let bottom = points[0];\n\n    // find the leftmost, rightmost, topmost and bottommost points\n    for (let i = 0; i < points.length; i++) {\n        const p = points[i];\n        if (p[0] < left[0]) left = p;\n        if (p[0] > right[0]) right = p;\n        if (p[1] < top[1]) top = p;\n        if (p[1] > bottom[1]) bottom = p;\n    }\n\n    // filter out points that are inside the resulting quadrilateral\n    const cull = [left, top, right, bottom];\n    const filtered = cull.slice();\n    for (let i = 0; i < points.length; i++) {\n        if (!pointInPolygon(points[i], cull)) filtered.push(points[i]);\n    }\n\n    // get convex hull around the filtered points\n    return convexHull(filtered);\n}\n\n// create a new node in a doubly linked list\nfunction insertNode(p, prev) {\n    const node = {\n        p,\n        prev: null,\n        next: null,\n        minX: 0,\n        minY: 0,\n        maxX: 0,\n        maxY: 0\n    };\n\n    if (!prev) {\n        node.prev = node;\n        node.next = node;\n\n    } else {\n        node.next = prev.next;\n        node.prev = prev;\n        prev.next.prev = node;\n        prev.next = node;\n    }\n    return node;\n}\n\n// square distance between 2 points\nfunction getSqDist(p1, p2) {\n\n    const dx = p1[0] - p2[0],\n        dy = p1[1] - p2[1];\n\n    return dx * dx + dy * dy;\n}\n\n// square distance from a point to a segment\nfunction sqSegDist(p, p1, p2) {\n\n    let x = p1[0],\n        y = p1[1],\n        dx = p2[0] - x,\n        dy = p2[1] - y;\n\n    if (dx !== 0 || dy !== 0) {\n\n        const t = ((p[0] - x) * dx + (p[1] - y) * dy) / (dx * dx + dy * dy);\n\n        if (t > 1) {\n            x = p2[0];\n            y = p2[1];\n\n        } else if (t > 0) {\n            x += dx * t;\n            y += dy * t;\n        }\n    }\n\n    dx = p[0] - x;\n    dy = p[1] - y;\n\n    return dx * dx + dy * dy;\n}\n\n// segment to segment distance, ported from http://geomalgorithms.com/a07-_distance.html by Dan Sunday\nfunction sqSegSegDist(x0, y0, x1, y1, x2, y2, x3, y3) {\n    const ux = x1 - x0;\n    const uy = y1 - y0;\n    const vx = x3 - x2;\n    const vy = y3 - y2;\n    const wx = x0 - x2;\n    const wy = y0 - y2;\n    const a = ux * ux + uy * uy;\n    const b = ux * vx + uy * vy;\n    const c = vx * vx + vy * vy;\n    const d = ux * wx + uy * wy;\n    const e = vx * wx + vy * wy;\n    const D = a * c - b * b;\n\n    let sN, tN;\n    let sD = D;\n    let tD = D;\n\n    if (D === 0) {\n        sN = 0;\n        sD = 1;\n        tN = e;\n        tD = c;\n    } else {\n        sN = b * e - c * d;\n        tN = a * e - b * d;\n        if (sN < 0) {\n            sN = 0;\n            tN = e;\n            tD = c;\n        } else if (sN > sD) {\n            sN = sD;\n            tN = e + b;\n            tD = c;\n        }\n    }\n\n    if (tN < 0.0) {\n        tN = 0.0;\n        if (-d < 0.0) sN = 0.0;\n        else if (-d > a) sN = sD;\n        else {\n            sN = -d;\n            sD = a;\n        }\n    } else if (tN > tD) {\n        tN = tD;\n        if ((-d + b) < 0.0) sN = 0;\n        else if (-d + b > a) sN = sD;\n        else {\n            sN = -d + b;\n            sD = a;\n        }\n    }\n\n    const sc = sN === 0 ? 0 : sN / sD;\n    const tc = tN === 0 ? 0 : tN / tD;\n\n    const cx = (1 - sc) * x0 + sc * x1;\n    const cy = (1 - sc) * y0 + sc * y1;\n    const cx2 = (1 - tc) * x2 + tc * x3;\n    const cy2 = (1 - tc) * y2 + tc * y3;\n    const dx = cx2 - cx;\n    const dy = cy2 - cy;\n\n    return dx * dx + dy * dy;\n}\n\nfunction compareByX(a, b) {\n    return a[0] === b[0] ? a[1] - b[1] : a[0] - b[0];\n}\n\nfunction convexHull(points) {\n    points.sort(compareByX);\n\n    const lower = [];\n    for (let i = 0; i < points.length; i++) {\n        while (lower.length >= 2 && cross(lower[lower.length - 2], lower[lower.length - 1], points[i]) <= 0) {\n            lower.pop();\n        }\n        lower.push(points[i]);\n    }\n\n    const upper = [];\n    for (let ii = points.length - 1; ii >= 0; ii--) {\n        while (upper.length >= 2 && cross(upper[upper.length - 2], upper[upper.length - 1], points[ii]) <= 0) {\n            upper.pop();\n        }\n        upper.push(points[ii]);\n    }\n\n    upper.pop();\n    lower.pop();\n    return lower.concat(upper);\n}\n"]}