Question

Interpolation

“内插”就是找一个函数，完全符合手边的一堆数据。此函数称作“内插函数”。

换句话说，找到一个函数，穿过所有给定的函数点。外观就像是在相邻的函数点之间，插满函数点，因而得名“内插”。

这裡谈的是用函数符合数据们，主角是函数，所以会把数据对应到函数的格式。

Spline Interpolation

概论

Piecewise：切成小段、分开处理。形容词。

Spline：切成小段、分开处理，而且是多项式。名词。

内插时，不考虑全部的函数点，只考虑附近的函数点。

Nearest Neighbor Interpolation

“近邻内插”。内插函数是许多个零次多项式。

Plot3D[Nearest[{{2,5},{5,4},{6,7},{1,2},{4,2}}->{3,4,2,1,0}, {x,y}], {x,0,10}, {y,0,10}, ColorFunction -> "Rainbow"]

n = Nearest[{{2,5},{5,4},{6,7},{1,2},{4,2}}->{3,4,2,1,0}]; Plot3D[n[{x,y}], {x,0,10}, {y,0,10}, PlotRange -> {0, 8}, Boxed -> False, Axes -> False, Mesh -> None, NormalsFunction -> None, PlotPoints -> 100, ColorFunction -> (ColorData["CherryTones"][Rescale[#3, {-4, 4}]] &)]

根据输入值，找到最接近的函数点，取其输出值。俯瞰即“ Voronoi Diagram ”。

简单来说，就是找到最近的函数点，然后设定成一样。

Linear Interpolation

“线性内插”。内插函数是许多个一次多项式。

p = {{2,3,3},{5,4,5},{6,6,6},{1,2,1},{4,2,0},{0,4,1},{1,7,1},{0,7,4},{10,10,2},{0,0,1},{0,10,2},{9,1,0}}; m = DelaunayMesh[ p[[All,1;;2]] ]; r = MeshRegion[p, Style[MeshCells[m, 2], {ColorData["CherryTones"][0.5], EdgeForm[Directive[Pink]]}]]; Show[ Plot3D[0, {x, 0, 10}, {y, 0, 10}, PlotRange -> {0, 7}, PlotStyle -> Opacity[0], BoundaryStyle -> None, Boxed -> False, Axes -> False, Mesh -> None], r ]

p = {{2,3,3},{5,4,5},{6,6,6},{1,2,1},{4,2,0},{0,4,1},{1,7,1},{0,7,4},{10,10,2},{0,0,1},{0,10,2},{9,1,0}}; q = Transpose[{ p[[All,1;;2]] , p[[All,3]] }]; f = Interpolation[q, InterpolationOrder->1]; Plot3D[f[x,y], {x, 0, 10}, {y, 0, 10}, PlotRange -> {0, 7}, Boxed -> False, Axes -> False, Mesh -> None, PlotPoints -> 100, ColorFunction -> (ColorData["CherryTones"][Rescale[#3, {-4, 4}]] &)]

输入值相邻的函数点，以直线连接。俯瞰即“ Triangulation ”，有许多种选择，其中最美观的是 Delaunay Triangulation。

简单来说，就是找旁边的两个函数点，以“相似三角形、边长等比例”求得输出值。过程类似于“ 两直线交点 ”。

already known (x1, y1) (x2, y2)
given x , get f(x)

        x  - x1
f(x) = --------- * (y2 - y1) + y1
        x2 - x1

Cubic Interpolation

“三次内插”。内插函数是许多个三次多项式。

f = Interpolation[{{20,85},{40,30},{65,70},{90,120},{105,40},{115,95},{130,45},{140,150},{145,125},{175,115}}]; Plot[f[x], {x, 0, 200}, PlotRange -> {-50, 200}]

输入值相邻的函数点，以三次多项式函数衔接。令衔接之处一次导数相同、二次导数相同。

http://par.cse.nsysu.edu.tw/~homework/algo01/9031636/new_page_2.htm

Monotone Cubic Interpolation

“单调三次内插”。函数点严格递增（减），内插函数是许多个严格递增（减）三次多项式。其他地方与三次内插相同。

p = {{20,85},{40,30},{65,70},{90,120},{105,40},{115,95},{130,45},{140,150},{145,125},{175,115}}; q = Transpose[{ p[[All,1]] , Sort[p[[All,2]]] }] f = Interpolation[q]; Plot[f[x], {x, 0, 200}, PlotRange -> {-50, 200}]

有时候我们希望内插函数拥有反函数。又要多项式函数（连续函数）、又要反函数（一对一函数），那就只能是严格递增（减）函数了。此时“单调线性内插”、“单调三次内插”能派上用场。

http://math.stackexchange.com/questions/45218/

Bilinear Interpolation

二元函数，令函数点排列整齐于格点上，线性内插便只有一种可能，称做“双线性内插”。

经常应用于图片处理。因为图片像素排列整齐于格点上。

https://en.wikipedia.org/wiki/Bilinear_interpolation

q = {{{1,1},0},{{1,2},0},{{1,3},4},{{1,4},1},{{1,5},1},{{2,1},4},{{2,2},3},{{2,3},4},{{2,4},1},{{2,5},0},{{3,1},1},{{3,2},0},{{3,3},0},{{3,4},4},{{3,5},3},{{4,1},2},{{4,2},3},{{4,3},4},{{4,4},0},{{4,5},1},{{5,1},3},{{5,2},3},{{5,3},0},{{5,4},1},{{5,5},2}}

n = 5; p1 = Tuples[Range[n], 2]; p2 = RandomInteger[4,n*n]; q = Transpose[{p1,p2}]; f = Interpolation[q, InterpolationOrder->1]; g1 = Plot3D[f[x,y], {x, 1, n}, {y, 1, n}, PlotRange -> {0, 7}, Boxed -> False, Axes -> False, Mesh -> (n-2), PlotPoints -> 50, ColorFunction -> (ColorData["CherryTones"][Rescale[#3, {-4, 4}]] &)]; q2 = Transpose[{p1[[All,1]],p1[[All,2]],p2}]; g2 = Graphics3D[{Black, Ball[q2, 0.1]}]; Show[g1,g2]

Bicubic Interpolation

二元函数，令函数点排列整齐于格点上，三次内插便只有一种可能，称做“双三次内插”。

https://en.wikipedia.org/wiki/Bicubic_interpolation

Polynomial Interpolation

Polynomial Interpolation

“多项式内插”。内插函数採用多项式函数。同时考虑全部的函数点。

f = InterpolatingPolynomial[{{{2,5},3},{{5,4},4},{{6,7},2},{{1,2},1},{{4,2},0},{{0,4},3},{{2,6},2},{{9,1},1}},{x,y}]; Plot3D[f, {x, 0, 10}, {y, 0, 7}, PlotRange -> {-10, 10}, Boxed -> False, Axes -> False, Mesh->None, ColorFunction -> (ColorData["CherryTones"][Rescale[#3, {-2, 2}]] &) ]

Unisolvence Theorem

只有唯一一个 N-1 次多项式（N 项多项式，某些项可以为零。讲 N 项比较直觉），刚好符合 N 个不同函数点。

多项式内插即是：给定 N 个函数点，找到 N 个多项式係数。

给定 N 个函数点
(x₀ f(x₀)), (x₁ f(x₁)), ... , (xN-1 f(xN-1))

内插函数是 N 项多项式函数（N-1 次多项式函数）
f(x) = c₀ + c₁ x¹ + ... + cN-1 xN-1

目标是找到 N 个係数
c₀ c₁ ... cN-1

演算法（Vandermonde Matrix）

5 个函数点
f(0) = 32, f(2) = 12, f(3) = 43, f(5) = 55, f(9) = 66

内插函数是 4 次多项式，一共 5 项
f(x) = c₀ x⁰ + c₁ x¹ + c₂ x² + c₃ x³ + c₄ x⁴

内插就是满足
f(0) = 0⁰ c₀ + 0¹ c₁ + 0² c₂ + 0³ c₃ + 0⁴ c₄ = 32
f(2) = 2⁰ c₀ + 2¹ c₁ + 2² c₂ + 2³ c₃ + 2⁴ c₄ = 12
f(3) = 3⁰ c₀ + 3¹ c₁ + 3² c₂ + 3³ c₃ + 3⁴ c₄ = 43
f(5) = 5⁰ c₀ + 5¹ c₁ + 5² c₂ + 5³ c₃ + 5⁴ c₄ = 55
f(9) = 9⁰ c₀ + 9¹ c₁ + 9² c₂ + 9³ c₃ + 9⁴ c₄ = 66

写成线性变换的模样
[ 0⁰ 0¹ 0² 0³ 0⁴ ] [ c₀ ]   [ 32 ]
[ 2⁰ 2¹ 2² 2³ 2⁴ ] [ c₁ ]   [ 12 ]
[ 3⁰ 3¹ 3² 3³ 3⁴ ] [ c₂ ] = [ 43 ]
[ 5⁰ 5¹ 5² 5³ 5⁴ ] [ c₃ ]   [ 55 ]
[ 9⁰ 9¹ 9² 9³ 9⁴ ] [ c₄ ]   [ 66 ]

求得多项式係数             -1
[ c₀ ]   [ 0⁰ 0¹ 0² 0³ 0⁴ ] [ 32 ]
[ c₁ ]   [ 2⁰ 2¹ 2² 2³ 2⁴ ] [ 12 ]
[ c₂ ] = [ 3⁰ 3¹ 3² 3³ 3⁴ ] [ 43 ]
[ c₃ ]   [ 5⁰ 5¹ 5² 5³ 5⁴ ] [ 55 ]
[ c₄ ]   [ 9⁰ 9¹ 9² 9³ 9⁴ ] [ 66 ]

多项式係数有唯一解的条件，就是 x=0,2,3,5,9 是五个不同数字。

N 个函数
(x₁ f(x₀)), (x₁ f(x₁)), ... , (xN-1 f(xN-1))

内插函数
f(x) = c₀ + c₁ x¹ + ... + cN-1 xN-1

内插就是满足
f(x₀)   = c₀ + c₁ x₀¹  + ... + cN-1 x₀N-1  
f(x₁)   = c₀ + c₁ x₁¹  + ... + cN-1 x₁N-1  
  :             :
f(xN-1) = c₀ + c₁ xN-1¹ + ... + cN-1 xN-1N-1

写成线性变换的模样
[ 1 x₀¹   .. x₀N-1   ] [ c₀  ]   [ f(x₀)   ]
[ 1 x₁¹   .. x₁N-1   ] [ c₁  ]   [ f(x₁)   ]
[ : :        :       ] [ :   ] = [   :     ]
[ : :        :       ] [ :   ]   [   :     ]
[ 1 xN-1¹ .. xN-1N-1 ] [ cN-1 ]   [ f(xN-1) ]

         A             c      =   y

向量 c 有唯一解的条件，就是 x₀到 xN-1都不同。
换句话说，一开始给定的 N 个函数点，X 座标都不同。
顺便证明了 Unisolvence Theorem。

十分漂亮的公式解，时间複杂度等同高斯消去法 O(N^3)。

数值经过次方，一下子就溢位了；数值范围很大，解方程组易生误差。因此这个公式解并不实用。

Weighted Average Interpolation

概论

以函数点的加权平均值，当作内插点。权重有许多种设定方式。

Linear Interpolation

“线性内插”。两个点，以另一端的线段长度做为权重。

Quadrilateral Interpolation【尚无正式名称】

“四边形内插”。线性内插的二维版本。四个点，以斜对角的面积做为权重。

上方两点做线性内插、下方两点做线性内插，然后方才得到的两点做线性内插。

当函数点整齐排列于格点上，即是 Bilinear Interpolation。

Barycentric Interpolation

“重心内插”。退化成三个点，以对面的面积做为权重。

Inverse Distance Weighting

所有点，以距离的倒数做为权重。

Natural Neighbor Interpolation

函数点形成 Voronoi Diagram，加入内插点形成新的 Voronoi Diagram。所有邻点，以内插点侵占的面积做为权重。

Weighted Average Coordinates

Natural Coordiniate System

使用几何元件来建立的座标系统。

Weighted Average Coordinates【尚无专有名词】

运用加权平均值，创建座标系！

钉选数点（数字）。令权重总和为一。

正向：给座标（权重），求点（加权平均值）。

逆向：给点（加权平均值），求座标（权重）。

coordinate                point
(1, 0, 0, 0, 0)       --> p0 (-3, 3)
(0, 1, 0, 0, 0)       --> p1 (-0.5, -2)
(0, 0, 1, 0, 0)       --> p2 (2, 4)
(0, 0, 0, 1, 0)       --> p3 (3.5, -3.5)
(0, 0, 0, 0, 1)       --> p4 (-3, -3.5)
(0, 0.5, 0.3, 0.2, 0) --> p  (1.05, -0.5)

Barycentric Coordinates

https://classes.soe.ucsc.edu/cmps160/Fall10/resources/barycentricInterpolation.pdf

“重心座标”。钉选三个点，建立座标系。

正向：三个顶点的加权平均值。

反向：如连结。三块小三角形面积的比例。

Wachspress Coordinates

钉选四点以上，有许多种权重组合，得到同一点──无法订立座标系，座标与点必须是一对一对应。我们需要限制权重的格式，以制造一对一对应。

留给读者一个不那麽重要的问题：尝试以线性代数的角度，解释为何有许多种权重组合，得到同一点。

http://128.148.32.110/courses/cs224/papers/mean_value.pdf

“Wachspress 座标”。钉选星状多边形（点有顺序），建立座标系。

正向：简单多边形顶点的加权平均值。

反向：如连结。

Mean Value Coordinates

http://www.mn.uio.no/math/english/people/aca/michaelf/papers/barycentric.pdf

“均值座标”。钉选简单多边形（点有顺序），建立座标系。

正向：简单多边形顶点的加权平均值。

反向：如连结。

Laplace Coordinates

http://www-umlauf.informatik.uni-kl.de/~bobach/work/publications/dagstuhl06.pdf

加入该点，形成的新 Voronoi Diagram，毗邻区域的衔接处（二维是长度、三维是面积），除以距离，当作权重。

Natural Neighbor Coordinates

http://www-umlauf.informatik.uni-kl.de/~bobach/work/publications/dagstuhl06.pdf

新 Voronoi Diagram 的该点区域、原 Voronoi Diagram 的毗邻区域，两者的交集面积，当作权重。

容易推算梯度。

Bilinear Interpolation

“双线性内插”。宛如二维座标系。一个长方形，取左下顶点为原点，下边长度定为 1，左边长度定为 1，两个维度使用两个权重。

“双线性内插”不是“所有点的加权平均值”的形式，脱离本章主旨。介绍它，是为了替下个小节“四边形内插”铺路。

Quadrilateral Interpolation

“四边形内插”有多种方式。除了方才介绍的“Wachspress 座标”和“均值座标”等，以下再介绍两个常见的方法。

仿照“重心座标”与“双线性内插”的精神，每个点取对顶的小矩形面积，四块面积比例当作权重，塑造加权平均值的格式。

https://www.particleincell.com/2012/quad-interpolation/

正向：四个顶点的加权平均值，权重由两个参数塑成。预先解联立方程式，以得到参数。

反向：如连结。移项整理之后，解二次方程式。

Quadrilateral Interpolation

http://crpit.com/confpapers/CRPITV11Halim.pdf

另一种“四边形内插”。

正向：四个顶点的加权平均值，权重由四个边界距离塑成。

反向：如连结。