曲線擬合飛機上的未分類點

Question

問題：如果飛機上的點沒有單一值，您如何擬合曲線？

對於所示的示例，如何將曲線（如黑色曲線）擬合到嘈雜的藍色數據？它與樣條平滑類似，但我不知道數據的順序。

Matlab的將是優選的，但僞代碼是好的。或者指出這個問題的正確術語是什麼會很好。

謝謝

Answer 1

查看此文章：Shape-preserving least-squares approximation by polynomial parametric spline curves，它似乎目前a解決方案。另外，請參閱最後的參考書目。

Answer 2

你必須做多個分段擬合或樣條曲線。不要指望任何算法能夠一次完成所有的算法。可能至少有三條曲線：第一條到達十字路口，循環，然後從十字路口向前返回。

Answer 3

編輯：nvm誤解了這個問題。無論如何，我會在這裏留下這個答案。

也許嘗試找到點convex hull第一則適合於執行 http://en.wikipedia.org/wiki/Convex_hull_algorithms

平原

http://www.cse.unsw.edu.au/~lambert/java/3d/giftwrap.html < --includes的Java動畫的凸包。如果你不想效率也有一些非常簡單的實現，如禮品包裝版本是O（n^2） http://en.wikipedia.org/wiki/Gift_wrapping_algorithm

分而治之版本是O（nlogn）

Answer 4

根據某些基礎參數t，您的數據看起來像是(x,y)的二維parametric plot。因此，如果你能爲它們想出一個合理的模型，可以做least-squares擬合x(t)和y(t)。您的數據似乎描述了limacon。

Answer 5

這個問題是真的如果你沒有訂購，很難。在某些（x（t），y（t））上做最小二乘是很容易的 - 假設您知道t的排序。

您可能需要一些有點搜索算法。遺傳算法可能沒問題。

Answer 6

您可以嘗試推斷點的順序，然後應用樣條過程。當然，曲線自身存在一個模棱兩可的地方。

也許最天真的方法將是計算Delaunay Triangulation（nlogn時間），從中通過點近似歐幾里德最小距離哈密爾頓週期。你仍然需要弄清楚'結局'在哪裏。從訂購中，您可以應用樣條技術。對於參考，見Finding Hamiltonian Cycles in Delaunay Triangulations Is NP-Complete，或Reinelt對TSP啓發，1992年，或EMST紙在Wikipedia

心連心，

Answer 7

對於使用B樣條可以使用this Matlab包分段近似值。它適用於自動和半手動模式。