PAL Algorithms: Interpolation

Interpolation routines for two- and three-dimensional grids, cubic splines, and Newton-form polynomial interpolation.

PAL Algorithms: Interpolation — 12 functions

KiratAlgCorePalAlgoBilinearInterpolationGetDoubleValueAt

Signature
T_DOUBLE KiratAlgCorePalAlgoBilinearInterpolationGetDoubleValueAt( T_DOUBLE **ppdDataZ, T_DOUBLE dXSpace, T_DOUBLE dYSpace, T_INT iNumX, T_INT iNumY, T_DOUBLE dX, T_DOUBLE dY);
Description
Performs bilinear interpolation on an equidistant 2D support grid using double-precision values. At the boundaries, the implementation falls back to edge/corner values or one-dimensional interpolation.
Mathematical operation
\(i_x=\operatorname{trunc}(x/\Delta_x),\;i_y=\operatorname{trunc}(y/\Delta_y),\;u=x/\Delta_x-i_x,\;v=y/\Delta_y-i_y;\quad z=(1-u)(1-v)z_{i_x,i_y}+u(1-v)z_{i_x+1,i_y}+(1-u)vz_{i_x,i_y+1}+uvz_{i_x+1,i_y+1}\). At an outer edge the code reduces this to 1-D interpolation or returns the nearest corner value.

KiratAlgCorePalAlgoBilinearInterpolationGetFloatValueAt

Signature
T_FLOAT KiratAlgCorePalAlgoBilinearInterpolationGetFloatValueAt( T_FLOAT **ppfDataZ, T_FLOAT fXSpace, T_FLOAT fYSpace, T_INT iNumX, T_INT iNumY, T_FLOAT fX, T_FLOAT fY);
Description
Performs bilinear interpolation on an equidistant 2D support grid using single-precision values. At the boundaries, the implementation falls back to edge/corner values or one-dimensional interpolation.
Mathematical operation
\(i_x=\operatorname{trunc}(x/\Delta_x),\;i_y=\operatorname{trunc}(y/\Delta_y),\;u=x/\Delta_x-i_x,\;v=y/\Delta_y-i_y;\quad z=(1-u)(1-v)z_{i_x,i_y}+u(1-v)z_{i_x+1,i_y}+(1-u)vz_{i_x,i_y+1}+uvz_{i_x+1,i_y+1}\). At an outer edge the code reduces this to 1-D interpolation or returns the nearest corner value.

KiratAlgCorePalAlgoDoubleGetSplineInterpolationCoefficients

Signature
void KiratAlgCorePalAlgoDoubleGetSplineInterpolationCoefficients( T_DOUBLE *pdInputY, T_DOUBLE *pdInputX, T_DOUBLE *pdA, T_DOUBLE *pdB, T_DOUBLE *pdC, T_DOUBLE *pdD, T_DOUBLE *pdAlpha, T_DOUBLE *pdBeta, T_INT iLen);
Description
Calculates the coefficients of a cubic spline in double precision by solving a tridiagonal system of equations.
Mathematical operation
For \(h_i=x_i-x_{i-1}\) the code forms \(F_i=6[(y_{i+1}-y_i)/h_{i+1}-(y_i-y_{i-1})/h_i]\) and solves the tridiagonal spline system recursively. It then sets \(a_i=y_i\), \(d_i=(c_i-c_{i-1})/h_i\) and \(b_i=(y_i-y_{i-1})/h_i+h_i(2c_i+c_{i-1})/6\), yielding \(S_i(x)=a_i+b_i\Delta+c_i\Delta^2/2+d_i\Delta^3/6\).

KiratAlgCorePalAlgoDoubleSplineInterpolationGetValue

Signature
T_DOUBLE KiratAlgCorePalAlgoDoubleSplineInterpolationGetValue( T_DOUBLE *pdInputX, T_DOUBLE *pdA, T_DOUBLE *pdB, T_DOUBLE *pdC, T_DOUBLE *pdD, T_INT iLen, T_DOUBLE dX, T_BOOL bEquidistant);
Description
Evaluates a previously calculated cubic spline at position x using double precision.
Mathematical operation
\(S_j(x)=a_j+b_j\Delta+c_j\Delta^2/2+d_j\Delta^3/6,\quad \Delta=x-x_j\). For equidistant points the implementation uses \(j=\operatorname{trunc}\!\left(x/(x_1-x_0)\right)\); otherwise it selects the interval by binary search and returns the endpoint value outside the support range.

KiratAlgCorePalAlgoFloatGetSplineInterpolationCoefficients

Signature
void KiratAlgCorePalAlgoFloatGetSplineInterpolationCoefficients( T_FLOAT *pfInputY, T_FLOAT *pfInputX, T_FLOAT *pfA, T_FLOAT *pfB, T_FLOAT *pfC, T_FLOAT *pfD, T_FLOAT *pfAlpha, T_FLOAT *pfBeta, T_INT iLen);
Description
Calculates the coefficients of a cubic spline in single precision by solving a tridiagonal system of equations.
Mathematical operation
For \(h_i=x_i-x_{i-1}\) the code forms \(F_i=6[(y_{i+1}-y_i)/h_{i+1}-(y_i-y_{i-1})/h_i]\) and solves the tridiagonal spline system recursively. It then sets \(a_i=y_i\), \(d_i=(c_i-c_{i-1})/h_i\) and \(b_i=(y_i-y_{i-1})/h_i+h_i(2c_i+c_{i-1})/6\), yielding \(S_i(x)=a_i+b_i\Delta+c_i\Delta^2/2+d_i\Delta^3/6\).

KiratAlgCorePalAlgoFloatSplineInterpolationGetValue

