{"version":3,"sources":["jsdelivr-header.js","/npm/delatin@0.2.0/index.js"],"names":[],"mappings":"AAAA;AACA;AACA;AACA;AACA;AACA;AACA,eCLe,MAAM,QAEjB,WAAA,CAAY,EAAM,EAAO,EAAS,GAC9B,KAAK,KAAO,EACZ,KAAK,MAAQ,EACb,KAAK,OAAS,EAEd,KAAK,OAAS,GACd,KAAK,UAAY,GAGjB,KAAK,WAAa,GAClB,KAAK,YAAc,GACnB,KAAK,cAAgB,GAErB,KAAK,OAAS,GACd,KAAK,QAAU,GACf,KAAK,SAAW,GAChB,KAAK,YAAc,EAEnB,KAAK,SAAW,EAChB,KAAK,OACT,CAGA,GAAA,CAAI,EAAW,GACX,KAAO,KAAK,cAAgB,GACxB,KAAK,QAEb,CAGA,MAAA,GACI,KAAK,QACL,KAAK,QACT,CAGA,WAAA,GACI,OAAO,KAAK,QAAQ,EACxB,CAGA,OAAA,GACI,OAAO,KAAK,KAAK,KAAK,SAAW,KAAK,QAAQ,OAClD,CAGA,QAAA,CAAS,EAAG,GACR,OAAO,KAAK,KAAK,KAAK,MAAQ,EAAI,EACtC,CAEA,KAAA,GACI,MAAM,EAAK,KAAK,MAAQ,EAClB,EAAK,KAAK,OAAS,EACnB,EAAK,KAAK,UAAU,EAAG,GACvB,EAAK,KAAK,UAAU,EAAI,GACxB,EAAK,KAAK,UAAU,EAAG,GACvB,EAAK,KAAK,UAAU,EAAI,GAGxB,EAAK,KAAK,aAAa,EAAI,EAAI,GAAK,GAAI,GAAI,GAClD,KAAK,aAAa,EAAI,EAAI,EAAI,GAAK,GAAI,GACvC,KAAK,QACT,CAGA,MAAA,GACI,MAAM,EAAS,KAAK,OACpB,IAAK,IAAI,EAAI,EAAG,EAAI,KAAK,YAAa,IAAK,CACvC,MAAM,EAAI,KAAK,SAAS,GAElB,EAAI,EAAI,KAAK,UAAc,EAAJ,EAAQ,GAC/B,EAAI,EAAI,KAAK,UAAc,EAAJ,EAAQ,GAC/B,EAAI,EAAI,KAAK,UAAc,EAAJ,EAAQ,GACrC,KAAK,eAAe,EAAO,GAAI,EAAO,EAAI,GAAI,EAAO,GAAI,EAAO,EAAI,GAAI,EAAO,GAAI,EAAO,EAAI,GAAI,EACtG,CACA,KAAK,YAAc,CACvB,CAGA,cAAA,CAAe,EAAK,EAAK,EAAK,EAAK,EAAK,EAAK,GAEzC,MAAM,EAAO,KAAK,IAAI,EAAK,EAAK,GAC1B,EAAO,KAAK,IAAI,EAAK,EAAK,GAC1B,EAAO,KAAK,IAAI,EAAK,EAAK,GAC1B,EAAO,KAAK,IAAI,EAAK,EAAK,GAGhC,IAAI,EAAM,OAAO,EAAK,EAAK,EAAK,EAAK,EAAM,GACvC,EAAM,OAAO,EAAK,EAAK,EAAK,EAAK,EAAM,GACvC,EAAM,OAAO,EAAK,EAAK,EAAK,EAAK,EAAM,GAC3C,MAAM,EAAM,EAAM,EACZ,EAAM,EAAM,EACZ,EAAM,EAAM,EACZ,EAAM,EAAM,EACZ,EAAM,EAAM,EACZ,EAAM,EAAM,EAGZ,EAAI,OAAO,EAAK,EAAK,EAAK,EAAK,EAAK,GACpC,EAAK,KAAK,SAAS,EAAK,GAAO,EAC/B,EAAK,KAAK,SAAS,EAAK,GAAO,EAC/B,EAAK,KAAK,SAAS,EAAK,GAAO,EAGrC,IAAI,EAAW,EACX,EAAK,EACL,EAAK,EACT,IAAK,IAAI,EAAI,EAAM,GAAK,EAAM,IAAK,CAE/B,IAAI,EAAK,EACL,EAAM,GAAa,IAAR,IACX,EAAK,KAAK,IAAI,EAAI,KAAK,OAAO,EAAM,KAEpC,EAAM,GAAa,IAAR,IACX,EAAK,KAAK,IAAI,EAAI,KAAK,OAAO,EAAM,KAEpC,EAAM,GAAa,IAAR,IACX,EAAK,KAAK,IAAI,EAAI,KAAK,OAAO,EAAM,KAGxC,IAAI,EAAK,EAAM,EAAM,EACjB,EAAK,EAAM,EAAM,EACjB,EAAK,EAAM,EAAM,EAEjB,GAAY,EAEhB,IAAK,IAAI,EAAI,EAAO,EAAI,GAAK,EAAM,IAAK,CAEpC,GAAI,GAAM,GAAK,GAAM,GAAK,GAAM,EAAG,CAC/B,GAAY,EAGZ,MAAM,EAAI,EAAK,EAAK,EAAK,EAAK,EAAK,EAC7B,EAAK,KAAK,IAAI,EAAI,KAAK,SAAS,EAAG,IACrC,EAAK,IACL,EAAW,EACX,EAAK,EACL,EAAK,EAEb,MAAO,GAAI,EACP,MAGJ,GAAM,EACN,GAAM,EACN,GAAM,CACV,CAEA,GAAO,EACP,GAAO,EACP,GAAO,CACX,EAEI,IAAO,GAAO,IAAO,GAAO,IAAO,GAAO,IAAO,GAAO,IAAO,GAAO,IAAO,KAC7E,EAAW,GAIf,KAAK,YAAY,EAAI,GAAK,EAC1B,KAAK,YAAY,EAAI,EAAI,GAAK,EAG9B,KAAK,WAAW,EAAG,EACvB,CAGA,KAAA,GAEI,MAAM,EAAI,KAAK,YAET,EAAS,EAAJ,EAAQ,EACb,EAAS,EAAJ,EAAQ,EACb,EAAS,EAAJ,EAAQ,EAEb,EAAK,KAAK,UAAU,GACpB,EAAK,KAAK,UAAU,GACpB,EAAK,KAAK,UAAU,GAEpB,EAAK,KAAK,OAAO,EAAI,GACrB,EAAK,KAAK,OAAO,EAAI,EAAK,GAC1B,EAAK,KAAK,OAAO,EAAI,GACrB,EAAK,KAAK,OAAO,EAAI,EAAK,GAC1B,EAAK,KAAK,OAAO,EAAI,GACrB,EAAK,KAAK,OAAO,EAAI,EAAK,GAC1B,EAAK,KAAK,YAAY,EAAI,GAC1B,EAAK,KAAK,YAAY,EAAI,EAAI,GAE9B,EAAK,KAAK,UAAU,EAAI,GAE9B,GAAuC,IAAnC,OAAO,EAAI,EAAI,EAAI,EAAI,EAAI,GAC3B,KAAK,iBAAiB,EAAI,QAEvB,GAAuC,IAAnC,OAAO,EAAI,EAAI,EAAI,EAAI,EAAI,GAClC,KAAK,iBAAiB,EAAI,QAEvB,GAAuC,IAAnC,OAAO,EAAI,EAAI,EAAI,EAAI,EAAI,GAClC,KAAK,iBAAiB,EAAI,OAEvB,CACH,MAAM,EAAK,KAAK,WAAW,GACrB,EAAK,KAAK,WAAW,GACrB,EAAK,KAAK,WAAW,GAErB,EAAK,KAAK,aAAa,EAAI,EAAI,EAAI,GAAK,GAAI,EAAG,GAC/C,EAAK,KAAK,aAAa,EAAI,EAAI,EAAI,GAAK,EAAG,EAAK,GAChD,EAAK,KAAK,aAAa,EAAI,EAAI,EAAI,EAAI,EAAK,EAAG,EAAK,GAE1D,KAAK,UAAU,GACf,KAAK,UAAU,GACf,KAAK,UAAU,EACnB,CACJ,CAGA,SAAA,CAAU,EAAG,GACT,MAAM,EAAI,KAAK,OAAO,QAAU,EAEhC,OADA,KAAK,OAAO,KAAK,EAAG,GACb,CACX,CAGA,YAAA,CAAa,EAAG,EAAG,EAAG,EAAI,EAAI,EAAI,EAAI,KAAK,UAAU,QACjD,MAAM,EAAI,EAAI,EAgCd,OA7BA,KAAK,UAAU,EAAI,GAAK,EACxB,KAAK,UAAU,EAAI,GAAK,EACxB,KAAK,UAAU,EAAI,GAAK,EAGxB,KAAK,WAAW,EAAI,GAAK,EACzB,KAAK,WAAW,EAAI,GAAK,EACzB,KAAK,WAAW,EAAI,GAAK,EAGrB,GAAM,IACN,KAAK,WAAW,GAAM,EAAI,GAE1B,GAAM,IACN,KAAK,WAAW,GAAM,EAAI,GAE1B,GAAM,IACN,KAAK,WAAW,GAAM,EAAI,GAI9B,KAAK,YAAY,EAAI,EAAI,GAAK,EAC9B,KAAK,YAAY,EAAI,EAAI,GAAK,EAC9B,KAAK,cAAc,IAAM,EAGzB,KAAK,SAAS,KAAK,eAAiB,EAG7B,CACX,CAEA,SAAA,CAAU,GAgBN,MAAM,EAAI,KAAK,WAAW,GAE1B,GAAI,EAAI,EACJ,OAGJ,MAAM,EAAK,EAAI,EAAI,EACb,EAAK,EAAI,EAAI,EACb,EAAK,GAAM,EAAI,GAAK,EACpB,EAAK,GAAM,EAAI,GAAK,EACpB,EAAK,GAAM,EAAI,GAAK,EACpB,EAAK,GAAM,EAAI,GAAK,EACpB,EAAK,KAAK,UAAU,GACpB,EAAK,KAAK,UAAU,GACpB,EAAK,KAAK,UAAU,GACpB,EAAK,KAAK,UAAU,GACpB,EAAS,KAAK,OAEpB,IAAK,SACD,EAAO,EAAI,GAAK,EAAO,EAAI,EAAK,GAChC,EAAO,EAAI,GAAK,EAAO,EAAI,EAAK,GAChC,EAAO,EAAI,GAAK,EAAO,EAAI,EAAK,GAChC,EAAO,EAAI,GAAK,EAAO,EAAI,EAAK,IAChC,OAGJ,MAAM,EAAM,KAAK,WAAW,GACtB,EAAM,KAAK,WAAW,GACtB,EAAM,KAAK,WAAW,GACtB,EAAM,KAAK,WAAW,GAE5B,KAAK,aAAa,EAAK,GACvB,KAAK,aAAa,EAAK,GAEvB,MAAM,EAAK,KAAK,aAAa,EAAI,EAAI,GAAK,EAAG,EAAK,EAAK,GACjD,EAAK,KAAK,aAAa,EAAI,EAAI,EAAI,EAAI,EAAK,EAAK,GAEvD,KAAK,UAAU,EAAK,GACpB,KAAK,UAAU,EAAK,EACxB,CAGA,gBAAA,CAAiB,EAAI,GACjB,MAAM,EAAK,EAAI,EAAI,EACb,EAAK,GAAM,EAAI,GAAK,EACpB,EAAK,GAAM,EAAI,GAAK,EACpB,EAAK,KAAK,UAAU,GACpB,EAAK,KAAK,UAAU,GACpB,EAAK,KAAK,UAAU,GACpB,EAAM,KAAK,WAAW,GACtB,EAAM,KAAK,WAAW,GAEtB,EAAI,KAAK,WAAW,GAE1B,GAAI,EAAI,EAAG,CACP,MAAM,EAAK,KAAK,aAAa,EAAI,EAAI,GAAK,EAAG,GAAM,EAAG,GAChD,EAAK,KAAK,aAAa,EAAI,EAAI,EAAI,GAAK,EAAG,GAGjD,OAFA,KAAK,UAAU,EAAK,QACpB,KAAK,UAAU,EAAK,EAExB,CAEA,MAAM,EAAK,EAAI,EAAI,EACb,EAAK,GAAM,EAAI,GAAK,EACpB,EAAK,GAAM,EAAI,GAAK,EACpB,EAAK,KAAK,UAAU,GACpB,EAAM,KAAK,WAAW,GACtB,EAAM,KAAK,WAAW,GAE5B,KAAK,aAAa,EAAK,GAEvB,MAAM,EAAK,KAAK,aAAa,EAAI,EAAI,EAAI,GAAM,GAAI,EAAG,GAChD,EAAK,KAAK,aAAa,EAAI,EAAI,EAAI,GAAM,EAAG,EAAK,EAAG,GACpD,EAAK,KAAK,aAAa,EAAI,EAAI,EAAI,GAAM,EAAG,EAAK,GACjD,EAAK,KAAK,aAAa,EAAI,EAAI,EAAI,EAAK,EAAK,EAAG,EAAK,GAE3D,KAAK,UAAU,GACf,KAAK,UAAU,GACf,KAAK,UAAU,GACf,KAAK,UAAU,EACnB,CAIA,UAAA,CAAW,EAAG,GACV,MAAM,EAAI,KAAK,OAAO,OACtB,KAAK,cAAc,GAAK,EACxB,KAAK,OAAO,KAAK,GACjB,KAAK,QAAQ,KAAK,GAClB,KAAK,UAAY,EAAQ,EACzB,KAAK,SAAS,EAClB,CAEA,SAAA,GACI,MAAM,EAAI,KAAK,OAAO,OAAS,EAG/B,OAFA,KAAK,WAAW,EAAG,GACnB,KAAK,WAAW,EAAG,GACZ,KAAK,eAChB,CAEA,aAAA,GACI,MAAM,EAAI,KAAK,OAAO,MAChB,EAAI,KAAK,QAAQ,MAGvB,OAFA,KAAK,UAAY,EAAI,EACrB,KAAK,cAAc,IAAM,EAClB,CACX,CAEA,YAAA,CAAa,GACT,MAAM,EAAI,KAAK,cAAc,GAC7B,GAAI,EAAI,EAAG,CACP,MAAM,EAAK,KAAK,SAAS,QAAQ,GACjC,IAAY,IAAR,EAGA,MAAM,IAAI,MAAM,gDAEpB,YAJI,KAAK,SAAS,GAAM,KAAK,WAAW,KAAK,aAKjD,CACA,MAAM,EAAI,KAAK,OAAO,OAAS,EAC3B,IAAM,IACN,KAAK,WAAW,EAAG,GACd,KAAK,WAAW,EAAG,IACpB,KAAK,SAAS,IAGtB,KAAK,eACT,CAEA,UAAA,CAAW,EAAG,GACV,OAAO,KAAK,QAAQ,GAAK,KAAK,QAAQ,EAC1C,CAEA,UAAA,CAAW,EAAG,GACV,MAAM,EAAK,KAAK,OAAO,GACjB,EAAK,KAAK,OAAO,GACvB,KAAK,OAAO,GAAK,EACjB,KAAK,OAAO,GAAK,EACjB,KAAK,cAAc,GAAM,EACzB,KAAK,cAAc,GAAM,EACzB,MAAM,EAAI,KAAK,QAAQ,GACvB,KAAK,QAAQ,GAAK,KAAK,QAAQ,GAC/B,KAAK,QAAQ,GAAK,CACtB,CAEA,QAAA,CAAS,GACL,IAAI,EAAI,EACR,OAAa,CACT,MAAM,EAAK,EAAI,GAAM,EACrB,GAAI,IAAM,IAAM,KAAK,WAAW,EAAG,GAC/B,MAEJ,KAAK,WAAW,EAAG,GACnB,EAAI,CACR,CACJ,CAEA,UAAA,CAAW,EAAI,GACX,IAAI,EAAI,EACR,OAAa,CACT,MAAM,EAAK,EAAI,EAAI,EACnB,GAAI,GAAM,GAAK,EAAK,EAChB,MAEJ,MAAM,EAAK,EAAK,EAChB,IAAI,EAAI,EAIR,GAHI,EAAK,GAAK,KAAK,WAAW,EAAI,KAC9B,EAAI,IAEH,KAAK,WAAW,EAAG,GACpB,MAEJ,KAAK,WAAW,EAAG,GACnB,EAAI,CACR,CACA,OAAO,EAAI,CACf,EAGJ,SAAS,OAAO,EAAI,EAAI,EAAI,EAAI,EAAI,GAChC,OAAQ,EAAK,IAAO,EAAK,IAAO,EAAK,IAAO,EAAK,EACrD,CAEA,SAAS,SAAS,EAAI,EAAI,EAAI,EAAI,EAAI,EAAI,EAAI,GAC1C,MAAM,EAAK,EAAK,EACV,EAAK,EAAK,EACV,EAAK,EAAK,EACV,EAAK,EAAK,EACV,EAAK,EAAK,EACV,EAAK,EAAK,EAGV,EAAK,EAAK,EAAK,EAAK,EACpB,EAAK,EAAK,EAAK,EAAK,EAE1B,OAAO,GAAM,EAAK,EAAK,EAAK,GACrB,GAAM,EAAK,EAAK,EAAK,IALjB,EAAK,EAAK,EAAK,IAMb,EAAK,EAAK,EAAK,GAAM,CACtC","file":"/npm/delatin@0.2.0/index.js","sourceRoot":"","sourcesContent":["/**\n * Minified by jsDelivr using Terser v5.39.0.\n * Original file: /npm/delatin@0.2.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","\nexport default class Delatin {\n\n    constructor(data, width, height = width) {\n        this.data = data; // height data\n        this.width = width;\n        this.height = height;\n\n        this.coords = []; // vertex coordinates (x, y)\n        this.triangles = []; // mesh triangle indices\n\n        // additional triangle data\n        this._halfedges = [];\n        this._candidates = [];\n        this._queueIndices = [];\n\n        this._queue = []; // queue of added triangles\n        this._errors = [];\n        this._pending = []; // triangles pending addition to queue\n        this._pendingLen = 0;\n\n        this._rmsdSum = 0;\n        this._init();\n    }\n\n    // refine the mesh until its maximum error gets below the given one\n    run(maxError = 1) {\n        while (this.getMaxError() > maxError) {\n            this.refine();\n        }\n    }\n\n    // refine the mesh with a single point\n    refine() {\n        this._step();\n        this._flush();\n    }\n\n    // max error of the current mesh\n    getMaxError() {\n        return this._errors[0];\n    }\n\n    // root-mean-square deviation of the current mesh\n    getRMSD() {\n        return Math.sqrt(this._rmsdSum / this._errors.length);\n    }\n\n    // height value at a given position\n    heightAt(x, y) {\n        return this.data[this.width * y + x];\n    }\n\n    _init() {\n        const x1 = this.width - 1;\n        const y1 = this.height - 1;\n        const p0 = this._addPoint(0, 0);\n        const p1 = this._addPoint(x1, 0);\n        const p2 = this._addPoint(0, y1);\n        const p3 = this._addPoint(x1, y1);\n\n        // add initial two triangles\n        const t0 = this._addTriangle(p3, p0, p2, -1, -1, -1);\n        this._addTriangle(p0, p3, p1, t0, -1, -1);\n        this._flush();\n    }\n\n    // rasterize and queue all triangles that got added or updated in _step\n    _flush() {\n        const coords = this.coords;\n        for (let i = 0; i < this._pendingLen; i++) {\n            const t = this._pending[i];\n            // rasterize triangle to find maximum pixel error\n            const a = 2 * this.triangles[t * 3 + 0];\n            const b = 2 * this.triangles[t * 3 + 1];\n            const c = 2 * this.triangles[t * 3 + 2];\n            this._findCandidate(coords[a], coords[a + 1], coords[b], coords[b + 1], coords[c], coords[c + 1], t);\n        }\n        this._pendingLen = 0;\n    }\n\n    // rasterize a triangle, find its max error, and queue it for processing\n    _findCandidate(p0x, p0y, p1x, p1y, p2x, p2y, t) {\n        // triangle bounding box\n        const minX = Math.min(p0x, p1x, p2x);\n        const minY = Math.min(p0y, p1y, p2y);\n        const maxX = Math.max(p0x, p1x, p2x);\n        const maxY = Math.max(p0y, p1y, p2y);\n\n        // forward differencing variables\n        let w00 = orient(p1x, p1y, p2x, p2y, minX, minY);\n        let w01 = orient(p2x, p2y, p0x, p0y, minX, minY);\n        let w02 = orient(p0x, p0y, p1x, p1y, minX, minY);\n        const a01 = p1y - p0y;\n        const b01 = p0x - p1x;\n        const a12 = p2y - p1y;\n        const b12 = p1x - p2x;\n        const a20 = p0y - p2y;\n        const b20 = p2x - p0x;\n\n        // pre-multiplied z values at vertices\n        const a = orient(p0x, p0y, p1x, p1y, p2x, p2y);\n        const z0 = this.heightAt(p0x, p0y) / a;\n        const z1 = this.heightAt(p1x, p1y) / a;\n        const z2 = this.heightAt(p2x, p2y) / a;\n\n        // iterate over pixels in bounding box\n        let maxError = 0;\n        let mx = 0;\n        let my = 0;\n        for (let y = minY; y <= maxY; y++) {\n            // compute starting offset\n            let dx = 0;\n            if (w00 < 0 && a12 !== 0) {\n                dx = Math.max(dx, Math.floor(-w00 / a12));\n            }\n            if (w01 < 0 && a20 !== 0) {\n                dx = Math.max(dx, Math.floor(-w01 / a20));\n            }\n            if (w02 < 0 && a01 !== 0) {\n                dx = Math.max(dx, Math.floor(-w02 / a01));\n            }\n\n            let w0 = w00 + a12 * dx;\n            let w1 = w01 + a20 * dx;\n            let w2 = w02 + a01 * dx;\n\n            let wasInside = false;\n\n            for (let x = minX + dx; x <= maxX; x++) {\n                // check if inside triangle\n                if (w0 >= 0 && w1 >= 0 && w2 >= 0) {\n                    wasInside = true;\n\n                    // compute z using barycentric coordinates\n                    const z = z0 * w0 + z1 * w1 + z2 * w2;\n                    const dz = Math.abs(z - this.heightAt(x, y));\n                    if (dz > maxError) {\n                        maxError = dz;\n                        mx = x;\n                        my = y;\n                    }\n                } else if (wasInside) {\n                    break;\n                }\n\n                w0 += a12;\n                w1 += a20;\n                w2 += a01;\n            }\n\n            w00 += b12;\n            w01 += b20;\n            w02 += b01;\n        }\n\n        if (mx === p0x && my === p0y || mx === p1x && my === p1y || mx === p2x && my === p2y) {\n            maxError = 0;\n        }\n\n        // update triangle metadata\n        this._candidates[2 * t] = mx;\n        this._candidates[2 * t + 1] = my;\n\n        // add triangle to priority queue\n        this._queuePush(t, maxError);\n    }\n\n    // process the next triangle in the queue, splitting it with a new point\n    _step() {\n        // pop triangle with highest error from priority queue\n        const t = this._queuePop();\n\n        const e0 = t * 3 + 0;\n        const e1 = t * 3 + 1;\n        const e2 = t * 3 + 2;\n\n        const p0 = this.triangles[e0];\n        const p1 = this.triangles[e1];\n        const p2 = this.triangles[e2];\n\n        const ax = this.coords[2 * p0];\n        const ay = this.coords[2 * p0 + 1];\n        const bx = this.coords[2 * p1];\n        const by = this.coords[2 * p1 + 1];\n        const cx = this.coords[2 * p2];\n        const cy = this.coords[2 * p2 + 1];\n        const px = this._candidates[2 * t];\n        const py = this._candidates[2 * t + 1];\n\n        const pn = this._addPoint(px, py);\n\n        if (orient(ax, ay, bx, by, px, py) === 0) {\n            this._handleCollinear(pn, e0);\n\n        } else if (orient(bx, by, cx, cy, px, py) === 0) {\n            this._handleCollinear(pn, e1);\n\n        } else if (orient(cx, cy, ax, ay, px, py) === 0) {\n            this._handleCollinear(pn, e2);\n\n        } else {\n            const h0 = this._halfedges[e0];\n            const h1 = this._halfedges[e1];\n            const h2 = this._halfedges[e2];\n\n            const t0 = this._addTriangle(p0, p1, pn, h0, -1, -1, e0);\n            const t1 = this._addTriangle(p1, p2, pn, h1, -1, t0 + 1);\n            const t2 = this._addTriangle(p2, p0, pn, h2, t0 + 2, t1 + 1);\n\n            this._legalize(t0);\n            this._legalize(t1);\n            this._legalize(t2);\n        }\n    }\n\n    // add coordinates for a new vertex\n    _addPoint(x, y) {\n        const i = this.coords.length >> 1;\n        this.coords.push(x, y);\n        return i;\n    }\n\n    // add or update a triangle in the mesh\n    _addTriangle(a, b, c, ab, bc, ca, e = this.triangles.length) {\n        const t = e / 3; // new triangle index\n\n        // add triangle vertices\n        this.triangles[e + 0] = a;\n        this.triangles[e + 1] = b;\n        this.triangles[e + 2] = c;\n\n        // add triangle halfedges\n        this._halfedges[e + 0] = ab;\n        this._halfedges[e + 1] = bc;\n        this._halfedges[e + 2] = ca;\n\n        // link neighboring halfedges\n        if (ab >= 0) {\n            this._halfedges[ab] = e + 0;\n        }\n        if (bc >= 0) {\n            this._halfedges[bc] = e + 1;\n        }\n        if (ca >= 0) {\n            this._halfedges[ca] = e + 2;\n        }\n\n        // init triangle metadata\n        this._candidates[2 * t + 0] = 0;\n        this._candidates[2 * t + 1] = 0;\n        this._queueIndices[t] = -1;\n\n        // add triangle to pending queue for later rasterization\n        this._pending[this._pendingLen++] = t;\n\n        // return first halfedge index\n        return e;\n    }\n\n    _legalize(a) {\n        // if the pair of triangles doesn't satisfy the Delaunay condition\n        // (p1 is inside the circumcircle of [p0, pl, pr]), flip them,\n        // then do the same check/flip recursively for the new pair of triangles\n        //\n        //           pl                    pl\n        //          /||\\                  /  \\\n        //       al/ || \\bl            al/    \\a\n        //        /  ||  \\              /      \\\n        //       /  a||b  \\    flip    /___ar___\\\n        //     p0\\   ||   /p1   =>   p0\\---bl---/p1\n        //        \\  ||  /              \\      /\n        //       ar\\ || /br             b\\    /br\n        //          \\||/                  \\  /\n        //           pr                    pr\n\n        const b = this._halfedges[a];\n\n        if (b < 0) {\n            return;\n        }\n\n        const a0 = a - a % 3;\n        const b0 = b - b % 3;\n        const al = a0 + (a + 1) % 3;\n        const ar = a0 + (a + 2) % 3;\n        const bl = b0 + (b + 2) % 3;\n        const br = b0 + (b + 1) % 3;\n        const p0 = this.triangles[ar];\n        const pr = this.triangles[a];\n        const pl = this.triangles[al];\n        const p1 = this.triangles[bl];\n        const coords = this.coords;\n\n        if (!inCircle(\n            coords[2 * p0], coords[2 * p0 + 1],\n            coords[2 * pr], coords[2 * pr + 1],\n            coords[2 * pl], coords[2 * pl + 1],\n            coords[2 * p1], coords[2 * p1 + 1])) {\n            return;\n        }\n\n        const hal = this._halfedges[al];\n        const har = this._halfedges[ar];\n        const hbl = this._halfedges[bl];\n        const hbr = this._halfedges[br];\n\n        this._queueRemove(a0 / 3);\n        this._queueRemove(b0 / 3);\n\n        const t0 = this._addTriangle(p0, p1, pl, -1, hbl, hal, a0);\n        const t1 = this._addTriangle(p1, p0, pr, t0, har, hbr, b0);\n\n        this._legalize(t0 + 1);\n        this._legalize(t1 + 2);\n    }\n\n    // handle a case where new vertex is on the edge of a triangle\n    _handleCollinear(pn, a) {\n        const a0 = a - a % 3;\n        const al = a0 + (a + 1) % 3;\n        const ar = a0 + (a + 2) % 3;\n        const p0 = this.triangles[ar];\n        const pr = this.triangles[a];\n        const pl = this.triangles[al];\n        const hal = this._halfedges[al];\n        const har = this._halfedges[ar];\n\n        const b = this._halfedges[a];\n\n        if (b < 0) {\n            const t0 = this._addTriangle(pn, p0, pr, -1, har, -1, a0);\n            const t1 = this._addTriangle(p0, pn, pl, t0, -1, hal);\n            this._legalize(t0 + 1);\n            this._legalize(t1 + 2);\n            return;\n        }\n\n        const b0 = b - b % 3;\n        const bl = b0 + (b + 2) % 3;\n        const br = b0 + (b + 1) % 3;\n        const p1 = this.triangles[bl];\n        const hbl = this._halfedges[bl];\n        const hbr = this._halfedges[br];\n\n        this._queueRemove(b0 / 3);\n\n        const t0 = this._addTriangle(p0, pr, pn, har, -1, -1, a0);\n        const t1 = this._addTriangle(pr, p1, pn, hbr, -1, t0 + 1, b0);\n        const t2 = this._addTriangle(p1, pl, pn, hbl, -1, t1 + 1);\n        const t3 = this._addTriangle(pl, p0, pn, hal, t0 + 2, t2 + 1);\n\n        this._legalize(t0);\n        this._legalize(t1);\n        this._legalize(t2);\n        this._legalize(t3);\n    }\n\n    // priority queue methods\n\n    _queuePush(t, error) {\n        const i = this._queue.length;\n        this._queueIndices[t] = i;\n        this._queue.push(t);\n        this._errors.push(error);\n        this._rmsdSum += error * error;\n        this._queueUp(i);\n    }\n\n    _queuePop() {\n        const n = this._queue.length - 1;\n        this._queueSwap(0, n);\n        this._queueDown(0, n);\n        return this._queuePopBack();\n    }\n\n    _queuePopBack() {\n        const t = this._queue.pop();\n        const e = this._errors.pop();\n        this._rmsdSum -= e * e;\n        this._queueIndices[t] = -1;\n        return t;\n    }\n\n    _queueRemove(t) {\n        const i = this._queueIndices[t];\n        if (i < 0) {\n            const it = this._pending.indexOf(t);\n            if (it !== -1) {\n                this._pending[it] = this._pending[--this._pendingLen];\n            } else {\n                throw new Error('Broken triangulation (something went wrong).');\n            }\n            return;\n        }\n        const n = this._queue.length - 1;\n        if (n !== i) {\n            this._queueSwap(i, n);\n            if (!this._queueDown(i, n)) {\n                this._queueUp(i);\n            }\n        }\n        this._queuePopBack();\n    }\n\n    _queueLess(i, j) {\n        return this._errors[i] > this._errors[j];\n    }\n\n    _queueSwap(i, j) {\n        const pi = this._queue[i];\n        const pj = this._queue[j];\n        this._queue[i] = pj;\n        this._queue[j] = pi;\n        this._queueIndices[pi] = j;\n        this._queueIndices[pj] = i;\n        const e = this._errors[i];\n        this._errors[i] = this._errors[j];\n        this._errors[j] = e;\n    }\n\n    _queueUp(j0) {\n        let j = j0;\n        while (true) {\n            const i = (j - 1) >> 1;\n            if (i === j || !this._queueLess(j, i)) {\n                break;\n            }\n            this._queueSwap(i, j);\n            j = i;\n        }\n    }\n\n    _queueDown(i0, n) {\n        let i = i0;\n        while (true) {\n            const j1 = 2 * i + 1;\n            if (j1 >= n || j1 < 0) {\n                break;\n            }\n            const j2 = j1 + 1;\n            let j = j1;\n            if (j2 < n && this._queueLess(j2, j1)) {\n                j = j2;\n            }\n            if (!this._queueLess(j, i)) {\n                break;\n            }\n            this._queueSwap(i, j);\n            i = j;\n        }\n        return i > i0;\n    }\n}\n\nfunction orient(ax, ay, bx, by, cx, cy) {\n    return (bx - cx) * (ay - cy) - (by - cy) * (ax - cx);\n}\n\nfunction inCircle(ax, ay, bx, by, cx, cy, px, py) {\n    const dx = ax - px;\n    const dy = ay - py;\n    const ex = bx - px;\n    const ey = by - py;\n    const fx = cx - px;\n    const fy = cy - py;\n\n    const ap = dx * dx + dy * dy;\n    const bp = ex * ex + ey * ey;\n    const cp = fx * fx + fy * fy;\n\n    return dx * (ey * cp - bp * fy) -\n           dy * (ex * cp - bp * fx) +\n           ap * (ex * fy - ey * fx) < 0;\n}\n"]}