1

C＃で区分線形整数から整数への曲線補間を実装する簡単で効率的な方法はありますか（それが重要な場合はUnity3Dの場合）？
詳細は次のとおりです。

  • 区分線形曲線表現は、時間をかけて構築する必要があります。最初の補間リクエストは、すべてのデータ ポイントを取得する前に行われます
  • 曲線は厳密に単調です
  • 最初の点は常に (0, 0)
  • データポイントの最初の座標も、到着時間に関して厳密に単調です。つまり、ポイントは最初の座標によって自然に順序付けられます。
  • データ ポイントは、4 バイト整数のオーバーフローの問題を引き起こす範囲内にありません
  • 出力は 100% 正確である必要はないため、丸め誤差は問題になりません。

C++ では、次のようにします。

#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# でこのような動作を行う方法はわかりますが、簡潔でも効率的でもありません。どんな助けでも大歓迎です。

編集:より正確である必要はなく、区分線形補間に完全に満足しているため、補間品質の向上はここでは問題ではありません。
私が探しているのは、これを行うための効率的で簡潔な方法です。効率的とは、次のようなことを意味します: データ ポイントが自然に順序付けられているという事実に依存して、二分探索を使用して適切なセグメントを見つけることができるようにする

4

1 に答える 1

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。 3 次補間の制御点です。 曲線 は からまで
t = < 0.0 , 1.0 >の曲線パラメータです。p1p2

これにより、位置と一次導関数が連続することが保証されます (c1)。整数演算でこれを行う場合は、それに応じてai,biantをスケーリングし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<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バインドされたポイントの外にある、またはポイント リストが小さすぎるなどの特殊なケースの処理を追加します

于 2014-04-02T08:55:18.180 に答える