Signature
T_FLOAT KiratAlgCorePalAlgoFloatSplineInterpolationGetValue( T_FLOAT *pfInputX, T_FLOAT *pfA, T_FLOAT *pfB, T_FLOAT *pfC, T_FLOAT *pfD, T_INT iLen, T_FLOAT fX, T_FLOAT bEquidistant);
Description
Evaluates a previously calculated cubic spline at position x. For non-equidistant support points, the appropriate interval is found by binary search.
Mathematical operation
\(S_j(x)=a_j+b_j\Delta+c_j\Delta^2/2+d_j\Delta^3/6,\quad \Delta=x-x_j\). For equidistant points the implementation uses \(j=\operatorname{trunc}\!\left(x/(x_1-x_0)\right)\); otherwise it selects the interval by binary search and returns the endpoint value outside the support range.

KiratAlgCorePalAlgoPolyfit

Signature
void KiratAlgCorePalAlgoPolyfit( T_DOUBLE *pdDataPointsX, T_DOUBLE *pdDataPointsY, T_INT iPolynomialOrder );
Description
Computes Newton interpolation coefficients from support points using divided differences. The input y-values are replaced by the resulting coefficients.
Mathematical operation
\(a_k=f[x_0,\ldots,x_k]\), with divided differences \(f[x_i,\ldots,x_j]=\dfrac{f[x_{i+1},\ldots,x_j]-f[x_i,\ldots,x_{j-1}]}{x_j-x_i}\). The array containing the input \(y_i\) values is overwritten by the Newton coefficients \(a_k\).

KiratAlgCorePalAlgoPolyval

Signature
void KiratAlgCorePalAlgoPolyval( T_DOUBLE *pdDataPointsX, T_DOUBLE *pdNewtonCoeff, T_DOUBLE dInput, T_DOUBLE *pdOutput, T_INT iPolynomialOrder );
Description
Evaluates a Newton interpolation polynomial efficiently in nested form.
Mathematical operation
\(p(x)=a_0+(x-x_0)\left[a_1+(x-x_1)\left[a_2+\cdots +(x-x_{m-1})a_m\right]\right]\).

KiratAlgCorePalAlgoTrilinearInterpolationCalcIndexRatio

Signature
T_FLOAT KiratAlgCorePalAlgoTrilinearInterpolationCalcIndexRatio(T_INT iNum, T_INT iNumUpscaled);
Description
Calculates the ratio between input and output indices used for trilinear resampling (Float).
Mathematical operation
\(r=\begin{cases}(N_{\mathrm{up}}-1)/(N-1),&N>1,\\1,&N\le1.\end{cases}\)

KiratAlgCorePalAlgoTrilinearInterpolationCalcIndexRatiod

Signature
T_DOUBLE KiratAlgCorePalAlgoTrilinearInterpolationCalcIndexRatiod(T_INT iNum, T_INT iNumUpscaled);
Description
Calculates the ratio between input and output indices used for trilinear resampling (Double).
Mathematical operation
\(r=\begin{cases}(N_{\mathrm{up}}-1)/(N-1),&N>1,\\1,&N\le1.\end{cases}\)

KiratAlgCorePalAlgoTrilinearInterpolationGetDoubleValueAt

Signature
T_DOUBLE KiratAlgCorePalAlgoTrilinearInterpolationGetDoubleValueAt( T_DOUBLE*** pppfData, T_DOUBLE dXIndexRatio, T_DOUBLE dYIndexRatio, T_DOUBLE dZIndexRatio, T_INT iNumX, T_INT iNumY, T_INT iNumZ, T_DOUBLE dXIndex, T_DOUBLE dYIndex, T_DOUBLE dZIndex);
Description
Performs trilinear interpolation in a 3D grid using double precision. Indices are limited to the valid data range.
Mathematical operation
\(\xi=x_{\mathrm{out}}/r_x,\;\eta=y_{\mathrm{out}}/r_y,\;\zeta=z_{\mathrm{out}}/r_z\). With \(i_0=\operatorname{trunc}(\xi)\), \(j_0=\operatorname{trunc}(\eta)\), \(k_0=\operatorname{trunc}(\zeta)\) (neighbor indices clipped to the valid array) and \(u=\xi-i_0\), \(v=\eta-j_0\), \(w=\zeta-k_0\): \(f=\sum_{a,b,c\in\{0,1\}}f_{i_a j_b k_c}(1-u)^{1-a}u^a(1-v)^{1-b}v^b(1-w)^{1-c}w^c\).

KiratAlgCorePalAlgoTrilinearInterpolationGetFloatValueAt

Signature
T_FLOAT KiratAlgCorePalAlgoTrilinearInterpolationGetFloatValueAt( T_FLOAT*** pppfData, T_FLOAT fXIndexRatio, T_FLOAT fYIndexRatio, T_FLOAT fZIndexRatio, T_INT iNumX, T_INT iNumY, T_INT iNumZ, T_FLOAT fXIndex, T_FLOAT fYIndex, T_FLOAT fZIndex);
Description
Performs trilinear interpolation in a 3D grid. The value is interpolated linearly along x, then y, and finally z.
Mathematical operation
\(\xi=x_{\mathrm{out}}/r_x,\;\eta=y_{\mathrm{out}}/r_y,\;\zeta=z_{\mathrm{out}}/r_z\). With \(i_0=\operatorname{trunc}(\xi)\), \(j_0=\operatorname{trunc}(\eta)\), \(k_0=\operatorname{trunc}(\zeta)\) (neighbor indices clipped to the valid array) and \(u=\xi-i_0\), \(v=\eta-j_0\), \(w=\zeta-k_0\): \(f=\sum_{a,b,c\in\{0,1\}}f_{i_a j_b k_c}(1-u)^{1-a}u^a(1-v)^{1-b}v^b(1-w)^{1-c}w^c\).