Interpolation

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}]] &) ]

給定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

Unisolvence Theorem

只有唯一一個N-1次多項式(N項多項式,某些項可以為零。講N項比較直覺),剛好符合N個相異函數點。

Underfitting / Overfitting

次方數(講項數比較直覺)不正確,就有許多種符合方式。

高於N項的多項式,太過符合N個相異函數點。存在許多種符合方式。

低於N項的多項式,無法符合N個相異函數點。不存在符合方式,除非運氣好。

演算法(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³)。

數值經過次方,一下子就溢位了;數值範圍很大,解方程組易生誤差。因此這個公式解並不實用。

UVa 12143 12339

演算法(Lagrange Interpolation)

Plot[(12(x-0)(x-3)(x-5)(x-9))/((2-0)(2-3)(2-5)(2-9)), {x, -1, 10}, PlotRange -> {-50,50}, Axes -> False, Mesh -> None]
Plot[InterpolatingPolynomial[{{0,32}, {2,12}, {3,43}, {5,55}, {9,66}}, x], {x, -1, 10}, PlotRange -> {-60,60}, Axes -> False, Mesh -> None]

製作N個N-1次多項式函數,第一個只穿過第一點、其餘點為零,第二個只穿過第二點、其餘點為零,以此類推。相加起來,仍是N-1次多項式函數,而且穿過所有點──正是內插函數。

      N-1         x  - xⱼ
f(x) = ∑  yᵢ  ∏  —————————
      i=0    j≠i  xᵢ - xⱼ
f(0) = 32, f(2) = 12, f(3) = 43, f(5) = 55, f(9) = 66

                  (x-2)(x-3)(x-5)(x-9)
F₀(x) = 32 ⋅ —————————————————————————   只有代入x=0會等於32,
                  (0-2)(0-3)(0-5)(0-9)   代入x=2,3,5,9皆是0。


             (x-0)     (x-3)(x-5)(x-9)
F₁(x) = 12 ⋅ —————————————————————————   只有代入x=2會等於12,
             (2-0)     (2-3)(2-5)(2-9)   代入x=0,3,5,9皆是0。

             (x-0)(x-2)     (x-5)(x-9)
F₂(x) = 43 ⋅ —————————————————————————
             (3-0)(3-2)     (3-5)(3-9)

             (x-0)(x-2)(x-3)     (x-9)
F₃(x) = 55 ⋅ —————————————————————————
             (5-0)(5-2)(5-3)     (5-9)

             (x-0)(x-2)(x-3)(x-5)
F₄(x) = 66 ⋅ —————————————————————————
             (9-0)(9-2)(9-3)(9-5)

f(x) = F₀(x) + F₁(x) + F₂(x) + F₃(x) + F₄(x) 即為所求

時間複雜度分析如下:

一、先備知識:多項式乘法、多項式除法,O(N²)。

二、分子:連乘N項,然後分別除以第一項到第N項,分別得到每道多項式函數的分子。O(N³)。

三、分母與倍率:每道多項式函數分別處理。連乘分母,然後多項式函數的N個係數,分別除以分母。O(N²)。

四、加總:所有多項式函數,對應項係數相加。O(N²)。

時間複雜度為O(N³)。

求得內插函數,顯然非常麻煩!偷懶的方式是不求內插函數,而是直接代入x的數值,時間複雜度為O(N²)。

總結一下。求得內插函數為O(N³),內插函數求值為O(N)。不求內插函數,直接求值為O(N²)。

演算法(Newton Interpolation)

Lagrange Interpolation改成online版本。

遞推法,逐次加入一個新的函數點,即時更新內插函數。一、穿過前n點的內插函數;二、製作只穿過第n+1點,而前n點都是零的函數。兩個函數相加即可。

因為相加之後要穿過第n+1點,所以第二個函數必須調整倍率,以便抵銷第一個函數在第n+1點的影響。

F₀(x) = y₀
                                       i   x    - xⱼ
Fᵢ₊₁(x) = Fᵢ(x) + (yᵢ₊₁ - Fᵢ(xᵢ₊₁)) ⋅  ∏  ———————————
                                      j=0  xᵢ₊₁ - xⱼ
FN-1(x)  即為所求
f(0) = 32, f(2) = 12, f(3) = 43, f(5) = 55, f(9) = 66

F₀(x) = 32

                               (x-0)     (x-3)(x-5)(x-9)
F₁(x) = F₀(x) + (12 - F₀(2)) ⋅ —————————————————————————
                               (2-0)     (2-3)(2-5)(2-9)

                               (x-0)(x-2)     (x-5)(x-9)
F₂(x) = F₁(x) + (43 - F₁(3)) ⋅ —————————————————————————
                               (3-0)(3-2)     (3-5)(3-9)

                               (x-0)(x-2)(x-3)     (x-9)
F₃(x) = F₂(x) + (55 - F₂(5)) ⋅ —————————————————————————
                               (5-0)(5-2)(5-3)     (5-9)

                               (x-0)(x-2)(x-3)(x-5)
F₄(x) = F₃(x) + (66 - F₃(9)) ⋅ —————————————————————————  即為所求
                               (9-0)(9-2)(9-3)(9-5)

