How to write a function that interpolates an array of variable size along a selected column?

Hi,

I have written a function that can interpolate a curve described in a two dimensional array. Hereby, each row is a point (xCurve ,yCurve) on my defined curve(s), and the function calculates an linear interpolation for any point x. This works.

Now I want to extend that function so that the array is not just holding one curve, but several. And that the number of rows (points on x-Axis) is also not pre-defined.

Extension means I have several curves (values on y-axis, in severa columns) in the array, and the program is providing the interpolation for the curve to be taken while for all curves the x-axis is the same. Unfortunately, I'm failing in doing so.

Please refer to my code below:

const byte numRowsTable1 = 13;                          // Rows of Table 1
const int  myTable1 [][3]                               
                  {                                     
                    { 800,     0,     0},               
                    { 900,  4956,  2000},
                    {1000,  7754,  4000},
                    {1100,  9166,  6000},
                    {1200,  9775,  8000},
                    {1300,  9978,  9000},
                    {1350, 10000, 10000},
                    {1400,  9978,  9000},
                    {1500,  9975,  8000},
                    {1600,  9166,  7000},
                    {1700,  7754,  6000},
                    {1800,  4956,  5000},
                    {1900,     0,     0}                
                  };

const byte numRowsTable2 = 5;                          // Rows of Table 2
const int  myTable2 [][2]                               
                  {                                     
                    { 80,  10},               
                    { 90,  50},
                    {100, 100},
                    {150, 250},
                    {300, 500},
                  };

// 2D-Table Linear Interpolation
int Table2D_s16(int x, int const table2D[][3], byte const numRows, byte curve = 1) {
  
  int ret;
  // Check for boundaries of 2D-Table, otherwise interpolate
  if (x <= table2D[0][  0  ]) {                           // Below lower bound?
     ret = table2D[0][curve];                             // --> return y(x_min) for all x <= x_min
  }
  else if (x >= table2D[numRows-1][0]) {                  // Above upper bound?
     ret = table2D[numRows-1][curve];                     // --> return y(x_max) for all x >= x_max
  }
  else {                                                  // --> interpolate!
    int upper_idx = 1;
    while (x > table2D[upper_idx][0]) {                   // Find approbirate slot for interpolation
      upper_idx++;
    }
    // y = y(k) + (x - x(k)) * (y(k+1)-y(k)) / (x(k+1)- x(k))
    ret =  table2D[upper_idx - 1][curve] +              
            (int)( (long)(table2D[upper_idx][curve] - table2D[upper_idx - 1][curve]) *
                         (       x                  - table2D[upper_idx - 1][  0  ]) /
                         (table2D[upper_idx][  0  ] - table2D[upper_idx - 1][  0  ]) );
  }
  return(ret);
}

char buffer[80];
int x, ysoll;
byte curve = 2;

void setup() {
  Serial.begin(57600);
  delay(3000);
  Serial.println("Interpolate curve 2 of Table 1");
  for (byte idx = 0; idx < numRowsTable1; idx++){
    x = myTable1[idx][  0  ] + 50;
    sprintf(buffer,"At x = %4d (idx = %2d), the table 1 is read to %5d.", 
      x, idx, Table2D_s16(x, myTable1, numRowsTable1, curve));
    Serial.println(buffer);
  }
  
  Serial.println("Interpolate the 1st and only curve of Table 2");
  for (byte idx = 0; idx < numRowsTable2; idx++){
    x = myTable2[idx][  0  ] + 5;
    sprintf(buffer,"At x = %4d (idx = %2d), the table 2 is read to %5d.", 
      x, idx, Table2D_s16(x, myTable2, numRowsTable2));
    Serial.println(buffer);
  }
}

void loop() {
  // put your main code here, to run repeatedly:
}

With the part for Table 2 in, I get following error message:

C:\Users\Sebastian_2\Documents\Projekte\Arduino\Playground\HCLCurves\HCLCurves.ino: In function 'void setup()':
HCLCurves:76:53: error: cannot convert 'const int (*)[2]' to 'const int (*)[3]' for argument '2' to 'int Table2D_s16(int, const int (*)[3], byte, byte)'
       x, idx, Table2D_s16(x, myTable2, numRowsTable2));
                                                     ^
exit status 1
cannot convert 'const int (*)[2]' to 'const int (*)[3]' for argument '2' to 'int Table2D_s16(int, const int (*)[3], byte, byte)'

