近似非參數三次貝塞爾

Question

近似三次貝塞爾曲線的最佳方法是什麼？理想情況下，我想要一個函數y（x），它可以給出任意給定x的精確y值，但這將涉及爲每個x值求解一個三次方程，這對於我的需求來說太慢了，並且可能存在數值穩定性問題以及這種方法。

this會是一個很好的解決方案嗎？

Answer 1

只需解決立方。如果你在談論Bezier平面曲線，其中x（t）和y（t）是三次多項式，那麼y（x）可能是未定義的或者有多個值。一個極端退化的情況是行x = 1.0，它可以表示爲一個三次Bezier（控制點2與終點1相同;控制點3與終點4相同）。在這種情況下，y（x）對於x！= 1.0沒有解，對於x == 1.0無窮解。

一個遞歸細分的方法可以工作，但我希望它比僅僅求解立方體要慢得多。 （除非你正在處理某種嵌入式處理器，而且浮點容量異常差）

你應該沒有問題找到解決已被徹底測試過的立方體的代碼。如果你使用遞歸細分來實現你自己的解決方案，那麼你就沒有這個優勢。

最後，是的，可能存在數值穩定性問題，例如當您想要的點接近切線時，但細分方法不會使這些問題消失。這隻會讓他們不太明顯。

編輯：迴應您的評論，但我需要超過300個字符。

我只處理貝塞爾曲線，其中y（x）只有一個（實數）根。關於數值穩定性，使用http://en.wikipedia.org/wiki/Cubic_equation#Summary中的公式，如果u很小，可能會出現問題。 - jtxx000

wackypedia文章是沒有代碼的數學。我懷疑你可以在某處找到一些更易於使用的食譜代碼。也許數字Recipies或ACM收集算法link text。

對於您的具體問題，並使用與文章相同的符號，當p也爲零或接近零時，u僅爲零或接近零。他們通過方程相關：
u^^6 + q u^^3 == p^^3 /27
零點附近，你可以使用近似：
q u^^3 == p^^3 /27
或p/3u == Q的立方根
所以從u x的計算應該包含這樣的：

(fabs(u) >= somesmallvalue) ? (p/u/3.0) : cuberoot (q) 

「接近」零接近？取決於你需要多少準確度。你可以在Maple或Matlab上花費一些質量時間，看看引入了多大的錯誤來確定u的大小。當然，只有你知道你需要多少準確性。

這篇文章給出了3個立方體3根的公式。給定三個u值，你可以得到3個相應的x值。 u和x的3個值都是具有虛部的複數。如果你是肯定必須只有一個真正的解決方案，那麼你期望其中一個根具有零虛構分量，另外兩個是複共軛。它看起來像你必須計算所有三個，然後選擇真正的。 （注意：一個複數u可以對應一個實數x！）但是，這裏還存在另一個數值穩定性問題：浮點算術就是它的實際解，虛實數解不會完全爲零，虛數分量非實根可以任意接近零。因此，數字舍入可能會導致您選擇錯誤的根目錄。如果您的應用程序中存在一些可以在其中應用的完整性檢查，那將會很有幫助。

如果你確實選擇了正確的根，牛頓 - 拉夫森的一個或多個迭代可以提高它的精度。

Answer 2

是的，de Casteljau算法會適合你。但是，我不知道它是否比通過Cardano方法求解三次方程更快。