C#/Unity3D 中的分段线性整数曲线插值 [英] Piecewise linear integer curve interpolation in C#/Unity3D

问题描述

是否有一种简单有效的方法可以在 C# 中实现分段线性整数到整数曲线插值(对于 Unity3D，如果重要的话)?
详情如下:

Is there a simple, efficient way to implement a piecewise linear integer-to-integer curve interpolation in C# (for Unity3D, if it matters) ?
Details are as follows:

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

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

In C++, I would do something like this:

#include <algorithm>
#include <vector>
#include <cassert>

using namespace std;

typedef pair<int, int> tDataPoint;
typedef vector<tDataPoint> tPLC;

void appendData(tPLC& curve, const tDataPoint& point) {
  assert(curve.empty() || curve.back().first < point.first);
  curve.push_back(point);
}

int interpolate(const tPLC& curve, int cursor) {
  assert(!curve.empty());
  int result = 0;  
  // below zero, the value is a constant 0
  if (cursor > 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# 中做一些类似这样的工作，但没有那么简洁或高效.任何帮助将不胜感激.

I can see how I could do something that work sort of like this in C#, but nothing as concise or efficient. Any help will be appreciated.

我不需要更准确，并且对分段线性插值非常满意，因此更好的插值质量不是我的问题.
我正在寻找的是一种高效、简洁的方法.高效，我的意思是这样的事情:依赖于数据点自然排序的事实，以便能够使用二分搜索来找到合适的段

I do not need to be more accurate, and am perfectly happy with piecewise linear interpolation, so better interpolation quality is not my problem here.
What I am looking for is an efficient, concise way of doing this. By efficient, I mean things like: relying on the fact that the data points are naturally ordered to be able to use binary search to find the proper segment

推荐答案

我会使用这个插值三次方:

I would use this interpolation cubic:

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

其中 a0..a3 是这样计算的:

where a0..a3 are computed like this:

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

b0 .. b3 are computed in same way but use y coordinates of course
p0..p3 are control points for cubic interpolation curve
t = < 0.0 , 1.0 > is curve parameter from p1 to p2

这确保位置和一阶导数是连续的(c1).如果您想在整数数学上执行此操作，则只需相应地缩放 ai,bi ant t. 您还可以根据需要添加任意数量的维度以同样的方式

This ensures that position and first derivation is continuous (c1). If you want to do this on integer math then just scale ai,bi ant t accordingly. You can also add as many dimensions as you need in the same manner

现在你需要一些参数来通过你的插值点，例如 u = <0 , N-1>

Now you need some parameter to go through your interpolation points for example u = <0 , N-1>

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

p(0..N-1) are your control points list
u = 0 means start point p(0)
u = N-1 means end point p(N-1)
P0..P3 are control points used for interpolation

所以你需要计算t并选择哪些点用于插值

So you need to compute t and select which points to use for interpolation

    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

If you want to do this on integer math then just scale u,t accordingly. If N<3 then use linear interpolation ... or duplicate end points until 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<i;j<<=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;
        }
    p.x=x;
    p.y=p[i].y+((p[i+1].y-p[i].y)*(x-p[i].x)/(p[i+1].x-p[i].x))
    return p;
    }

添加边缘情况处理，例如 x 超出点边界或点列表太小

add edge cases handling like x is out of points bound or point list is too small

这篇关于C#/Unity3D 中的分段线性整数曲线插值的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！