拉格朗日(Lagrange)曲线插值

作者：追风剑情发布于：2017-4-27 23:33 分类：Algorithms

一、Lagrange插值公式

式中，g_i(t)是混合函数。

使用此混合函数，使t=ti时，曲线P(t)通过给定点型值点f(ti)。

任何类型的曲线都可以通过其控制点的线性组合来表示。

例如，当k=2，m0=m1=m2=1时，已知函数f(t)在三个点t0、t1和t2的函数值f(t0)、f(t1)和f(t2)，则二次多项式P(t)为

P(t)=f(t0)g0(t) + f(t1)g1(t) + f(t2)g2(t)

式中，混合函数如下：

g0(t)=[(t-t1)(t-t2)] / [(t0-t1)(t0-t2)]

g1(t)=[(t-t0)(t-t2)] / [(t1-t0)(t1-t2)]

g2(t)=[(t-t0)(t-t1)] / [(t2-t0)(t2-t1)]

代码实现(C#版)

using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Windows.Forms;

namespace TestLine
{
    public partial class Form1 : Form
    {
        public Form1()
        {
            InitializeComponent();
        }

        private void Form1_Load(object sender, EventArgs e)
        {

        }

        protected override void OnPaint(PaintEventArgs e)
        {
            LagrangeCurve curve = new LagrangeCurve();
            curve.input.Add(new Vector2(0, 0));
            curve.input.Add(new Vector2(10, 10));
            curve.input.Add(new Vector2(20, 20));
            curve.input.Add(new Vector2(30, 30));
            curve.input.Add(new Vector2(40, 40));

            curve.input.Add(new Vector2(50, 40));
            curve.input.Add(new Vector2(60, 30));
            curve.input.Add(new Vector2(70, 20));
            curve.input.Add(new Vector2(80, 10));
            curve.input.Add(new Vector2(90, 0));

            for (float x = 0; x <= 90; x++)
            {
                float y = curve.Lerp(x);
                PaintPoint(e, x, y);
            }
        }

        public void PaintPoint(PaintEventArgs e, float x, float y)
        {
            Graphics g = e.Graphics;
            Pen myPen = new Pen(Color.Red, 2);
            g.DrawEllipse(myPen, x, y, 2, 2);
        }
    }

    public class Vector2
    {
        public float x;
        public float y;

        public Vector2(float x, float y)
        {
            this.x = x;
            this.y = y;
        }
    }

    /// <summary>
    /// 拉格朗日曲线插值类
    /// </summary>
    public class LagrangeCurve
    {
        //输入点(即，曲线要经过的点)
        public List<Vector2> keyPoint = new List<Vector2>();

        public float Lerp(float x)
        {
            float y = 0;
            //构建input.Count个混合函数
            for (int i = 0; i < keyPoint.Count; i++)
            {
                float yi = keyPoint[i].y;
                float xi = keyPoint[i].x;
                float yj = 1;
                //每个混合函数需要遍历所有输入点(根据混合函数公式)
                for (int j = 0; j < keyPoint.Count; j++)
                {
                    if (i != j)
                    {
                        float xj = keyPoint[j].x;
                        yj *= (x - xj) / (xi - xj);
                    }
                }
                y += yi * yj;
            }
            return y;
        }
    }
}

运行测试