總結一下。求得內插函數為O(N³),內插函數求值為O(N)。不求內插函數,直接求值為O(N²)。

演算法(Neville Interpolation)

兩個函數,選兩處x值並且實施線性內插,得到一個函數。

每個函數點分別建立常數函數(零次多項式函數)。兩個零次多項式函數,線性內插,得到一次多項式函數,穿過兩個函數點。兩個一次多項式函數,線性內插,得到二次多項式函數,穿過三個函數點。以此類推。

注意到,以上這些演算法,函數點都不需要按照座標大小排序。

Fᵢᵢ(x) = yᵢ   for i = 0...N-1

          (xⱼ - x) Fᵢ ⱼ₋₁(x) + (x - xᵢ) Fᵢ₊₁ ⱼ(x)
Fᵢⱼ(x) = —————————————————————————————————————————
                   (xⱼ - x) + (x - xᵢ)

f(x) = F₀ N-1(x)  即為所求

Dynamic Programming,子問題是區間,每個子問題[i,j]源自兩個子問題[i-1,j]與[i,j-1],子問題總共O(N²)個。解決一個子問題,需要多項式倍率、多項式加法,時間複雜度為O(N)。總時間複雜度為O(N³)。

總結一下。求得內插函數為O(N³),內插函數求值為O(N)。不求內插函數,直接求值為O(N²)。

Runge Phenomenon

多項式內插有個缺點:函數曲線抖動。

為了緩和曲線,以下繼續介紹其他內插演算法。見招拆招。

Piecewise Polynomial Interpolation

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。

以「相似三角形、邊長等比例」求得輸出值。

        x - a
f(x) = ——————— ⋅ (f(b) - f(a)) + f(a)
        b - a

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}]

輸入值相鄰的函數點,以三次多項式函數銜接。令銜接之處一次導數相同、二次導數相同。

Monotone Cubic Interpolation

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

「單調三次內插」。函數點嚴格遞增(減),內插函數是許多個嚴格遞增(減)三次多項式。其他地方與三次內插相同。

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}]

有時候我們希望內插函數擁有反函數。又要多項式函數、又要反函數,那就只能是嚴格遞增(減)函數了。此時「單調線性內插」、「單調三次內插」能派上用場。

【查無名稱】

兩個相鄰函數點,取附近k個函數點,求得多項式內插函數,然後截取兩個相鄰函數點之間的那一段。

窮舉相鄰函數點,銜接成內插函數。

Catmull-Rom Spline Interpolation

兩個相鄰函數點,取附近4個函數點,以Neville Interpolation求得多項式內插函數,但是遞推最後一步改成中央兩點。其餘同前。

效果是緩和曲線。副作用是4個函數點只穿過中央兩點,導致左右邊界各漏失一段內插函數。解法是在邊界外面補充函數點。

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

二元函數,輸入值形成格點,三次內插只有唯一一種結果,稱做「雙三次內插」。

每個格子,上方兩點做三次內插、下方兩點做三次內插,得到兩點再做三次內插。

改成左方兩點、右方兩點,結果仍相同。

Weighted Average Interpolation

Radial Basis Function Interpolation

RBF是中心對稱的函數。等高線是同心圓。名稱莫名其妙。

實際應用當中,大家視之為「向四周釋放力場的函數」,內高外低。函數造型任君挑選,例如Gaussian Function。

