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 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 interpolation method does is that it finds an element, in this case a triangle, a coordinate inside. Then it interpolates the value between the corners of the element in which it is contained.

I understand that there are many aspects in it to optimize performance, for example, to grow a tree, which allows you to quickly narrow the elements, having previously processed the bounding rectangles. All of this would be great, but I'm just trying to get started.

There should be some kind of library that I can use for it instead of writing my own.

Answer 1

Since the search results for barycentric interpolation in javascript were inconclusive, here is some code that can help you get started.

This code takes as input a set of two-dimensional points, each with a value of "value" and a "new point" with an unknown value. First, he finds the smallest triangle in the dataset that contains the “new point”, then performs barycentric interpolation using this triangle to find the value for the “new point”.

. , - , . N 3, N, , " " " ", .

// 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)); 

, . kriging, .js .