Generator for Voronoi cell neighbors for d3-delaunay

gistfile1.txt

// Modification of delaunay.neighbors to find Voronoi cell neighbors
// This generator should be attached to delaunay.voronoi

*neighbors(i) {
        const {delaunay: {inedges, hull, _hullIndex, halfedges, triangles, collinear = undefined}} = this;

        // degenerate case with several collinear points
        if (collinear) {
            const l = collinear.indexOf(i);
            if (l > 0) yield collinear[l - 1];
            if (l < collinear.length - 1) yield collinear[l + 1];
            return;
        }

        const potentialNeighbors = [];
        const e0 = inedges[i];
        if (e0 === -1) return; // coincident point
        let e = e0, p0 = -1;
        let internal = hull[_hullIndex[i]] === -1;
        do {
            p0 = triangles[e]; // yield p0 = triangles[e];
            potentialNeighbors.push(p0);
            internal = internal && hull[_hullIndex[p0]] === -1;
            e = e % 3 === 2 ? e - 2 : e + 1;
            if (triangles[e] !== i) break; // bad triangulation
            e = halfedges[e];
            if (e === -1) {
                internal = false;
                const p = hull[(_hullIndex[i] + 1) % hull.length];
                if (p !== p0) potentialNeighbors.push(p); // yield p;
                break;
            }
        } while (e !== e0);

        // if all points were internal (not on the convex hull) then
        // no further processing is necessary
        if (internal) {
            for (let p of potentialNeighbors) yield p;
            return;
        }

        // a point is a neighbor if its cell polygon has at least two points
        // in common with the selected cell polygon
        const home = this.cellPolygon(i);
        const K = home.length - 1;
        for (let p of potentialNeighbors) {
            const neighbor = this.cellPolygon(p);
            const L = neighbor.length - 1;
            let common = 0;
            for (let k = 0; k < K; k++) {
                const a = home[k];
                for (let l = 0; l < L; l++) {
                    const b = neighbor[l];
                    if (a[0] === b[0] && a[1] === b[1]) { // Not sure why I previously also checked a[1] === b[0] etc.
                        common++;
                        break;
                    }
                }
                if (common > 1) break;
            }
            if (common > 1) yield p;
        }
    }