曲线拟合飞机上的未分类点

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包分段近似值。它适用于自动和半手动模式。