Кусочно-линейная целочисленная интерполяция в C # / Unity3D
Существует ли простой и эффективный способ реализации кусочно-линейной интерполяции целочисленных кривых в 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 #, но не так лаконично или эффективно. Любая помощь будет оценена.
РЕДАКТИРОВАТЬ:
Мне не нужно быть более точным, и я совершенно доволен кусочно-линейной интерполяцией, поэтому лучшее качество интерполяции здесь не моя проблема.
То, что я ищу, — эффективный, краткий способ сделать это. Под эффективностью я имею в виду такие вещи, как: полагаться на тот факт, что точки данных естественным образом упорядочены, чтобы иметь возможность использовать бинарный поиск, чтобы найти нужный сегмент
Решение
Я бы использовал эту кубическую интерполяцию:
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 муравей 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 вне границ точек или список точек слишком мал
Другие решения
Других решений пока нет …