Interpolación de curvas enteras lineales por partes en C#/ Unity3D

c++ interpolation

Question

¿Existe una forma simple y eficiente de implementar una interpolación de curva de entero a entero lineal por segmentos en C # (para Unity3D, si es importante)?
Los detalles son los siguientes:

• La representación de la curva lineal a trozos tiene que construirse a lo largo del tiempo. La primera solicitud de interpolación se produce antes de que tengamos todos los puntos de datos
• La curva es estrictamente monótona
• El primer punto es siempre (0, 0)
• Las primeras coordenadas de los puntos de datos también son estrictamente monótonas con el tiempo de llegada, es decir, los puntos se ordenan naturalmente por su primera coordenada.
• Los puntos de datos no están en rangos que causarían problemas de desbordamiento de causa para enteros de 4 bytes
• La salida no tiene que ser 100% precisa, por lo que los errores de redondeo no son un problema.

En C ++, haría algo como esto:

#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;
}

Puedo ver cómo puedo hacer algo que funciona más o menos así en C #, pero nada tan conciso o eficiente. Cualquier ayuda será apreciada.

EDITAR: No necesito ser más preciso, y estoy perfectamente satisfecho con la interpolación lineal por partes, así que una mejor calidad de interpolación no es mi problema aquí.
Lo que estoy buscando es una forma eficiente y concisa de hacer esto. Por eficiente, me refiero a cosas como: confiar en el hecho de que los puntos de datos están ordenados naturalmente para poder utilizar la búsqueda binaria para encontrar el segmento adecuado

Answer 1

Yo usaría esta interpolación cúbica:

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

donde a0..a3 se calculan de la siguiente manera:

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 se calculan de la misma manera pero usan coordenadas y por supuesto
p0..p3 son puntos de control para curva de interpolación cúbica
t = < 0.0 , 1.0 > es el parámetro de curva de p1 a p2

Esto asegura que la posición y la primera derivación es continua (c1). Si quiere hacer esto en matemáticas enteras, simplemente escale ai,bi y t consecuencia. También puede agregar tantas dimensiones como necesite de la misma manera

Ahora necesita algún parámetro para pasar por sus puntos de interpolación, por ejemplo, u = <0 , N-1>

p(0..N-1) son su lista de puntos de control
u = 0 significa el punto de inicio p(0)
u = N-1 significa punto final p(N-1)
P0..P3 son puntos de control utilizados para la interpolación

Entonces necesita calcular t y seleccionar qué puntos usar para la interpolación

 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);

Si quieres hacer esto en matemáticas enteras, simplemente escala u,t consecuencia. Si N<3 entonces usa interpolación lineal ... o puntos finales duplicados hasta N>=3

[edit1] enfoque de interpolación lineal

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;
}

agregar casos extremos manejando como x está fuera de los límites de los puntos o la lista de puntos es demasiado pequeña