Porting d3-voronoi to d3-delunay

Question

What I want to do is replicate a data-structure produced by processing the output from d3-voronoi, but by using d3-delaunay instead.

The data-structure in question is the one produced by this makeMesh function:

function makeMesh(pts, extent) {
      extent = extent || defaultExtent;
      var vor = voronoi(pts, extent);
      var vxs = [];
      var vxids = {};
      var adj = [];
      var edges = [];
      var tris = [];
      for (var i = 0; i < vor.edges.length; i++) {
          var e = vor.edges[i];
          if (e == undefined) continue;
          var e0 = vxids[e[0]];
          var e1 = vxids[e[1]];
          if (e0 == undefined) {
              e0 = vxs.length;
              vxids[e[0]] = e0;
              vxs.push(e[0]);
          }
          if (e1 == undefined) {
              e1 = vxs.length;
              vxids[e[1]] = e1;
              vxs.push(e[1]);
          }
          adj[e0] = adj[e0] || [];
          adj[e0].push(e1);
          adj[e1] = adj[e1] || [];
          adj[e1].push(e0);
          edges.push([e0, e1, e.left, e.right]);
          tris[e0] = tris[e0] || [];
          if (!tris[e0].includes(e.left)) tris[e0].push(e.left);
          if (e.right && !tris[e0].includes(e.right)) tris[e0].push(e.right);
          tris[e1] = tris[e1] || [];
          if (!tris[e1].includes(e.left)) tris[e1].push(e.left);
          if (e.right && !tris[e1].includes(e.right)) tris[e1].push(e.right);
      }

      var mesh = {
          pts: pts,
          vxs: vxs,
          adj: adj,
          tris: tris,
          edges: edges,
          extent: extent
      }
      mesh.map = function (f) {
          var mapped = vxs.map(f);
          mapped.mesh = mesh;
          return mapped;
      }
      return mesh;
  }

I've been trying to solve this for a while now and have finally made some progress here on observablehq:

https://observablehq.com/@folcon/original-code-by-martin-oleary-mewo2

I'm assessing how well it works by comparing the rendered images:

I want to produce these smooth colour transitions, which requires a correct mapping between vertices, heightmap and triangles.

Attempt 1:

Well I got something rendered, if my approach below doesn't work, it might be instructive to come back to this.

Attempt 2:

This one I feel is a lot better, I don't appear to be getting extra triangles (no black ones visible), but the issue appears to be I'm rendering in the wrong order. I was attempting to go from the leftmost point and then walk around the cell edges, this seems like the right idea, but the ordering is wrong...

I've dug into the delunator's guide to datastructures and at this point I feel like I'm pretty close, but missing something obvious.

Useful Notes / Assumptions:

The mesh uses the edges of the cells, not the triangles for "edges", if you look at the adj (adjacencies) it's never higher than 3, which is in keeping with using the cells as each vertex of the cell has no more than 3 neighbours.

Given that an edge is an edge of a cell, the left and the right of the edge should therefore be the two cells that edge sits on.

Hopefully that's clear.

To answer @thclark:

The Output Data Structure:

{
  pts: pts,
  vxs: vxs,
  adj: adj,
  tris: tris,
  edges: edges,
  extent: extent
}

pts is the original points array, which is a list of pairs of [x, y] coordinates. vxs is the vertices of the cell as pairs of [x, y] coordinates. The points here are unique, and their index in the array is the authoritative id for that vertex.

I will use one of redblobgame's images to clarify:

The red dots in this image are the original points, the blue one's are the vertices of the cell.

edges is are comprised of 4 values, the first two are the indexes of the vertices that make up the edges of a cell, which in the image above are in white. The second two are the circumcenter's corresponding left and right cells which I've illustrated in an image above, but hopefully this will be clearer:

adj is a mapping from a vertex index to the other vertex index's which are connected to it, because we're using the cells, no entry in adj should have more than 3 indexes. As you can see in the image below, each vertex (red), can only have 3 neighbours (green).

tris is an array of triangles, the original data-structure does not always have complete triangles, but they indexed by the vertex index, to the circumcenter's corresponding left and right cells.

You can see in the above image, that by combining the left and right circumcenter's of three edges, it describes a triangle.

The Input Data Structure:

Delaunator's data-structures guide has a lot more detail, but a quick overview is this:

Delaunator takes an array of [x, y] coordinates of length N and makes a points array of length 2N where each coordinate in the original [x, y] array now sits at it's original index * 2 if it was the x coord, and * 2 + 1 if it was the y.

For example, the coords [[1, 2], [3, 4], [5, 6]] would become: [1, 2, 3, 4, 5, 6].

It then builds a delaunay triangulation, where each triangle edge is comprised of two halfedge's.

A halfedge takes a bi-directional edge and splits it into two directional edges.

So a triangle made up of 3 edges, now has 6 halfedges like so:

It also constructs two arrays:

delaunay.triangles which takes a halfedge index and returns the point id (an index into the points array described previously) where the halfedge begins. delaunay.halfedges which takes a halfedge index and returns the opposite halfedge in the adjacent triangle:

Hopefully that's sufficient detail?

I've tried to make the setup runnable, so if someone wants to poke around with it to test out a quick hypothesis, they can do so easily, just edit the notebook or fork it.

I've also added at the bottom a more complete example that's purely focused on the "physical" things the map derives from the mesh+heightmap, which is basically the coastline and rivers.

Porting d3-voronoi to d3-delunay

0 Answers