dual-mesh

Dual mesh library for my polygon map generator projects (mapgen2, mapgen4). Feel free to use this, but it’s not a stable library and I do make breaking changes. The create.js interface is the most likely to change in the future.

This is a wrapper around Delaunator. I wrote the Delaunator Guide based on the code from this project. The code in the guide is easier to read and more general but less efficient than the code in this library.

Documentation is here, but it’s a bit rough. See my blog post about centroid polygons and my blog post about the dual mesh data structure for the history. Those blog posts used the names “seeds, edges, triangles” but now I call them “regions, sides, triangles”, and I use “ghost” elements to eliminate the boundaries.

The naming convention is output-from-input: x_name_y takes type y (r, s, t) as input and produces type x (r, s, t) as output. For example, r_begin_s is a function that takes a side (s) as input and returns a region (r), and could be called r = mesh.r_begin_s(s). A previous version of this library used the opposite naming convention, input-to-output, but the author was persuaded to switch by Tom Forsyth’s article on naming.

For efficiency, functions that return an array take an optional parameter where the result should be written:

let out_r = [];
mesh.r_around_t(t, out_r);
// output written into out_r

For convenience, they also return the array, so this allocates a new array and returns it:

let out_r = mesh.r_around_t(t);

To create a mesh, use the MeshBuilder:

let mesh = new MeshBuilder()
    .addPoints(array_of_points)
    .create();

let Poisson = require('poisson-disk-sampling');
let mesh = new MeshBuilder({boundarySpacing: 75})
    .addPoisson(Poisson, 75)
    .create();

Built with

• delaunator to build the Delaunay triangulation
• poisson-disk-sampling to choose evenly spaced points