5

For a LPC922 microcontroller (with SDCC) I want to create a lookup table with linear interpolation. Lets assume I got x and y values like

x=300 y=10,0201 
x=700 y=89,542 
x=800 y=126,452 
x=900 y=171,453 
x=1500 y=225,123

How can the code for a lookup table with linear interpolation look like, so I get for example for x=850 the right value for y ((171,453+126,452)/2)?

duplode
  • 33,731
  • 7
  • 79
  • 150
Stefan
  • 53
  • 1
  • 1
  • 3

3 Answers3

6
typedef struct { double x; double y; } coord_t;

coord_t c[5] = 
{
    {300, 10.02},
    {700, 89.542},
    {800, 126.452}, 
    {900, 171.453}, 
    {1500,225.123}
};    

double interp( coord_t* c, double x, int n )
{
    int i;

    for( i = 0; i < n-1; i++ )
    {
        if ( c[i].x <= x && c[i+1].x >= x )
        {
            double diffx = x - c[i].x;
            double diffn = c[i+1].x - c[i].x;

            return c[i].y + ( c[i+1].y - c[i].y ) * diffx / diffn; 
        }
    }

    return 0; // Not in Range
}

int main(int argc, char** argv) 
{
    double y = interp( c, 850, 5 );
}
MetallicPriest
  • 29,191
  • 52
  • 200
  • 356
2
double get_value(double x)
{
    /* NOTE: xs MUST be sorted */
    static const double xs[] = { 300, 700, 800, 900, 1500 };
    static const double ys[] = { 10.0201, 89.542, 126.452, 171.453, 225.123 };

    /* number of elements in the array */
    static const int count = sizeof(xs)/sizeof(xs[0]);

    int i;
    double dx, dy;

    if (x < xs[0]) {
        /* x is less than the minimum element
         * handle error here if you want */
        return ys[0]; /* return minimum element */
    }

    if (x > xs[count-1]) {
        return ys[count-1]; /* return maximum */
    }

    /* find i, such that xs[i] <= x < xs[i+1] */
    for (i = 0; i < count-1; i++) {
        if (xs[i+1] > x) {
            break;
        }
    }

    /* interpolate */
    dx = xs[i+1] - xs[i];
    dy = ys[i+1] - ys[i];
    return ys[i] + (x - xs[i]) * dy / dx;
}

This can fairly easily be extended to other interpolation methods if you wish. Note that you will then probably have to extend the special cases for the border regions however you wish to handle that. A common method is to do linear interpolation when not enough neighboring values are available for the preferred method.

Also when the number of values starts to grow i would recommend using a binary search method to compute the starting point. This shouldn't be a problem with this few values though.

Update: Since OP is working on a limited platform, here's a version of the above using libfixmath:

/* NOTE: xs MUST be sorted */
static const fix16_t xs[] = { 300<<16, 700<<16, 800<<16, 900<<16, 1500<<16 };
static const fix16_t ys[] = { (fix16_t)(65536.0*10.0201+0.5), (fix16_t)(65536.0*89.542+0.5), (fix16_t)(65536.0*126.452+0.5), (fix16_t)(65536.0*171.453+0.5), (fix16_t)(65536.0*225.123+0.5) };

fix16_t get_value_fix(fix16_t x)
{    
    /* number of elements in the array */
    static const int count = sizeof(xs)/sizeof(xs[0]);
    int i;
    fix16_t dx, dy;

    if (x < xs[0]) {
        /* x is less than the minimum element
         * handle error here if you want */
        return ys[0]; /* return minimum element */
    }

    if (x > xs[count-1]) {
        return ys[count-1]; /* return maximum */
    }

    /* find i, such that xs[i] <= x < xs[i+1] */
    for (i = 0; i < count-1; i++) {
        if (xs[i+1] > x) {
            break;
        }
    }

    /* interpolate */
    dx = fix16_sub(xs[i+1], xs[i]);
    dy = fix16_sub(ys[i+1], ys[i]);
    return fix16_add(ys[i],  fix16_div(fix16_mul(fix16_sub(x, xs[i]), dy), dx));
}
user786653
  • 29,780
  • 4
  • 43
  • 53
  • @Stefan: Browsing the manual for SDCC it looks like it only supports floats. In that case all the `double` declarations should be changed to `float` and all the constants should have `.0f` or simply `f` appended. Of course you might also want to use fixed point arithmetic instead. – user786653 Aug 17 '11 at 11:50
  • For the first try I changed it to int and just just fixed values without point. The problem with your solution is that Eclipse is saying: ?ASlink-Error-Could not get 534 consecutive bytes in internal RAM for area DSEG. at 1: warning 119: don't know what to do with file ' '. file extension unsupported make: *** [test.hex] Error 1 make: Target `all' not remade because of errors. If I use just 4 or less values it is alright, but if I use more it seems that there is not enough RAM for it. – Stefan Aug 17 '11 at 12:07
  • You can even store the last index in a static variable and start the search from this point, since typically, linear interpolation routines are called in a sequential manner. – Alexandre C. Aug 17 '11 at 12:21
  • @Stefan: Looks like it might be placing the data in a r/w segment rather than in read-only segment. Try moving `xs` and `ys` outside of the function, though I doubt that will help. – user786653 Aug 17 '11 at 12:25
  • @user786653 Thank you very much, that seems to work. Now I get my hex File for the µC, but at the moment its still not working correctly. But I will try to find that out. Thanks – Stefan Aug 17 '11 at 12:34
  • it is running, @user786653 thank you very much for your support. You have been a very big help for me. Thanks – Stefan Aug 17 '11 at 16:51
  • @Stefan: Great! :) Since you're new here: remember to upvote the posts you found useful and accept the answer if you think it's adequate. see the [FAQ](http://meta.stackexchange.com/questions/7931/faq-for-stack-exchange-sites) – user786653 Aug 17 '11 at 17:52
  • Thanks, at the moment I have not enough vote your answer up. But I clicked yes for the question if your post was useful. It was very useful so thanks again. – Stefan Aug 17 '11 at 18:14
0

Put all the values in an array. Then search for x.. if you didn't find the correct value you have an index and a neighbour index, then calculate the value using your formula..

duedl0r
  • 9,289
  • 3
  • 30
  • 45