Brunobkr/llama.cpp_AlgMor24_github

1(function (global, factory) {2typeof exports === 'object' && typeof module !== 'undefined' ? module.exports = factory() :3typeof define === 'function' && define.amd ? define(factory) :4(global = typeof globalThis !== 'undefined' ? globalThis : global || self, global.Delaunator = factory());5})(this, (function () { 'use strict';6 7const epsilon = 1.1102230246251565e-16;8const splitter = 134217729;9const resulterrbound = (3 + 8 * epsilon) * epsilon;10 11// fast_expansion_sum_zeroelim routine from oritinal code12function sum(elen, e, flen, f, h) {13    let Q, Qnew, hh, bvirt;14    let enow = e[0];15    let fnow = f[0];16    let eindex = 0;17    let findex = 0;18    if ((fnow > enow) === (fnow > -enow)) {19        Q = enow;20        enow = e[++eindex];21    } else {22        Q = fnow;23        fnow = f[++findex];24    }25    let hindex = 0;26    if (eindex < elen && findex < flen) {27        if ((fnow > enow) === (fnow > -enow)) {28            Qnew = enow + Q;29            hh = Q - (Qnew - enow);30            enow = e[++eindex];31        } else {32            Qnew = fnow + Q;33            hh = Q - (Qnew - fnow);34            fnow = f[++findex];35        }36        Q = Qnew;37        if (hh !== 0) {38            h[hindex++] = hh;39        }40        while (eindex < elen && findex < flen) {41            if ((fnow > enow) === (fnow > -enow)) {42                Qnew = Q + enow;43                bvirt = Qnew - Q;44                hh = Q - (Qnew - bvirt) + (enow - bvirt);45                enow = e[++eindex];46            } else {47                Qnew = Q + fnow;48                bvirt = Qnew - Q;49                hh = Q - (Qnew - bvirt) + (fnow - bvirt);50                fnow = f[++findex];51            }52            Q = Qnew;53            if (hh !== 0) {54                h[hindex++] = hh;55            }56        }57    }58    while (eindex < elen) {59        Qnew = Q + enow;60        bvirt = Qnew - Q;61        hh = Q - (Qnew - bvirt) + (enow - bvirt);62        enow = e[++eindex];63        Q = Qnew;64        if (hh !== 0) {65            h[hindex++] = hh;66        }67    }68    while (findex < flen) {69        Qnew = Q + fnow;70        bvirt = Qnew - Q;71        hh = Q - (Qnew - bvirt) + (fnow - bvirt);72        fnow = f[++findex];73        Q = Qnew;74        if (hh !== 0) {75            h[hindex++] = hh;76        }77    }78    if (Q !== 0 || hindex === 0) {79        h[hindex++] = Q;80    }81    return hindex;82}83 84function estimate(elen, e) {85    let Q = e[0];86    for (let i = 1; i < elen; i++) Q += e[i];87    return Q;88}89 90function vec(n) {91    return new Float64Array(n);92}93 94const ccwerrboundA = (3 + 16 * epsilon) * epsilon;95const ccwerrboundB = (2 + 12 * epsilon) * epsilon;96const ccwerrboundC = (9 + 64 * epsilon) * epsilon * epsilon;97 98const B = vec(4);99const C1 = vec(8);100const C2 = vec(12);101const D = vec(16);102const u = vec(4);103 104function orient2dadapt(ax, ay, bx, by, cx, cy, detsum) {105    let acxtail, acytail, bcxtail, bcytail;106    let bvirt, c, ahi, alo, bhi, blo, _i, _j, _0, s1, s0, t1, t0, u3;107 108    const acx = ax - cx;109    const bcx = bx - cx;110    const acy = ay - cy;111    const bcy = by - cy;112 113    s1 = acx * bcy;114    c = splitter * acx;115    ahi = c - (c - acx);116    alo = acx - ahi;117    c = splitter * bcy;118    bhi = c - (c - bcy);119    blo = bcy - bhi;120    s0 = alo * blo - (s1 - ahi * bhi - alo * bhi - ahi * blo);121    t1 = acy * bcx;122    c = splitter * acy;123    ahi = c - (c - acy);124    alo = acy - ahi;125    c = splitter * bcx;126    bhi = c - (c - bcx);127    blo = bcx - bhi;128    t0 = alo * blo - (t1 - ahi * bhi - alo * bhi - ahi * blo);129    _i = s0 - t0;130    bvirt = s0 - _i;131    B[0] = s0 - (_i + bvirt) + (bvirt - t0);132    _j = s1 + _i;133    bvirt = _j - s1;134    _0 = s1 - (_j - bvirt) + (_i - bvirt);135    _i = _0 - t1;136    bvirt = _0 - _i;137    B[1] = _0 - (_i + bvirt) + (bvirt - t1);138    u3 = _j + _i;139    bvirt = u3 - _j;140    B[2] = _j - (u3 - bvirt) + (_i - bvirt);141    B[3] = u3;142 143    let det = estimate(4, B);144    let errbound = ccwerrboundB * detsum;145    if (det >= errbound || -det >= errbound) {146        return det;147    }148 149    bvirt = ax - acx;150    acxtail = ax - (acx + bvirt) + (bvirt - cx);151    bvirt = bx - bcx;152    bcxtail = bx - (bcx + bvirt) + (bvirt - cx);153    bvirt = ay - acy;154    acytail = ay - (acy + bvirt) + (bvirt - cy);155    bvirt = by - bcy;156    bcytail = by - (bcy + bvirt) + (bvirt - cy);157 158    if (acxtail === 0 && acytail === 0 && bcxtail === 0 && bcytail === 0) {159        return det;160    }161 162    errbound = ccwerrboundC * detsum + resulterrbound * Math.abs(det);163    det += (acx * bcytail + bcy * acxtail) - (acy * bcxtail + bcx * acytail);164    if (det >= errbound || -det >= errbound) return det;165 166    s1 = acxtail * bcy;167    c = splitter * acxtail;168    ahi = c - (c - acxtail);169    alo = acxtail - ahi;170    c = splitter * bcy;171    bhi = c - (c - bcy);172    blo = bcy - bhi;173    s0 = alo * blo - (s1 - ahi * bhi - alo * bhi - ahi * blo);174    t1 = acytail * bcx;175    c = splitter * acytail;176    ahi = c - (c - acytail);177    alo = acytail - ahi;178    c = splitter * bcx;179    bhi = c - (c - bcx);180    blo = bcx - bhi;181    t0 = alo * blo - (t1 - ahi * bhi - alo * bhi - ahi * blo);182    _i = s0 - t0;183    bvirt = s0 - _i;184    u[0] = s0 - (_i + bvirt) + (bvirt - t0);185    _j = s1 + _i;186    bvirt = _j - s1;187    _0 = s1 - (_j - bvirt) + (_i - bvirt);188    _i = _0 - t1;189    bvirt = _0 - _i;190    u[1] = _0 - (_i + bvirt) + (bvirt - t1);191    u3 = _j + _i;192    bvirt = u3 - _j;193    u[2] = _j - (u3 - bvirt) + (_i - bvirt);194    u[3] = u3;195    const C1len = sum(4, B, 4, u, C1);196 197    s1 = acx * bcytail;198    c = splitter * acx;199    ahi = c - (c - acx);200    alo = acx - ahi;201    c = splitter * bcytail;202    bhi = c - (c - bcytail);203    blo = bcytail - bhi;204    s0 = alo * blo - (s1 - ahi * bhi - alo * bhi - ahi * blo);205    t1 = acy * bcxtail;206    c = splitter * acy;207    ahi = c - (c - acy);208    alo = acy - ahi;209    c = splitter * bcxtail;210    bhi = c - (c - bcxtail);211    blo = bcxtail - bhi;212    t0 = alo * blo - (t1 - ahi * bhi - alo * bhi - ahi * blo);213    _i = s0 - t0;214    bvirt = s0 - _i;215    u[0] = s0 - (_i + bvirt) + (bvirt - t0);216    _j = s1 + _i;217    bvirt = _j - s1;218    _0 = s1 - (_j - bvirt) + (_i - bvirt);219    _i = _0 - t1;220    bvirt = _0 - _i;221    u[1] = _0 - (_i + bvirt) + (bvirt - t1);222    u3 = _j + _i;223    bvirt = u3 - _j;224    u[2] = _j - (u3 - bvirt) + (_i - bvirt);225    u[3] = u3;226    const C2len = sum(C1len, C1, 4, u, C2);227 228    s1 = acxtail * bcytail;229    c = splitter * acxtail;230    ahi = c - (c - acxtail);231    alo = acxtail - ahi;232    c = splitter * bcytail;233    bhi = c - (c - bcytail);234    blo = bcytail - bhi;235    s0 = alo * blo - (s1 - ahi * bhi - alo * bhi - ahi * blo);236    t1 = acytail * bcxtail;237    c = splitter * acytail;238    ahi = c - (c - acytail);239    alo = acytail - ahi;240    c = splitter * bcxtail;241    bhi = c - (c - bcxtail);242    blo = bcxtail - bhi;243    t0 = alo * blo - (t1 - ahi * bhi - alo * bhi - ahi * blo);244    _i = s0 - t0;245    bvirt = s0 - _i;246    u[0] = s0 - (_i + bvirt) + (bvirt - t0);247    _j = s1 + _i;248    bvirt = _j - s1;249    _0 = s1 - (_j - bvirt) + (_i - bvirt);250    _i = _0 - t1;251    bvirt = _0 - _i;252    u[1] = _0 - (_i + bvirt) + (bvirt - t1);253    u3 = _j + _i;254    bvirt = u3 - _j;255    u[2] = _j - (u3 - bvirt) + (_i - bvirt);256    u[3] = u3;257    const Dlen = sum(C2len, C2, 4, u, D);258 259    return D[Dlen - 1];260}261 262function orient2d(ax, ay, bx, by, cx, cy) {263    const detleft = (ay - cy) * (bx - cx);264    const detright = (ax - cx) * (by - cy);265    const det = detleft - detright;266 267    const detsum = Math.abs(detleft + detright);268    if (Math.abs(det) >= ccwerrboundA * detsum) return det;269 270    return -orient2dadapt(ax, ay, bx, by, cx, cy, detsum);271}272 273const EPSILON = Math.pow(2, -52);274const EDGE_STACK = new Uint32Array(512);275 276/** @template {ArrayLike<number>} T */277class Delaunator {278 279    /**280     * Constructs a delaunay triangulation object given an array of points (`[x, y]` by default).281     * `getX` and `getY` are optional functions of the form `(point) => value` for custom point formats.282     *283     * @template P284     * @param {P[]} points285     * @param {(p: P) => number} [getX]286     * @param {(p: P) => number} [getY]287     */288    // @ts-expect-error TS2322289    static from(points, getX = defaultGetX, getY = defaultGetY) {290        const n = points.length;291        const coords = new Float64Array(n * 2);292 293        for (let i = 0; i < n; i++) {294            const p = points[i];295            coords[2 * i] = getX(p);296            coords[2 * i + 1] = getY(p);297        }298 299        return new Delaunator(coords);300    }301 302    /**303     * Constructs a delaunay triangulation object given an array of point coordinates of the form:304     * `[x0, y0, x1, y1, ...]` (use a typed array for best performance). Duplicate points are skipped.305     *306     * @param {T} coords307     */308    constructor(coords) {309        const n = coords.length >> 1;310        if (n > 0 && typeof coords[0] !== 'number') throw new Error('Expected coords to contain numbers.');311 312        this.coords = coords;313 314        // arrays that will store the triangulation graph315        const maxTriangles = Math.max(2 * n - 5, 0);316        /** @private */ this._triangles = new Uint32Array(maxTriangles * 3);317        /** @private */ this._halfedges = new Int32Array(maxTriangles * 3);318 319        // temporary arrays for tracking the edges of the advancing convex hull320        /** @private */ this._hashSize = Math.ceil(Math.sqrt(n));321        /** @private */ this._hullPrev = new Uint32Array(n); // edge to prev edge322        /** @private */ this._hullNext = new Uint32Array(n); // edge to next edge323        /** @private */ this._hullTri = new Uint32Array(n); // edge to adjacent triangle324        /** @private */ this._hullHash = new Int32Array(this._hashSize); // angular edge hash325 326        // temporary arrays for sorting points327        /** @private */ this._ids = new Uint32Array(n);328        /** @private */ this._dists = new Float64Array(n);329 330        /** @private */ this.trianglesLen = 0;331        /** @private */ this._cx = 0;332        /** @private */ this._cy = 0;333        /** @private */ this._hullStart = 0;334 335 336        /** A `Uint32Array` array of indices that reference points on the convex hull of the input data, counter-clockwise. */337        this.hull = this._triangles;338        /** A `Uint32Array` array of triangle vertex indices (each group of three numbers forms a triangle). All triangles are directed counterclockwise. */339        this.triangles = this._triangles;340        /**341         * A `Int32Array` array of triangle half-edge indices that allows you to traverse the triangulation.342         * `i`-th half-edge in the array corresponds to vertex `triangles[i]` the half-edge is coming from.343         * `halfedges[i]` is the index of a twin half-edge in an adjacent triangle (or `-1` for outer half-edges on the convex hull).344         */345        this.halfedges = this._halfedges;346 347        this.update();348    }349 350    /**351     * Updates the triangulation if you modified `delaunay.coords` values in place, avoiding expensive memory allocations.352     * Useful for iterative relaxation algorithms such as Lloyd's.353     */354    update() {355        const {coords, _hullPrev: hullPrev, _hullNext: hullNext, _hullTri: hullTri, _hullHash: hullHash} =  this;356        const n = coords.length >> 1;357 358        // populate an array of point indices; calculate input data bbox359        let minX = Infinity;360        let minY = Infinity;361        let maxX = -Infinity;362        let maxY = -Infinity;363 364        for (let i = 0; i < n; i++) {365            const x = coords[2 * i];366            const y = coords[2 * i + 1];367            if (x < minX) minX = x;368            if (y < minY) minY = y;369            if (x > maxX) maxX = x;370            if (y > maxY) maxY = y;371            this._ids[i] = i;372        }373        const cx = (minX + maxX) / 2;374        const cy = (minY + maxY) / 2;375 376        let i0 = 0, i1 = 0, i2 = 0;377 378        // pick a seed point close to the center379        for (let i = 0, minDist = Infinity; i < n; i++) {380            const d = dist(cx, cy, coords[2 * i], coords[2 * i + 1]);381            if (d < minDist) {382                i0 = i;383                minDist = d;384            }385        }386        const i0x = coords[2 * i0];387        const i0y = coords[2 * i0 + 1];388 389        // find the point closest to the seed390        for (let i = 0, minDist = Infinity; i < n; i++) {391            if (i === i0) continue;392            const d = dist(i0x, i0y, coords[2 * i], coords[2 * i + 1]);393            if (d < minDist && d > 0) {394                i1 = i;395                minDist = d;396            }397        }398        let i1x = coords[2 * i1];399        let i1y = coords[2 * i1 + 1];400 401        let minRadius = Infinity;402 403        // find the third point which forms the smallest circumcircle with the first two404        for (let i = 0; i < n; i++) {405            if (i === i0 || i === i1) continue;406            const r = circumradius(i0x, i0y, i1x, i1y, coords[2 * i], coords[2 * i + 1]);407            if (r < minRadius) {408                i2 = i;409                minRadius = r;410            }411        }412        let i2x = coords[2 * i2];413        let i2y = coords[2 * i2 + 1];414 415        if (minRadius === Infinity) {416            // order collinear points by dx (or dy if all x are identical)417            // and return the list as a hull418            for (let i = 0; i < n; i++) {419                this._dists[i] = (coords[2 * i] - coords[0]) || (coords[2 * i + 1] - coords[1]);420            }421            quicksort(this._ids, this._dists, 0, n - 1);422            const hull = new Uint32Array(n);423            let j = 0;424            for (let i = 0, d0 = -Infinity; i < n; i++) {425                const id = this._ids[i];426                const d = this._dists[id];427                if (d > d0) {428                    hull[j++] = id;429                    d0 = d;430                }431            }432            this.hull = hull.subarray(0, j);433            this.triangles = new Uint32Array(0);434            this.halfedges = new Int32Array(0);435            return;436        }437 438        // swap the order of the seed points for counter-clockwise orientation439        if (orient2d(i0x, i0y, i1x, i1y, i2x, i2y) < 0) {440            const i = i1;441            const x = i1x;442            const y = i1y;443            i1 = i2;444            i1x = i2x;445            i1y = i2y;446            i2 = i;447            i2x = x;448            i2y = y;449        }450 451        const center = circumcenter(i0x, i0y, i1x, i1y, i2x, i2y);452        this._cx = center.x;453        this._cy = center.y;454 455        for (let i = 0; i < n; i++) {456            this._dists[i] = dist(coords[2 * i], coords[2 * i + 1], center.x, center.y);457        }458 459        // sort the points by distance from the seed triangle circumcenter460        quicksort(this._ids, this._dists, 0, n - 1);461 462        // set up the seed triangle as the starting hull463        this._hullStart = i0;464        let hullSize = 3;465 466        hullNext[i0] = hullPrev[i2] = i1;467        hullNext[i1] = hullPrev[i0] = i2;468        hullNext[i2] = hullPrev[i1] = i0;469 470        hullTri[i0] = 0;471        hullTri[i1] = 1;472        hullTri[i2] = 2;473 474        hullHash.fill(-1);475        hullHash[this._hashKey(i0x, i0y)] = i0;476        hullHash[this._hashKey(i1x, i1y)] = i1;477        hullHash[this._hashKey(i2x, i2y)] = i2;478 479        this.trianglesLen = 0;480        this._addTriangle(i0, i1, i2, -1, -1, -1);481 482        for (let k = 0, xp = 0, yp = 0; k < this._ids.length; k++) {483            const i = this._ids[k];484            const x = coords[2 * i];485            const y = coords[2 * i + 1];486 487            // skip near-duplicate points488            if (k > 0 && Math.abs(x - xp) <= EPSILON && Math.abs(y - yp) <= EPSILON) continue;489            xp = x;490            yp = y;491 492            // skip seed triangle points493            if (i === i0 || i === i1 || i === i2) continue;494 495            // find a visible edge on the convex hull using edge hash496            let start = 0;497            for (let j = 0, key = this._hashKey(x, y); j < this._hashSize; j++) {498                start = hullHash[(key + j) % this._hashSize];499                if (start !== -1 && start !== hullNext[start]) break;500            }501 502            start = hullPrev[start];503            let e = start, q;504            while (q = hullNext[e], orient2d(x, y, coords[2 * e], coords[2 * e + 1], coords[2 * q], coords[2 * q + 1]) >= 0) {505                e = q;506                if (e === start) {507                    e = -1;508                    break;509                }510            }511            if (e === -1) continue; // likely a near-duplicate point; skip it512 513            // add the first triangle from the point514            let t = this._addTriangle(e, i, hullNext[e], -1, -1, hullTri[e]);515 516            // recursively flip triangles from the point until they satisfy the Delaunay condition517            hullTri[i] = this._legalize(t + 2);518            hullTri[e] = t; // keep track of boundary triangles on the hull519            hullSize++;520 521            // walk forward through the hull, adding more triangles and flipping recursively522            let n = hullNext[e];523            while (q = hullNext[n], orient2d(x, y, coords[2 * n], coords[2 * n + 1], coords[2 * q], coords[2 * q + 1]) < 0) {524                t = this._addTriangle(n, i, q, hullTri[i], -1, hullTri[n]);525                hullTri[i] = this._legalize(t + 2);526                hullNext[n] = n; // mark as removed527                hullSize--;528                n = q;529            }530 531            // walk backward from the other side, adding more triangles and flipping532            if (e === start) {533                while (q = hullPrev[e], orient2d(x, y, coords[2 * q], coords[2 * q + 1], coords[2 * e], coords[2 * e + 1]) < 0) {534                    t = this._addTriangle(q, i, e, -1, hullTri[e], hullTri[q]);535                    this._legalize(t + 2);536                    hullTri[q] = t;537                    hullNext[e] = e; // mark as removed538                    hullSize--;539                    e = q;540                }541            }542 543            // update the hull indices544            this._hullStart = hullPrev[i] = e;545            hullNext[e] = hullPrev[n] = i;546            hullNext[i] = n;547 548            // save the two new edges in the hash table549            hullHash[this._hashKey(x, y)] = i;550            hullHash[this._hashKey(coords[2 * e], coords[2 * e + 1])] = e;551        }552 553        this.hull = new Uint32Array(hullSize);554        for (let i = 0, e = this._hullStart; i < hullSize; i++) {555            this.hull[i] = e;556            e = hullNext[e];557        }558 559        // trim typed triangle mesh arrays560        this.triangles = this._triangles.subarray(0, this.trianglesLen);561        this.halfedges = this._halfedges.subarray(0, this.trianglesLen);562    }563 564    /**565     * Calculate an angle-based key for the edge hash used for advancing convex hull.566     *567     * @param {number} x568     * @param {number} y569     * @private570     */571    _hashKey(x, y) {572        return Math.floor(pseudoAngle(x - this._cx, y - this._cy) * this._hashSize) % this._hashSize;573    }574 575    /**576     * Flip an edge in a pair of triangles if it doesn't satisfy the Delaunay condition.577     *578     * @param {number} a579     * @private580     */581    _legalize(a) {582        const {_triangles: triangles, _halfedges: halfedges, coords} = this;583 584        let i = 0;585        let ar = 0;586 587        // recursion eliminated with a fixed-size stack588        while (true) {589            const b = halfedges[a];590 591            /* if the pair of triangles doesn't satisfy the Delaunay condition592             * (p1 is inside the circumcircle of [p0, pl, pr]), flip them,593             * then do the same check/flip recursively for the new pair of triangles594             *595             *           pl                    pl596             *          /||\                  /  \597             *       al/ || \bl            al/    \a598             *        /  ||  \              /      \599             *       /  a||b  \    flip    /___ar___\600             *     p0\   ||   /p1   =>   p0\---bl---/p1601             *        \  ||  /              \      /602             *       ar\ || /br             b\    /br603             *          \||/                  \  /604             *           pr                    pr605             */606            const a0 = a - a % 3;607            ar = a0 + (a + 2) % 3;608 609            if (b === -1) { // convex hull edge610                if (i === 0) break;611                a = EDGE_STACK[--i];612                continue;613            }614 615            const b0 = b - b % 3;616            const al = a0 + (a + 1) % 3;617            const bl = b0 + (b + 2) % 3;618 619            const p0 = triangles[ar];620            const pr = triangles[a];621            const pl = triangles[al];622            const p1 = triangles[bl];623 624            const illegal = inCircle(625                coords[2 * p0], coords[2 * p0 + 1],626                coords[2 * pr], coords[2 * pr + 1],627                coords[2 * pl], coords[2 * pl + 1],628                coords[2 * p1], coords[2 * p1 + 1]);629 630            if (illegal) {631                triangles[a] = p1;632                triangles[b] = p0;633 634                const hbl = halfedges[bl];635 636                // edge swapped on the other side of the hull (rare); fix the half-edge reference637                if (hbl === -1) {638                    let e = this._hullStart;639                    do {640                        if (this._hullTri[e] === bl) {641                            this._hullTri[e] = a;642                            break;643                        }644                        e = this._hullPrev[e];645                    } while (e !== this._hullStart);646                }647                this._link(a, hbl);648                this._link(b, halfedges[ar]);649                this._link(ar, bl);650 651                const br = b0 + (b + 1) % 3;652 653                // don't worry about hitting the cap: it can only happen on extremely degenerate input654                if (i < EDGE_STACK.length) {655                    EDGE_STACK[i++] = br;656                }657            } else {658                if (i === 0) break;659                a = EDGE_STACK[--i];660            }661        }662 663        return ar;664    }665 666    /**667     * Link two half-edges to each other.668     * @param {number} a669     * @param {number} b670     * @private671     */672    _link(a, b) {673        this._halfedges[a] = b;674        if (b !== -1) this._halfedges[b] = a;675    }676 677    /**678     * Add a new triangle given vertex indices and adjacent half-edge ids.679     *680     * @param {number} i0681     * @param {number} i1682     * @param {number} i2683     * @param {number} a684     * @param {number} b685     * @param {number} c686     * @private687     */688    _addTriangle(i0, i1, i2, a, b, c) {689        const t = this.trianglesLen;690 691        this._triangles[t] = i0;692        this._triangles[t + 1] = i1;693        this._triangles[t + 2] = i2;694 695        this._link(t, a);696        this._link(t + 1, b);697        this._link(t + 2, c);698 699        this.trianglesLen += 3;700 701        return t;702    }703}704 705/**706 * Monotonically increases with real angle, but doesn't need expensive trigonometry.707 *708 * @param {number} dx709 * @param {number} dy710 */711function pseudoAngle(dx, dy) {712    const p = dx / (Math.abs(dx) + Math.abs(dy));713    return (dy > 0 ? 3 - p : 1 + p) / 4; // [0..1]714}715 716/**717 * Squared distance between two points.718 *719 * @param {number} ax720 * @param {number} ay721 * @param {number} bx722 * @param {number} by723 */724function dist(ax, ay, bx, by) {725    const dx = ax - bx;726    const dy = ay - by;727    return dx * dx + dy * dy;728}729 730/**731 * Check whether point P is inside a circle formed by points A, B, C.732 *733 * @param {number} ax734 * @param {number} ay735 * @param {number} bx736 * @param {number} by737 * @param {number} cx738 * @param {number} cy739 * @param {number} px740 * @param {number} py741 */742function inCircle(ax, ay, bx, by, cx, cy, px, py) {743    const dx = ax - px;744    const dy = ay - py;745    const ex = bx - px;746    const ey = by - py;747    const fx = cx - px;748    const fy = cy - py;749 750    const ap = dx * dx + dy * dy;751    const bp = ex * ex + ey * ey;752    const cp = fx * fx + fy * fy;753 754    return dx * (ey * cp - bp * fy) -755           dy * (ex * cp - bp * fx) +756           ap * (ex * fy - ey * fx) < 0;757}758 759/**760 * Squared radius of the circle formed by points A, B, C.761 *762 * @param {number} ax763 * @param {number} ay764 * @param {number} bx765 * @param {number} by766 * @param {number} cx767 * @param {number} cy768 */769function circumradius(ax, ay, bx, by, cx, cy) {770    const dx = bx - ax;771    const dy = by - ay;772    const ex = cx - ax;773    const ey = cy - ay;774 775    const bl = dx * dx + dy * dy;776    const cl = ex * ex + ey * ey;777    const d = 0.5 / (dx * ey - dy * ex);778 779    const x = (ey * bl - dy * cl) * d;780    const y = (dx * cl - ex * bl) * d;781 782    return x * x + y * y;783}784 785/**786 * Get coordinates of a circumcenter for points A, B, C.787 *788 * @param {number} ax789 * @param {number} ay790 * @param {number} bx791 * @param {number} by792 * @param {number} cx793 * @param {number} cy794 */795function circumcenter(ax, ay, bx, by, cx, cy) {796    const dx = bx - ax;797    const dy = by - ay;798    const ex = cx - ax;799    const ey = cy - ay;800 801    const bl = dx * dx + dy * dy;802    const cl = ex * ex + ey * ey;803    const d = 0.5 / (dx * ey - dy * ex);804 805    const x = ax + (ey * bl - dy * cl) * d;806    const y = ay + (dx * cl - ex * bl) * d;807 808    return {x, y};809}810 811/**812 * Sort points by distance via an array of point indices and an array of calculated distances.813 *814 * @param {Uint32Array} ids815 * @param {Float64Array} dists816 * @param {number} left817 * @param {number} right818 */819function quicksort(ids, dists, left, right) {820    if (right - left <= 20) {821        for (let i = left + 1; i <= right; i++) {822            const temp = ids[i];823            const tempDist = dists[temp];824            let j = i - 1;825            while (j >= left && dists[ids[j]] > tempDist) ids[j + 1] = ids[j--];826            ids[j + 1] = temp;827        }828    } else {829        const median = (left + right) >> 1;830        let i = left + 1;831        let j = right;832        swap(ids, median, i);833        if (dists[ids[left]] > dists[ids[right]]) swap(ids, left, right);834        if (dists[ids[i]] > dists[ids[right]]) swap(ids, i, right);835        if (dists[ids[left]] > dists[ids[i]]) swap(ids, left, i);836 837        const temp = ids[i];838        const tempDist = dists[temp];839        while (true) {840            do i++; while (dists[ids[i]] < tempDist);841            do j--; while (dists[ids[j]] > tempDist);842            if (j < i) break;843            swap(ids, i, j);844        }845        ids[left + 1] = ids[j];846        ids[j] = temp;847 848        if (right - i + 1 >= j - left) {849            quicksort(ids, dists, i, right);850            quicksort(ids, dists, left, j - 1);851        } else {852            quicksort(ids, dists, left, j - 1);853            quicksort(ids, dists, i, right);854        }855    }856}857 858/**859 * @param {Uint32Array} arr860 * @param {number} i861 * @param {number} j862 */863function swap(arr, i, j) {864    const tmp = arr[i];865    arr[i] = arr[j];866    arr[j] = tmp;867}868 869/** @param {[number, number]} p */870function defaultGetX(p) {871    return p[0];872}873/** @param {[number, number]} p */874function defaultGetY(p) {875    return p[1];876}877 878return Delaunator;879 880}));881