在JavaScript中插值不规则2D数据的值

Question

在JavaScript中插值不规则2D数据的值

4

我需要找到一个库，可以让我从不规则的二维数据中获得插值值。想象一下有这样一些数据：

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

插值方法的作用是找到包含该坐标的元素，例如三角形，然后在该元素的角落之间插值。我知道有很多方面需要优化性能，比如构建一棵树，通过预处理边界框实现快速缩小元素。这些也都很好，但我只是想开始尝试。肯定有一些库可以代替自己编写。

- Franz Thomsen

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- rphv · Accepted Answer

由于搜索关于在javascript中的重心插值的结果不确定，这里提供了一些代码，可能会帮助你入门。

此代码以数据集的2D点为输入，每个点都有一个“值”，以及一个未知值的“新点”。它首先找到包含“新点”的数据集中最小的三角形，然后使用该三角形执行重心插值以找到“新点”的值。

对于几百个点的数据集，这个程序运行得相当快。有很多测试、错误检查和优化的机会——例如，不要查看数据集中的每个可能的三角形。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: https://dev59.com/VW025IYBdhLWcg3w3J5H#5752056
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: https://dev59.com/HW865IYBdhLWcg3wkfgW#20066663
  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));

还有其他种类的空间插值，例如克里金插值, 它至少有一个现成的.js库。