math/Voronoi.js

import { point } from "./Utils.js";
import { Delaunay } from "d3-delaunay";

/**
 * Voronoi wrapper around d3-delaunay
 * @see https://github.com/d3/d3-delaunay
 */
class Voronoi {

    /**
     * @param {Array} vertices array of points
     * @param {Number} w 
     * @param {Number} h 
     */
    constructor(vertices, w, h) {
        this.w = w;
        this.h = h;

        this.delaunay = Delaunay.from(vertices.map(point));
        this.update();
    }

    /**
     * get the vertices
     * @readonly
     */
    get vertices() {
        let points = this.delaunay.points;
        let vertices = [];

        for (let i = 0, n = points.length / 2; i < n; ++i) {
            vertices.push([
                points[2 * i],
                points[2 * i + 1]
            ])
        }

        return vertices
    }

    update() {
        this.voronoi = this.delaunay.voronoi([0, 0, this.w, this.h]);

        this.polygons = [];
        for (const p of this.voronoi.cellPolygons()) {
            this.polygons.push([...p]);
        }
    }

    /**
     * Perform a Lloyd relaxation
     * @param {Number} iterations
     * @see https://en.wikipedia.org/wiki/Lloyd%27s_algorithm
     */
    relax(iterations = 5) {
        for (let index = 0; index < iterations; index++) {
            this.polygons.forEach((polygon, i) => {
                let sumX = 0;
                let sumY = 0;
                let c = 0;

                for (const point of polygon) {
                    sumX += point[0];
                    sumY += point[1];
                    c++;
                }

                this.delaunay.points[i * 2] = sumX / c;
                this.delaunay.points[i * 2 + 1] = sumY / c;
            });

            this.delaunay.update();
            this.update();
        }
    }
}

export default Voronoi