C＃/ Unity3D中的分段线性整数曲线插值

有没有一种简单有效的方法在C＃中实现分段线性整数到整数曲线插值（对于Unity3D，如果重要的话）？
详情如下：

• 分段线性曲线表示必须随着时间的推移而建立。 第一个插值请求在我们拥有所有数据点之前
• 曲线严格单调
• 第一点总是（0,0）
• 数据点的第一坐标也是严格单调的到达时间，即这些点自然地按其第一坐标排序。
• 数据点不在可能导致4字节整数导致溢出问题的范围内
• 输出不必100％准确，因此舍入误差不是问题。

在C ++中，我会做这样的事情：

#include  #include  #include  using namespace std; typedef pair tDataPoint; typedef vector tPLC; void appendData(tPLC& curve, const tDataPoint& point) { assert(curve.empty() || curve.back().first  0) { // find the first data point above the cursor const auto upper = upper_bound(begin(curve), end(curve), cursor); // above the last data point, the value is a constant 0 if (upper == end(curve)) { result = curve.back().second; } else { // get the point below or equal to the cursor const auto lower = upper - 1; // lerp between float linear = float((cursor - lower.first) * (upper.second - lower.second)) / (upper.first - lower.first); result = lower.second + int(linear); } } return result; } 

我可以看到我如何在C＃中做一些类似的工作，但没有简洁或有效的方法。 任何帮助将不胜感激。

编辑：我不需要更准确，并且对分段线性插值非常满意，因此更好的插值质量不是我的问题。
我正在寻找的是一种有效，简洁的方法。 通过有效，我的意思是：依赖于数据点自然被排序以便能够使用二进制搜索来找到正确的段的事实

Answer 1

我会用这个插值立方体：

 x=a0+a1*t+a2*t*t+a3*t*t*t y=b0+b1*t+b2*t*t+b3*t*t*t 

其中a0..a3的计算方式如下：

 d1=0.5*(p2.x-p0.x); d2=0.5*(p3.x-p1.x); a0=p1.x; a1=d1; a2=(3.0*(p2.x-p1.x))-(2.0*d1)-d2; a3=d1+d2+(2.0*(-p2.x+p1.x)); 

b0 .. b3以相同的方式计算，但当然使用y坐标
p0..p3是三次插值曲线的控制点
t = < 0.0 , 1.0 >是从p1到p2曲线参数

这确保了位置和一阶导数是连续的（c1）。 如果你想在整数数学上做这个，那么只需缩放ai,bi ant t 。 您也可以以相同的方式添加任意数量的维度

现在您需要一些参数来遍历插值点，例如u = <0 , N-1>

p(0..N-1)是您的控制点列表
u = 0表示起点p(0)
u = N-1表示终点p(N-1)
P0..P3是用于插值的控制点

因此，您需要计算t并选择要用于插值的点

  double t=u-floor(u); // fractional part between control points int i=floor(u); // integer part points to starting control point used if (i<1) { P0=p( 0),P1=p( 0),P2=p( 1),P3=p( 2); } // handle start edge case else if (i==N-1) { P0=p(N-2),P1=p(N-1),P2=p(N-1),P3=p(N-1); } // handle end edge case else if (i>=N-2) { P0=p(N-3),P1=p(N-2),P2=p(N-1),P3=p(N-1); } // handle end edge case else { P0=p(i-1),P1=p(i ),P2=p(i+1),P3=p(i+2); } (x,y) = interpolation (P0,P1,P2,P3,t); 

如果你想在整数数学上做这个，那么只需缩放u,t 。 如果N<3则使用线性插值...或复制端点，直到N>=3

[edit1]线性插值方法

 struct pnt { int x,y; }; pnt interpolate (pnt *p,int N,int x) { int i,j; pnt p; for (j=1,i=N-1;j>=1; if (!j) j=1; // this just determine max mask for binary search ... can do it on p[] size change for (i=0;j;j>>=1) // binary search by x coordinate output is i as point index with p[i].x<=x { i|=j; if (i>=N) { i-=j; continue; } if (p[i].x==x) break; if (p[i].x> x) i-=j; } px=x; py=p[i].y+((p[i+1].yp[i].y)*(xp[i].x)/(p[i+1].xp[i].x)) return p; } 

添加边缘情况处理像x是超出点绑定或点列表太小