Request: a mutable variant with an update method, for Voronoi relaxation purposes

[JobLeonard]

Lloyd's Algorithm works by repeatedly moving generators of a Voronoi diagram to their center of mass and re-computing the diagram.

This is is used in many contexts, but a fun one is Secord's stippling algorithm - Mike Bostock has a notebook here.

This requires creating a new diagram from scratch each time. So far so good. However, that also comes with allocating nine typed arrays each iteration:

    constructor(coords) {
        const n = coords.length >> 1;

        /* ... */

        const maxTriangles = 2 * n - 5;
        const triangles = this.triangles = new Uint32Array(maxTriangles * 3);
        const halfedges = this.halfedges = new Int32Array(maxTriangles * 3);

        this._hashSize = Math.ceil(Math.sqrt(n));
        const hullPrev = this.hullPrev = new Uint32Array(n); // edge to prev edge
        const hullNext = this.hullNext = new Uint32Array(n); // edge to next edge
        const hullTri = this.hullTri = new Uint32Array(n); // edge to adjacent triangle
        const hullHash = new Int32Array(this._hashSize).fill(-1); // angular edge hash

        // populate an array of point indices; calculate input data bbox
        const ids = new Uint32Array(n);

        /* ... */

        const dists = new Float64Array(n);

        /* ... */

        this.hull = new Uint32Array(hullSize);
        /* ... */
    }

Now, the this.hull one is pretty small, so let's just pretend it compensates for the -5 in the maxTriangles calculation. Then for n points, we allocate the equivalent of Uint32Array(10*n) + Int32Array(6*n + Math.sqrt(n)) + Float64Array(n). For a single allocation this is not a big deal, but I want to hook up that Voronoi stippling algorithm to my webcam. At 60FPS, you start to notice this!

And when using Lloyd's Algorithm the number of coordinates remains the same anyway, so it would make a lot more sense to just re-use those arrays.

A hypothetical update() function would be almost identical to the currentt contructor, except it would have to check if the new coords is the same length as the old one, and then it would reset all typed arrays with TypedArray.prototype.fill(0).

Perhaps there is a preference for Delaunator to remain immutable. Well, then one could make a MutableDelaunator class, no?

[mourner]

That's a reasonable request — I'll look into it.

[JobLeonard]

I looked at the source-code for d3-delaunay, which is used in that notebook. The code wrapping Delaunator also does this superfluous allocatoin to some extent. Maybe it makes more sense for me to take the source code of both, manually inline, and then add the update function?

[JobLeonard]

Would this work?

https://gist.github.com/JobLeonard/b5dccf0ebacc06f30baf20029f206fb5

[mourner]

@JobLeonard ideally we would want to make this work while avoiding code duplication, while making sure we're not breaking the public API — it's tricky, but it's definitely possible. I had a stab at this some months ago but didn't finish — might need to revisit some time soon.

[JobLeonard]

Can't we just split out the main code into another method that is called from both the constructor and the update function?

[JobLeonard]

I suppose one question is that we don't want to cache the arrays by default. How about not doing so until update is called at least once?

[JobLeonard]

The last approach could be done like this:

• modify update to work just like the constructor does now, except that arrays are cached
• at the start of the update method, if the cached arrays are null or too small for the number of points, (re)allocate them. Otherwise reuse previous arrays
• modify constructor to just call this.update(coords), then set all caches to null to release memory

Does that sound like an elegant solution?

[mourner]

PR here: #48