Interpolate values in irregular 2d data in JavaScript

Question

I need to find a library that allows me to get interpolated values from irregular 2d data. Imagine having something like this:

var data = [{{x: 0, y: 0, value: 0},
             {x: 0.5, y: 1, value: 1},
             {x: 1, y: 0, value: 2}}, .... Many more elements]

var value = interpolate(data, 0.24, 0.3); // 0.24 = x, 0.3 = y

What the interpolate method does is that it finds the element, in this case a triangle, that the coordinate is inside. Then it interpolates the value between the corners of the element it is contained in.

I do realize that there are lots of aspects in it to optimize performance like building up a tree that allows fast narrowing of elements by having preprocessed bounding boxes. All of this would be great as well, but I am just trying to get started.

There must be some library out there that I can use for it instead of writing my own.

Answer 1

Since search results for barycentric interpolation in javascript were inconclusive, here's some code that might help you get started.

This code takes as input a data set of 2D points, each with a "value", and a "new point" with an unknown value. It first finds the smallest triangle in the data set that contains the "new point", then performs barycentric interpolation using that triangle to find a value for the "new point".

This runs reasonably quickly with a data set of a few hundred points. There are many opportunities for testing, error checking, and optimization - for example, don't look at every possible triangle in the data set. N choose 3 grows with the cube of N, so optimizing to look at triangles made with only points "close to" the "new point" could show significant performance gains.

// Calculate the area of a triangle
function triangle_area(vertexA, vertexB, vertexC) {
  return Math.abs(((vertexA.x - vertexC.x) * (vertexB.y - vertexA.y) - (
    vertexA.x - vertexB.x) * (vertexC.y - vertexA.y)) * 0.5)
}

// Given a number N, return a list of all possible triples from the list [1..N]
// credit: http://stackoverflow.com/a/5752056/1612562
function list_triples(N) {
  var fn = function(n, src, got, all) {
    if (n == 0) {
      if (got.length > 0) {
        all[all.length] = got;
      }
      return;
    }
    for (var j = 0; j < src.length; j++) {
      fn(n - 1, src.slice(j + 1), got.concat([ src[j] ]), all);
    }
    return;
  }

  var triples = [];

  // Generates the list [0, ..., N]
  // credit: http://stackoverflow.com/a/20066663/1612562
  var indices = 
      Array.apply(null, {length: N}).map(Number.call, Number);

  fn(3, indices, [], triples);

  return triples;
}

// Given three vertices of a triangle and a point, determine if
// the point falls in the triangle
// credit: https://koozdra.wordpress.com/2012/06/27/javascript-is-point-in-triangle/
// credit: http://www.blackpawn.com/texts/pointinpoly/default.html
function is_in_triangle(newPoint, vertexA, vertexB, vertexC) {
  var v0 = [vertexC.x - vertexA.x, vertexC.y - vertexA.y];
  var v1 = [vertexB.x - vertexA.x, vertexB.y - vertexA.y];
  var v2 = [newPoint.x - vertexA.x, newPoint.y - vertexA.y];

  var dot00 = (v0[0] * v0[0]) + (v0[1] * v0[1]);
  var dot01 = (v0[0] * v1[0]) + (v0[1] * v1[1]);
  var dot02 = (v0[0] * v2[0]) + (v0[1] * v2[1]);
  var dot11 = (v1[0] * v1[0]) + (v1[1] * v1[1]);
  var dot12 = (v1[0] * v2[0]) + (v1[1] * v2[1]);

  var invDenom = 1 / (dot00 * dot11 - dot01 * dot01);

  var u = (dot11 * dot02 - dot01 * dot12) * invDenom;
  var v = (dot00 * dot12 - dot01 * dot02) * invDenom;

  return ((u >= 0) && (v >= 0) && (u + v < 1));
}

// Perform barycentric interpolation on a point in a triangle
function barycentric_interpolate(newPoint, vertexA, vertexB, vertexC) {
  var area = triangle_area(vertexA, vertexB, vertexC);
  var sub_area_1 = triangle_area(newPoint, vertexB, vertexC);
  var sub_area_2 = triangle_area(vertexA, newPoint, vertexC);
  var sub_area_3 = triangle_area(vertexA, vertexB, newPoint);
  return ((sub_area_1 * vertexA.v) + (sub_area_2 * vertexB.v) + (sub_area_3 *
    vertexC.v)) / area;
}

// Find the smallest triangle in the data set containing the new
// point, and perform barycentric interpolation using that triangle 
function interpolate(newPoint, data) {
  var triangles = list_triples(data.length);
  var smallest_triangle_area = Number.MAX_VALUE;
  var smallest_triangle;
  for (t in triangles) {
    var vertexA = data[triangles[t][0]];
    var vertexB = data[triangles[t][1]];
    var vertexC = data[triangles[t][2]];
    var in_triangle = is_in_triangle(newPoint, vertexA, vertexB, vertexC);
    if (in_triangle) {
      if (triangle_area(vertexA, vertexB, vertexC) < smallest_triangle_area) {
        smallest_triangle = [vertexA, vertexB, vertexC];
      }
    }
  }

  return smallest_triangle 
         ? barycentric_interpolate(newPoint, smallest_triangle[0], smallest_triangle[1], smallest_triangle[2]) 
         : "Interpolation failed: newPoint isn't in a triangle";
}

var newPoint = {'x': 0.24, 'y': 0.3};

var data = [
    {'x': 0, 'y': 0, 'v': 0},
    {'x': 0.5, 'y': 1, 'v': 1},
    {'x': 1, 'y': 0, 'v': 2},
    {'x': 1.5, 'y': 2.5, 'v': 1.5},
    {'x': 2, 'y': 1, 'v': 0.5}
];

console.log(interpolate(newPoint, data)); 

There are also other kinds of spatial interpolation, e.g. kriging, which does have at least one ready-made .js library.