For better understanding also the output for curve 2 of Table 1 (the code for table 2 hidden by comments //)

Interpolate curve 2 of Table 1
At x =  850 (idx =  0), the table 1 is read to  1000.
At x =  950 (idx =  1), the table 1 is read to  3000.
At x = 1050 (idx =  2), the table 1 is read to  5000.
At x = 1150 (idx =  3), the table 1 is read to  7000.
At x = 1250 (idx =  4), the table 1 is read to  8500.
At x = 1350 (idx =  5), the table 1 is read to 10000.
At x = 1400 (idx =  6), the table 1 is read to  9000.
At x = 1450 (idx =  7), the table 1 is read to  8500.
At x = 1550 (idx =  8), the table 1 is read to  7500.
At x = 1650 (idx =  9), the table 1 is read to  6500.
At x = 1750 (idx = 10), the table 1 is read to  5500.
At x = 1850 (idx = 11), the table 1 is read to  2500.
At x = 1950 (idx = 12), the table 1 is read to     0.

Can somebody help me to adapt the function Table2D_s16 is working with both tables?

Regards
Sebastian

It is not trivial to pass 2D arrays with variable dimensions as function arguments in C++, but fortunately there are a number of tutorials on line demonstrating different approaches.

With an hour or so of study, you should have no problem finding a useful solution.

wouldn't the algorithm be

  • to pass the index of the array column (arr [row][col])
  • search the x column for the segment containing x -- search from index = 0 to index = N-2 and x > [n]
  • interpolate using the x values from col 0 and y values from the col argument

Just to clarify

do you mean that for the array below

x is always in the first column (800, 900, 1000, ...) and then the matching y for curve #1 is in column 1 (0, 4956,7754,...) and the matching y for curve #2 is in column 2 (0, 2000,4000,...) ?


This is probably best addressed with templates, try this code, you'll see that the functions knows how many rows and lines you have. Just add your own parameters and walk the array as you see fit.

const int  myTable1 [][3]
{
  { 800,     0,     0},
  { 900,  4956,  2000},
  {1000,  7754,  4000},
  {1100,  9166,  6000},
  {1200,  9775,  8000},
  {1300,  9978,  9000},
  {1350, 10000, 10000},
  {1400,  9978,  9000},
  {1500,  9975,  8000},
  {1600,  9166,  7000},
  {1700,  7754,  6000},
  {1800,  4956,  5000},
  {1900,     0,     0}
};
const size_t numColsTable1 = sizeof myTable1[0] / sizeof * myTable1[0];  // Cols of Table 1
const size_t numRowsTable1 = sizeof myTable1 / sizeof * myTable1;  // Rows of Table 1

const int  myTable2 [][2]
{
  { 80,  10},
  { 90,  50},
  {100, 100},
  {150, 250},
  {300, 500},
};
const size_t numColsTable2 = sizeof myTable2[0] / sizeof * myTable2[0]; // Cols of Table 2
const size_t numRowsTable2 = sizeof myTable2 / sizeof * myTable2; // Rows of Table 2


template <typename T, size_t numRows, size_t numCols>
void printArrayInfo(const T (&array)[numRows][numCols]) {
  Serial.print("Number of rows: ");
  Serial.println(numRows);
  Serial.print("Number of columns: ");
  Serial.println(numCols);

  for (size_t row = 0; row < numRows; ++row) {
    for (size_t col = 0; col < numCols; ++col) {
      Serial.print(array[row][col]);
      Serial.write('\t');  // Tab spacing for readability
    }
    Serial.println();
  }
}


void setup() {
  Serial.begin(115200);
  Serial.println(F("------------- TABLE 1 -------------"));
  printArrayInfo(myTable1);
  Serial.println(F("\n------------- TABLE 2 -------------"));
  printArrayInfo(myTable2);
}

void loop() {}

you should see

------------- TABLE 1 -------------
Number of rows: 13
Number of columns: 3
800		0		0	
900		4956	2000	
1000	7754	4000	
1100	9166	6000	
1200	9775	8000	
1300	9978	9000	
1350	10000	10000	
1400	9978	9000	
1500	9975	8000	
1600	9166	7000	
1700	7754	6000	
1800	4956	5000	
1900	0		0	

------------- TABLE 2 -------------
Number of rows: 5
Number of columns: 2
80	10	
90	50	
100	100	
150	250	
300	500	

1 Like

Do you need the Y-result-value within 5 to 20 microseconds = as fast as possible?
Or
would it be OK if the result is retrieved after 0,050 seconds?

Will you define the values one time while writing the code or will these value change when using the device often?

In case calculation-time can be in the range of 50 milliseconds and you do not change the values often there is another approach

Almost any spread-sheet-software like Excel, LibreOffice, etc. offers curve-approximation

You enter XY-value-pairs into the spread-sheet and choose the type of approximationfunction
linear, polynomical exponential, logrithmic.

The spread-sheet-software will calculate the coefficients for each summand.
For your first Y-columm of Y-values this looks like this

s

As you can see the orange squares which represent the values from the table
and the orange dot-line which is the linear connection from datapoint to datapoint
and the blue approximation-function are very close together.

This means the array-table is replaced by a calculation-formula f(x)

look this over

output

getXy: x  500, n  0, y -14868
getXy: x 1370, n  7, y   9978
getXy: x 1400, n  8, y  10784
getXy: x 2000, n 12, y      0

getXy: x  500, n  0, y  -6000
getXy: x 1370, n  7, y   9300
getXy: x 1400, n  8, y   9000
getXy: x 2000, n 12, y    -20
char s [90];

// -----------------------------------------------------------------------------
const int  TblXy [][3]
{ 
    {  800,     0,     0 }, // 0
    {  900,  4956,  2000 },
    { 1000,  7754,  4000 },
    { 1100,  9166,  6000 },

    { 1200,  9775,  8000 }, // 4
    { 1300,  9978,  9000 },
    { 1350, 10000, 10000 },
    { 1400,  9978,  9000 },

    { 1500,  9975,  8000 }, // 8
    { 1600,  9166,  7000 },
    { 1700,  7754,  6000 },
    { 1800,  4956,  5000 },

    { 1900,     0,     0 }, // 12
};
const byte NtblXy = 13;        // # rows

// -----------------------------------------------------------------------------
int
getXy (
    int x,
    int yIdx )
{
    int n;

    // find x segment
    for (n = 0; n < NtblXy-1; n++)
        if (TblXy [n][0] > x)
            break;

    int y = map (x, TblXy [n][0],    TblXy [n+1][0],
                    TblXy [n][yIdx], TblXy [n+1][yIdx] );

    sprintf (s, "getXy: x %4d, n %2d, y %6d", x, n, y);
    Serial.println (s);

    return y;
}


// -----------------------------------------------------------------------------
char buffer[80];
int x, ysoll;
byte curve = 2;

void setup()
{
    Serial.begin(57600);

    getXy ( 500, 1);
    getXy (1370, 1);
    getXy (1400, 1);
    getXy (2000, 1);

    getXy ( 500, 2);
    getXy (1370, 2);
    getXy (1400, 2);
    getXy (2000, 2);
}

void loop() { }

Yes, your understanding is correct.

And many thanks - it is the solution I was looking for (marked as solution)! :slightly_smiling_face: :upside_down_face: :slightly_smiling_face:

The only thing I had to put the additional parameters x and curve at the after the template definition.
Here is my final code:

const int  myTable1 [][3]
{
  { 800,     0,     0},
  { 900,  4956,  2000},
  {1000,  7754,  4000},
  {1100,  9166,  6000},
  {1200,  9775,  8000},
  {1300,  9978,  9000},
  {1350, 10000, 10000},
  {1400,  9978,  9000},
  {1500,  9975,  8000},
  {1600,  9166,  7000},
  {1700,  7754,  6000},
  {1800,  4956,  5000},
  {1900,     0,     0}
};
const size_t numColsTable1 = sizeof myTable1[0] / sizeof * myTable1[0];  // Cols of Table 1
const size_t numRowsTable1 = sizeof myTable1 / sizeof * myTable1;  // Rows of Table 1

const int  myTable2 [][2]
{
  { 80,  10},
  { 90,  50},
  {100, 100},
  {150, 250},
  {300, 500},
};
const size_t numColsTable2 = sizeof myTable2[0] / sizeof * myTable2[0]; // Cols of Table 2
const size_t numRowsTable2 = sizeof myTable2 / sizeof * myTable2; // Rows of Table 2


template <typename T, size_t numRows, size_t numCols>
int Table2D_s16(const T (&table2D)[numRows][numCols], int x, byte curve = 1) {
  int ret;
  // Check for boundaries of 2D-Table, otherwise interpolate
  if (x <= table2D[0][  0  ]) {                           // Below lower bound?
     ret = table2D[0][curve];                             // --> return y(x_min) for all x <= x_min
  }
  else if (x >= table2D[numRows-1][0]) {                  // Above upper bound?
     ret = table2D[numRows-1][curve];                     // --> return y(x_max) for all x >= x_max
  }
  else {                                                  // --> interpolate!
    int upper_idx = 1;
    while (x > table2D[upper_idx][0]) {                   // Find approbirate slot for interpolation
      upper_idx++;
    }
    // y = y(k) + (y(k+1)-y(k)) * (x - x(k)) / (x(k+1)- x(k))
    ret =  table2D[upper_idx - 1][curve] +              
            (int)( (long)(table2D[upper_idx][curve] - table2D[upper_idx - 1][curve]) *
                         (       x                  - table2D[upper_idx - 1][  0  ]) /
                         (table2D[upper_idx][  0  ] - table2D[upper_idx - 1][  0  ]) );
  }
  return(ret);
}

char buffer[80];
int x, ysoll;
byte curve = 2;

void setup() {
  Serial.begin(57600);
  delay(3000);
  Serial.print("Table 1: Rows = ");
  Serial.print(numRowsTable1); Serial.print(" ,Cols = ");Serial.println(numColsTable1);
  Serial.print("Table 2: Rows = ");
  Serial.print(numRowsTable2); Serial.print(" ,Cols = ");Serial.println(numColsTable2);

  sprintf(buffer, "Interpolate curve %d of Table 1", curve);
  Serial.println(buffer);
  for (byte idx = 0; idx < numRowsTable1; idx++){
    x = myTable1[idx][  0  ] + 50;
    sprintf(buffer,"At x = %4d (idx = %2d), the table 1 is read to %5d.", 
      x, idx, Table2D_s16(myTable1, x, curve));
    Serial.println(buffer);
  }

  Serial.println(" ");
  Serial.println("Interpolate the 1st and only curve of Table 2");
  for (byte idx = 0; idx < numRowsTable2; idx++){
    x = myTable2[idx][  0  ] + 5;
    sprintf(buffer,"At x = %4d (idx = %2d), the table 2 is read to %5d.", 
      x, idx, Table2D_s16(myTable2, x));
    Serial.println(buffer);
  }
}

void loop() {
  // put your main code here, to run repeatedly:
}

Matter of fact: no. Today the curves are interpolated every minute, so there would be plenty of time.

To be honest, I haven't thought of this. But, even though, e.g., polynominal, would look nicer (as you have shared), it also would be a little overdone for the intended application.

myTable1 in its 2nd column contains the reference colortemperature a set of tuneable white high-power LEDs shall be controlled to, and the first column is the corresponding day-time in industrial minutes (i.e. 1350 equal 13:30 o'clock). At the end, it is about adjusting the lighting to the sun.
The other columns would be different selectable profiles (note: I put here just numbers in the 3rd column for testing).
But since tuneable white LEDs consist phyiscally of just two LEDs (2800K and 6500K in my case), interpolation to obtain intermediate colortemperatures can be done just in a linear fashion.
Example: to obtain, e.g. 4650K, both LEDs are driven with same current because 4650K is just in the middle of 2800K and 6500K
BUT: in color space white for different color temperatures isn't a straigt line but curved. So, at the end, dominant errors are done by this linear control of the two LEDs and not by the curves stored in the table and how intermediate values are retrieved.

I did. And was playing with it.

Oh, it took some time to understand. Not sure if I will use - I prefer code that I understand easily on my own.
Additionally, as outlined above and you couldn't be aware of, for times outside the range of the table (first column), a further interpolation shall not be done. But function map() does that, and so additional if-statements would be required anyway (already in my code).

Again, thanks for your support!

1 Like

cool.

For sake of coherence, you should use size_t for the type of the curve instead of byte (unless you are really RAM constrained, in which case replace the other size_t by byte too. that will limit your arrays to 255 entries or columns)

also x is probably of type T instead of int as well as ret

so something like:

template <typename T, size_t numRows, size_t numCols>
T Table2D_s16(const T (&table2D)[numRows][numCols], T x, size_t curve = 1) {
  T ret;

and check the inner variables like
int upper_idx = 1;
which would be also size_t if it's an index
and double checks types there

            (int)( (long)(table2D[upper_idx][curve] - table2D[upper_idx - 1][curve]) *
                         (       x                  - table2D[upper_idx - 1][  0  ]) /
                         (table2D[upper_idx][  0  ] - table2D[upper_idx - 1][  0  ]) );

if you only want to use int's in your tables then drop the templated type T and simplify as

template <size_t numRows, size_t numCols>
int Table2D_s16(const int (&table2D)[numRows][numCols], int x, size_t curve = 1) {
  int ret;

or if you need less than 255 entries

template < byte numRows, byte numCols>
int Table2D_s16(const int (&table2D)[numRows][numCols], int x, byte curve = 1) {
  int ret;

Not sure if I got this right. But it is correct that upper_idx shall be actually a byte (/uint8_t) as well. Code updated.

With respect to your other proposals it looks as they do not run with C++11 being used in IDE1.8.19, which I still use.

I.e.

template <typename T, byte numRows, byte numCols>
int Table2D_s16(const T (&table2D)[numRows][numCols], int x, byte curve = 1) {
  int ret;

does compile, while just changing to

template <byte numRows, byte numCols>
int Table2D_s16(const int (&table2D)[numRows][numCols], int x, byte curve = 1) {
  int ret;

because the function is intended to run with int in any case, does not. Following error message is created (look for warning: variable templates only available with -std=c++14 or -std=gnu++14 at 2nd line of text below):

HCLCurves_Final_v2f6:34:54: error: expected primary-expression before 'const'
 
                                                      ^    
C:\Users\Sebastian_2\Documents\Projekte\Arduino\Playground\HCLCurves_Final_v2f6\HCLCurves_Final_v2f6.ino:34:42: warning: variable templates only available with -std=c++14 or -std=gnu++14
 
                                          ^          
HCLCurves_Final_v2f6:34:73: error: previous non-function declaration 'template<unsigned char numRows, unsigned char numCols> int Table2D_s16<numRows, numCols>'
 
                                                                         ^
HCLCurves_Final_v2f6:36:78: error: conflicts with function declaration 'template<unsigned char numRows, unsigned char numCols> int Table2D_s16(const int (&)[numRows][numCols], int, byte)'
 int Table2D_s16(const int (&table2D)[numRows][numCols], int x, byte curve = 1) {
                                                                              ^
C:\Users\Sebastian_2\Documents\Projekte\Arduino\Playground\HCLCurves_Final_v2f6\HCLCurves_Final_v2f6.ino: In function 'void setup()':
HCLCurves_Final_v2f6:76:26: error: missing template arguments before '(' token
       x, idx, Table2D_s16(myTable1, x, curve));
                          ^
HCLCurves_Final_v2f6:85:26: error: missing template arguments before '(' token
       x, idx, Table2D_s16(myTable2, x));
                          ^
exit status 1
expected primary-expression before 'const'

So, I guess, I stick to the little improvement with respect to upper_idx

The version of C++ that's used to compile your code is set by the Arduino Core for the particular board you've selected, not the version of the IDE. For example, when an ESP32 board is selected, the code will be compiled as C++20 (assuming you use a fairly new ESP32 Arduino Core package).

I wasn't aware of this.

I run my tests on Arduino Uno. So all my replies refer to this board.

Just made a quick check for Arduino Nano Every, which will be the final one, and got same error messge by just trying to compile.

That board is based on an ATMega4809 which is an 8-bit AVR processor (as is the processor on an Uno Board). So, it's not surprising you got the same error.

I guess this is due to how the IDE tries to generate the function's prototypes and fails with the template... stick to the templated type indeed...

Just some final modification. When changed to

template<typename arrayType>
int Table2D_s16(int x, arrayType &table2D, byte curve = 1) {
  const uint8_t numRows = sizeof (arrayType) / sizeof table2D[0];
  int ret;

the definition of the tables can be limited to

const byte  myTable3 [][3]                               
                  {                                     
                    { 80,  10, 100},               
                    { 90,  50, 200},
                    {100, 100, 210},
                    {150, 200, 220},
                    {250, 250, 230},
                  };

I compared Flash and SRAM consumption, as well as computation time. Well marginal, a few bytes more (less than 10), and 10% increase in computation time for taken examples (about 5-8us, 8us for the larger table with 13 rows shown above); nothing to worry about.
But, I think, a little more easy to use because number of rows and columns disappear from the function call (less risk of typos, or accidently just half adaption for other table after copy and paste).
Function call is then simply

    y = Table2D_s16(x, myTable3, curve);

... I'm a lazy guy :wink: ...

1 Like