Plot3D[PDF[MultinormalDistribution[{0, 0}, {{1, 0}, {0, 1}}], {x, y}], {x, -3, 3}, {y, -3, 3}, PlotRange -> {0,0.18}, Boxed -> False, Axes -> False, Mesh -> None, ColorFunction -> (ColorData["CherryTones"][Rescale[#3, {-2, 2}]] &) ]

函數點的RBF的加權平均值,做為內插函數。

實際應用當中,挑選一種力場,明定高矮胖瘦。函數點釋放力場,力場乘上權重,調整強弱。疊加力場,得到內插函數。

w0 = Exp[- (x - 0) ^ 2 / 8]; w1 = Exp[- (x - 2) ^ 2 / 8]; w2 = Exp[- (x - 3) ^ 2 / 8]; w3 = Exp[- (x - 5) ^ 2 / 8]; w4 = Exp[- (x - 9) ^ 2 / 8]; f = 149.646 * w0 - 391.202 * w1 + 376.984 * w2 - 62.8542 * w3 + 71.1682 * w4; Plot[f, {x, -1, 10}]

為了穿過所有函數點,需要解方程組,求得權重。

之所以採用加權平均值,正是因為線性方程組容易求解。

Φ(d) = exp(d² / 2σ²)      σ is constant

[ Φ(‖x₀-x₀‖)   Φ(‖x₀-x₁‖)  .. Φ(‖x₀-xN-1‖)   ] [ w₀  ]   [ y₀   ]
[ Φ(‖x₁-x₀‖)   Φ(‖x₁-x₁‖)  .. Φ(‖x₁-xN-1‖)   ] [ w₁  ]   [ y₁   ]
[    :            :                 :        ] [ :   ] = [ :    ]
[    :            :                 :        ] [ :   ]   [ :    ]
[ Φ(‖xN-1-x₀‖) Φ(‖xN-1-x₁‖) .. Φ(‖xN-1-xN-1‖) ] [ wN-1]   [ yN-1 ]

B-spline Interpolation

Neville Interpolation是常數函數(高度是yᵢ)的線性內插。

B-spline是矩形函數(高度是1)的反線性內插(權重互換)。

為了形成山丘:首先高度除以寬度,才做反線性內插;最後高度乘以總寬度,高度還原為1。

函數點的B-spline的加權平均值,做為內插函數。

為了穿過所有函數點,需要解方程組,求得權重。

B-spline是許多個多項式,每遞推一層就升高一次方。遞推層數越多,曲線越平緩。大家習慣遞推三層、得到三次多項式,曲線不會太過平緩,而山峰也恰好對齊函數點。

如同Catmull-Rom Spline,需要在邊界外面補充函數點。

Inverse Distance Weighting Interpolation
(Shepard Interpolation)

距離倒數函數,顧名思義。若想高䠷纖瘦,就取k次方。

Plot3D[1/Norm[{x,y}], {x, -1, 1}, {y, -1, 1}, PlotRange -> {0,15}, Boxed -> False, Axes -> False, Mesh -> None, ColorFunction -> (ColorData["CherryTones"][Rescale[#3, {-2, 2}]] &) ]

函數點的距離倒數函數的加權平均值,做為內插函數。

為了穿過所有函數點,令各個距離倒數函數,穿過自己的函數點,不穿過其餘的函數點,仿效Lagrange Interpolation。

手法:一、各個距離倒數函數除以其總和。二、權重是輸出值。

wᵢ(x) = (1 / ‖x - xᵢ‖)ᵏ   for i = 0...N-1   (k is constant)

w (x) = w₀(x) + w₁(x) + ...

       w₀(x)      w₁(x)             w₀(x) y₀ + w₁(x) y₁ + ... 
f(x) = ————— y₀ + ————— y₁ + ... = ———————————————————————————
       w (x)      w (x)                 w₀(x) + w₁(x) + ...   
w0 = 1/Abs[x]; w1 = 1/Abs[x-2]; w2 = 1/Abs[x-3]; w3 = 1/Abs[x-5]; w4 = 1/Abs[x-9]; w = w0 + w1 + w2 + w3 + w4; f = w0 * 32 + w1 * 12 + w2 * 43 + w3 * 55 + w4 * 66; Plot[f/w, {x, -1, 10}]

再介紹另外一種解讀方式,稍微艱澀。

函數點的常數函數的加權平均值,做為內插函數。

權重不是數值,而是函數──根據內插點位置,決定權重多寡。此處使用距離倒數函數,也可以換成別的函數。

為了穿過所有函數點,權重必須滿足兩個條件:

一、無論內插點在何處,權重總和必須是1。輕鬆解套方式:各權重除以權重總和。

二、當內插點位於函數點,該常數函數的權重必須是1,其餘必須是0。輕鬆解套方式:權重趨近無限大。

Fᵢ(x) = yᵢ                for i = 0...N-1
wᵢ(x) = (1 / ‖x - xᵢ‖)ᵏ   for i = 0...N-1   (k is constant)

        w₀(x) F₀(x) + w₁(x) F₁(x) + ... 
f(x) = —————————————————————————————————
              w₀(x) + w₁(x) + ...       

Weighted Average Coordinates

Weighted Average Coordinates【尚無專有名詞】
註:少數文獻稱作Natural Coordinate System

運用加權平均值,創建座標系!

釘選數點,設定權重,令權重總和為一。

座標變點:給座標(權重),求點(加權平均值)。

點變座標:給點(加權平均值),求座標(權重)。

座標與點必須一一對應。以二維空間為例:兩點以下,不存在任何權重格式,可滿足一一對應;三點只有一種;四點以上有多種。

原理是Unisolvence Theorem。這裡就不證明了。

Barycentric Coordinates

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

「重心座標」。三個點,權重是對面的面積比重。

座標變點:三個頂點的加權平均值。

點變座標:三塊小三角形的面積比重。

Bilinear Interpolation

「雙線性內插」。四個點,權重是斜對角的面積比重。由於是矩形,兩個維度可以分開處理,權重是對面線段的長度比重。

座標變點:下方兩點做線性內插、左方兩點做線性內插。

點變座標:線段長度比重。

Quadrilateral Interpolation

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

「四邊形內插」。四個點,權重是斜對角的面積比重。由於權重太複雜,於是權重簡化為新參數。

座標變點:四個頂點的加權平均值。

點變座標:如連結。移項整理之後,解二次方程式。

Quadrilateral Interpolation

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

另一種「四邊形內插」。四個點,權重是對面邊界的距離比重。

座標變點:四個頂點的加權平均值。

點變座標:如連結。

Wachspress Coordinates

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

座標變點:星狀多邊形頂點(有順序)的加權平均值。

點變座標:如連結。

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。新舊交集面積,當作權重。