樣條曲面插補

Question

比方說，我對Z軸

f(x1,y1) = 10 
f(x2,y2) = 12 
f(x3,y3) = 5 
f(x4,y4) = 2 
... 
f(xn,yn) = 21 

現在我希望能夠以接近F（X，Y）定義表面點的n個。我正在尋找一種線性算法，特別是樣條逼近算法。一個示例算法或至少一些指針會很好。

Answer 1

您可以使用您的點作爲貝塞爾曲面（或Bspline）曲面的控制點，尤其是如果(xi, yi)在XY平面中對矩形進行了樣本點。在這方面，沒有涉及的配件。

您將得到的表面將位於您的點的凸包中，並將相交（插入）在邊界{xi, yi}處的點。

如果您想嘗試，This forums posting似乎包含在Matlab簡單的代碼，並且可以使用GuIRIT做同樣的，如果你沒有做Matlab（儘管它需要搞清楚程序的文件格式） 。

Answer 2

這是對線性逼近方法的模糊描述。

1. 確定貴點Voronoi diagram（在平面上的每一個點，找到最近的(x_i,y_i)）
2. 抓住這個雙重拿到Delaunay triangulation：連接(x_i,y_i)和(x_j,y_j)如果點的線段所以(x_i,y_i)和(x_j,y_j)是等距的（並且比任何其他對更接近）。
3. 在每個三角形上，通過三個頂點找到平面。這是您需要的線性插值。

---

下實現在Python前兩個步驟。網格的規律性可能會讓你加快速度（這也可能導致三角測量的混亂）。

import itertools 

""" Based on http://stackoverflow.com/a/1165943/2336725 """ 
def is_ccw(tri): 
    return ((tri[1][0]-tri[0][0])*(tri[1][1]+tri[0][1]) 
      + (tri[2][0]-tri[1][0])*(tri[2][1]+tri[1][1]) 
      + (tri[0][0]-tri[2][0])*(tri[0][1]+tri[2][1])) < 0 

def circumcircle_contains_point(triangle,point): 
    import numpy as np 
    matrix = np.array([ [p[0],p[1],p[0]**2+p[1]**2,1] for p in triangle+point ]) 
    return is_ccw(triangle) == (np.linalg.det(matrix) > 0) 

triangulation = set() 
""" 
A triangle is in the Delaunay triangulation if and only if its circumscribing 
circle contains no other point. This implementation is O(n^4). Faster methods 
are at http://en.wikipedia.org/wiki/Delaunay_triangulation 
""" 
for triangle in itertools.combinations(points,3): 
    triangle_empty = True 
    for point in points: 
     if point in triangle: 
      next 
     if circumcircle_contains_point(triangle,point): 
      triangle_empty = False 
      break 
    if triangle_empty: 
     triangulation.add(triangle) 

Answer 3

不規則二維數據的插值並不那麼容易。我知道不規則的2D沒有真正的樣條泛化。除了基於三角測量的方法，你可以看看巴恩斯（http://en.wikipedia.org/wiki/Barnes_interpolation）和反距離加權（http://en.wikipedia.org/wiki/Inverse_distance_weighting），或更一般地說，RBF（http://en.wikipedia.org/wiki/Radial_basis_functions）。

如果你的觀點是強非均勻擴散（稠密聚類），可能有必要使函數的大小自適應，或求助於近似而不是插值。