8

z軸上のサーフェスを定義するn個の点があるとしましょう

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

今、私は f(x,y) を近似できるようにしたいと考えています。線形近似、特にスプライン近似のアルゴリズムを探しています。アルゴリズムの例または少なくともいくつかのポインターは素晴らしいでしょう。

4

3 に答える 3

4

これは、線形近似を作成するためのアプローチのあいまいな説明です。

  1. ポイントのボロノイ図を決定します（平面内のすべてのポイントについて、最も近い を見つけます(x_i,y_i)）
  2. ドロネー三角形分割を取得するには、これの双対を取ります。点の線分がある場合は、(x_i,y_i)と を接続して、とが等距離になるようにします (そして、他のどのペアよりも近くなります)。(x_j,y_j)(x_i,y_i)(x_j,y_j)
  3. 各三角形で、3 つの頂点を通る平面を見つけます。これが必要な線形補間です。

以下は、最初の 2 つのステップを 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)
于 2014-05-05T21:43:37.930 に答える
2

不規則な 2D データの補間はそれほど簡単ではありません。私は、不規則な 2D への真のスプライン一般化を知りません。

三角測量ベースのアプローチの他に、Barnes ( http://en.wikipedia.org/wiki/Barnes_interpolation ) と Inverse Distance Weighting ( http://en.wikipedia.org/wiki/Inverse_distance_weighting )を見ることができます。より一般的には、RBF ( http://en.wikipedia.org/wiki/Radial_basis_functions )。

ポイントが非常に不均一に広がっている (密集したクラスター) 場合は、関数のサイズを適応させるか、補間ではなく近似に頼る必要があります。

于 2014-05-06T08:26:24.620 に答える
1

(xi, yi)特に平面で長方形をサンプリングする場合は、ポイントをベジエ (または B スプライン) サーフェスの制御点として使用できますXY。この点で、フィッティングは関係ありません。

得られるサーフェスは、ポイントの凸包内にあり、 の境界でポイントと交差 (補間) し{xi, yi}ます。

試してみたい場合は、このフォーラムの投稿に簡単なコードが含まれています.MatlabMatlab

于 2012-03-11T17:36:50.060 に答える