線性插值_c語言實作

這是個很簡單的數學工具。有的問題可能就隻需要簡單的數學工具就能解決。

線性插值

線性插值法：是指使用連接配接兩個已知量的直線來确定在這兩個已知量之間的一個未知量的值的方法。

線性插值相比其他插值方式，如抛物線插值，具有簡單、友善的特點。

線性插值可以用來近似代替原函數，也可以用來計算得到查表過程中表中沒有的數值。它是實作精确快速查找表的一種非常好的方法。

設y=f(x) 在x0 和x1上值分别為，y0，y1，求多項式：

y = φ 1 ( x ) = a 0 + a 1 x y=\varphi _1\left( x \right) =a_0+a_1x y=φ1​(x)=a0​+a1​x

滿足：

φ 1 ( x 0 ) = y 0 , φ 1 ( x 1 ) = y 1 \varphi _1\left( x_0 \right) =y_0,\varphi _1\left( x_1 \right) =y_1 φ1​(x0​)=y0​,φ1​(x1​)=y1​

得到

y = φ 1 ( x ) = y 0 + y 1 − y 0 x 1 − x 0 ( x − x 0 ) y=\varphi _1\left( x \right) =y_0+\frac{y_1-y_0}{x_1-x_0}\left( x-x_0 \right) y=φ1​(x)=y0​+x1​−x0​y1​−y0​​(x−x0​)

這樣就能直接得到y。我們需要滿足x在x0和x1之間。假設x不在x0和x1之間，公式也是滿足，叫線性外插。

其實就是一個一進制一次方程，y=kx+b，我們需要計算的就是斜率k，以及截距b。通過這個一進制一次方程去計算區間内的x對應的y。

線性插值舉例

1. ntc電阻測溫度

   ntc的溫度曲線近似成一個數學表達式，但是需要用到math.h中的，占資源，計算慢。可以用線性插值的方法，比如隻需要0-100度。儲存一百個資料，以及對應的adc的值，之後根據測的adc進行插值。

2. 速度規劃

   知道目标速度，加速度，根據這次速度回報，設定下次速度給定。

3. 分段pid

   已知對應速度門檻值的序列，以及對應pid的序列。根據速度回報，或者速度給定，進行插值計算，讓pid的更平滑。

4. 圖像裡的線性插值，雙線性插值，三線性插值。處理二維三維的圖像

還很多。

程式設計

1. 傳入曲線的xy的表格
2. 利用二分法查找區間
3. 利用公式理計算區間内x的值

程式.h:

/***************************************************************
 * @Copyright(C)    2020-2021, wangchongwei
 * @FileName:       linear_interp.h
 * @Author:         wangchongwei
 * @Version:        0.1.1
 * @LastDate:       2021.8.14
 ************************************************************/
#ifndef _LINEAR_INTERP_H_
#define _LINEAR_INTERP_H_
#include <stdint.h>

#ifdef __cplusplus
extern "C" {
#endif

struct LinearInterp
{
	// 初始化曲線
    void (*Init)(struct LinearInterp *self,
                float *arr_x, float *arr_y,
                uint32_t size);    
	// 調用計算
    float (*Cal)(struct LinearInterp *self, float val);

    float out;

    struct 
    {
        float *arr_x;
        float *arr_y;
        int32_t size;
    }pvt;
};

void LinearInterp_Create(struct LinearInterp *self);


#ifdef __cplusplus
}
#endif

#endif
           

/***************************************************************
 * @Copyright(C)    2020-2021, wangchongwei
 * @FileName:       linear_interp.c
 * @Author:         wangchongwei
 * @Version:        0.1.1
 * @LastDate:       2021.8.14
 ************************************************************/

#include "linear_Interp.h"
#include "string.h"

static void _Init(struct LinearInterp *self,
                float *arr_x, float *arr_y,
                uint32_t size)
{
    self->pvt.arr_x = arr_x;
    self->pvt.arr_y = arr_y;
    self->pvt.size = size;
}

static float _Cal(struct LinearInterp *self, float val)
{
    int32_t left = 0, mid = 0;
    int32_t right = self->pvt.size - 1;

    float x0,y0,x1,y1;

    // 二分法
    while (left <= right)
    {
        mid = (left+right)/2;

        if (val<self->pvt.arr_x[mid])
            right = mid - 1;
        else if (self->pvt.arr_x[mid] < val)
            left = mid + 1;
        else 
            break;
    }
    
    // 頭尾檢測
    if (mid == (self->pvt.size - 1)) {
        mid = mid-1;
    }
    else if (mid == 0){
        mid = 0;
    }
    else{
        mid = (self->pvt.arr_x[mid] <= val)?mid:mid-1; // 中間二分查找出現的情況
    }

    // 3.Linear interpolation
    x0 = self->pvt.arr_x[mid];
    y0 = self->pvt.arr_y[mid];
    x1 = self->pvt.arr_x[mid+1];
    y1 = self->pvt.arr_y[mid+1];

    self->out = y0+(((y1-y0)*(val - x0))/(x1-x0));

    return self->out;
}

void LinearInterp_Create(struct LinearInterp *self)
{
    memset(self , 0 , sizeof(struct LinearInterp));

    self->Init = _Init;
    self->Cal = _Cal;
}
           

測試：

float arr_x[5] = {1,5,8,13,17};
    float arr_y[5] = {4,45,10,40,20};
    float res;
    LinearInterp_Create(&line_interp);
    line_interp.Init(&line_interp, arr_x,arr_y,5);
    res = line_interp.Cal(&line_interp,6);
    qDebug()<<"插值結果："<<res;
           

我按1的步長，從-10-30的區間進行插值，畫圖：

代碼肯定還有很多優化的地方，計算時間，記憶體，效率。都應該考慮，但是在考慮都通用的情況下，必然會舍去一些。

比如優化：

提前計算出每個區間的斜率和截距。查找到後，隻需要做一次乘法和加法。

gitee位址：

https://gitee.com/wang_chong_wei/qt_wave.git

被抛棄的寫随筆公衆号改寫技術文章了，感興趣的可以關注公衆号：王崇衛