點序列插值

Question

給定任意的空間點序列，如何在它們之間產生平滑的連續插值？

歡迎使用2D和3D解決方案。產生任意粒度點列表的解決方案以及爲貝塞爾曲線生成控制點的解決方案也值得讚賞。

此外，看到一個迭代解決方案可以接近曲線的早期部分，因爲它可以接收點，所以可以用它來繪製。

Answer 1

Catmull-Rom spline保證通過所有的控制點。我發現這比試圖調整其他類型樣條的中間控制點更爲方便。

這PDF by Christopher Twigg有一個很好的簡要介紹了樣條的數學。最好的總結一句話就是：

的Catmull-ROM花鍵具有C1 連續性，局部控制和 插值，但沒有在 處於其控制 點的凸包。

換一種說法，如果點表示向右急轉彎，則樣條線在向右轉彎之前會左轉（在該文檔中有一個示例圖片）。在這種情況下，在示例矩陣中使用他的tau參數可控制這些轉彎的緊密程度。

這裏是another example與一些可下載的DirectX代碼。

Answer 2

你看過Unix spline命令嗎？這可以被迫做你想做的事嗎？

Answer 3

一種方法是Lagrange polynominal，這是一種產生將經過所有給定數據點的多項式的方法。

在我大學的第一年，我寫了一個小工具來做到這一點在二維，你可以find it on this page，它被稱爲拉格朗日求解器。維基百科的頁面也有一個示例實現。

工作原理是這樣的：您有一個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。然後你有一個遍歷所有點的多項式，現在你可以在這些點之間進行插值。

但請注意，這可能不適合您的目的，因爲它不提供調整曲率等的方法 - 您無法改變一個解決方案。

Answer 4

不幸的是，拉格朗日或其他形式的多項式插值不適用於任意一組點。他們只能在一個維度上工作X

X _我 < X _{i + 1的}

對於arbitary點的集合，例如一個飛機飛行路徑，其中每個點都是（經度，緯度）對，您最好使用當前經度緯度和速度對飛機旅程進行建模。通過調整飛機可以轉彎的速度（角速度），取決於它與下一個航點的距離，您可以獲得平滑的曲線。

由此產生的曲線不會在數學上顯着，也不會給你更多的控制點。然而，不管路點的數量如何，該算法在計算上都是簡單的，並且可以產生任意粒度的內插點列表。它也不要求您提前提供完整的一組點，您可以根據需要簡單地將航點添加到該集的末尾。

Answer 5

有幾種算法用於在一組點之間進行插值（和外插）。你應該檢查出numerical recipes，它們還包括那些算法的C++實現。

Answer 6

谷歌「正交回歸」。

鑑於最小二乘技術試圖儘量減少擬合線和每個f（x）之間的垂直距離，正交回歸最小化垂直距離。

補遺

在嘈雜數據的存在，古老RANSAC算法是值得檢查過。

Answer 7

在3D圖形世界中，NURBS很受歡迎。更多信息很容易搜索到。

Answer 8

你應該看看B-splines。它們比貝塞爾曲線的優勢在於每個部分僅依賴於局部點。因此，移動一個點對遠離曲線的部分沒有影響，「遠處」由樣條曲線的參數決定。

Langrange多項式的問題是添加一個點可能會對曲線上看起來任意的部分產生極端影響;沒有像上面描述的「地方性」。

Answer 9

我想出了同樣的問題，並在前些日子與一些朋友一起實施。我喜歡在github上分享示例項目。

https://github.com/johnjohndoe/PathInterpolation
隨意叉它。