質問

空間内の任意の点のシーケンスが与えられた場合、それらの間のスムーズな連続補間をどのように生成しますか?

2D および 3D ソリューションは大歓迎です。任意の粒度で点のリストを生成するソリューションや、ベジェ曲線の制御点を生成するソリューションも高く評価されます。

また、ポイントを受け取ったときに曲線の初期セクションを近似できる反復ソリューションがあれば、それを使って描画できるのも素晴らしいでしょう。

役に立ちましたか？

解決

の Catmull-Rom スプライン すべてのコントロール ポイントを通過することが保証されています。これは、他のタイプのスプラインの中間制御点を調整するよりも便利だと思います。

これ クリストファー・ツイッグによる PDF スプラインの数学についての簡単な紹介が含まれています。最適な要約文は次のとおりです。

CatMull-ROMスプラインは、C1の連続性、局所制御、および補間を持っていますが、それらの制御点の凸式船体内にはありません。

別の言い方をすると、点が右への急な曲がりを示している場合、スプラインは右に曲がる前に左にバンクします (そのドキュメントに例の図があります)。これらのターンのきつさは制御可能であり、この場合は行列例のタウ パラメーターを使用します。

ここは もう一つの例 ダウンロード可能な DirectX コードが含まれています。

他のヒント

1つの方法は、 ラグランジュ多項式, これは、指定されたすべてのデータ点を通過する多項式を生成する方法です。

大学の 1 年目に、これを 2D で行うための小さなツールを書きました。 このページで見つけてください, 、それはラグランジュソルバーと呼ばれます。Wikipedia のページにはサンプル実装もあります。

その仕組みは次のとおりです。n 次の多項式があります。 p(x), ここで、n は所有しているポイントの数です。それは形を持っています a_n x^n + a_(n-1) x^(n-1) + ...+ a_0, 、 どこ _ 下付き文字です、 ^ 力です。次に、これを一連の連立方程式に変換します。

p(x_1) = y_1
p(x_2) = y_2
...
p(x_n) = y_n

上記を拡張行列に変換し、係数を求めます。 a_0 ... a_n. 。これで、すべての点を通過する多項式が得られ、点間を補間できるようになります。

ただし、曲率などを調整する方法がないため、これは目的に合わない可能性があることに注意してください。変更できない単一の解決策に行き詰まっています。

見てみるといいよ B スプライン. 。ベジェ曲線に対する利点は、各部分がローカル点のみに依存することです。したがって、点を移動しても、遠くにあるカーブの部分には影響しません。「遠くにある」はスプラインのパラメータによって決まります。

ラングランジュ多項式の問題は、点を追加すると、曲線の一見任意の部分に極端な影響を与える可能性があることです。上記のような「地域性」はありません。

Unixを見たことがありますか スプライン 指示？それはあなたが望むことを強制することができますか？

任意の (ただし最終的な) 点セット間を内挿 (および外挿) するためのアルゴリズムがいくつかあります。チェックアウトする必要があります 数値レシピ, 、それらのアルゴリズムの C++ 実装も含まれています。

残念ながら、ラグランジュまたは他の形式の多項式補間は、任意の点のセットでは機能しません。それらは 1 次元のセットでのみ機能します。バツ

バツ私 < xi+1

任意の点のセットの場合、たとえば飛行機の飛行経路では、各点が (経度、緯度) のペアになっているため、現在の経度、緯度、速度を使用して飛行機の移動を単純にモデル化する方が良いでしょう。次のウェイポイントにどれだけ近いかに応じて飛行機の回転速度 (角速度) を調整することで、滑らかな曲線を実現できます。

結果の曲線は数学的に重要ではなく、ベジェ制御点も得られません。ただし、アルゴリズムはウェイポイントの数に関係なく計算的には単純で、任意の粒度でポイントの内挿リストを生成できます。また、事前にポイントの完全なセットを提供する必要はなく、必要に応じてセットの最後にウェイポイントを追加するだけで済みます。

先日、私も同じ問題を思いつき、友達と一緒に実装しました。サンプルプロジェクトを github で共有したいと思います。

PathInterpolation screenshot

https://github.com/johnjohndoe/PathInterpolation
ご自由にフォークしてください。

Googleの「直交回帰」。

最小二乗法ではフィット ラインと各 f(x) の間の垂直距離を最小化しようとしますが、直交回帰では垂直距離が最小化されます。

補遺

ノイズの多いデータが存在する場合、 ランサック アルゴリズムもチェックする価値があります。

3D グラフィックスの世界では、NURBS が人気です。さらに詳しい情報はグーグルで簡単に検索できます。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top