30

问题：如果它们不是单值的，如何将曲线拟合到平面上的点？

对于所示的示例，如何将一条曲线（如黑色曲线）拟合到嘈杂的蓝色数据？它类似于样条平滑，但我不知道数据的顺序。

Matlab 将是首选，但伪代码很好。或者指出这个问题的正确术语是什么会很棒。

谢谢

4

7 回答 7

9

您的数据看起来像一个二维参数图，(x,y)它是某个基础参数的函数t。因此，如果您可以为它们提出合理的模型，则可以进行最小二乘拟合。您的数据似乎描述了一个limacon。x(t)y(t)

于 2009-06-15T00:05:47.327 回答
1

您可以尝试推断点的顺序，然后应用样条程序。当然，曲线与自身相交的地方存在歧义。

也许最简单的方法是计算 Delaunay 三角剖分（nlogn 时间），从中近似得出通过点的欧几里得最小距离哈密顿循环。你仍然需要弄清楚“终点”在哪里。然后，您可以从订购中应用样条技术。如需参考，请参阅Find Hamiltonian Cycles in Delaunay Triangulations Is NP-Complete或 Reinelt 关于 TSP heuristics 的论文，1992 或 Wikipedia 上的 EMST

h,

于 2009-08-28T17:00:04.383 回答
1

编辑：nvm 误解了这个问题。无论如何我都会把这个答案留在这里。

也许尝试先找到点的凸包，然后在平原上拟合凸包

http://www.cse.unsw.edu.au/~lambert/java/3d/giftwrap.html <--包括java实现动画 http://en.wikipedia.org/wiki/Convex_hull_algorithms

如果您不想要效率，有一些非常简单的实现，例如 O(n^2) http://en.wikipedia.org/wiki/Gift_wrapping_algorithm的礼品包装版本

分而治之的版本是 O(nlogn)

于 2009-06-15T00:02:46.117 回答
1

对于使用 B 样条的分段近似，您可以使用这个 Matlab包。它适用于自动和半手动模式。

于 2016-10-11T09:28:56.583 回答
1

我不是这方面的专家，但我找到了这个页面，谈论曲线重建，这似乎符合你的问题。仍在阅读论文并且很难理解它们，所以我还不能提供解决方案。

于 2018-11-16T00:58:21.433 回答
0

您必须进行多个分段拟合或样条曲线。不要指望任何算法能够一次性完成所有操作。至少可以是三条曲线：第一条到交叉点，循环，然后从交叉点向前返回。

于 2009-06-14T23:54:00.333 回答
0

如果你没有订单，这个问题真的很难。对一些(x(t), y(t))做最小二乘很容易——假设你知道t的顺序。

您可能需要某种搜索算法。遗传算法可能没问题。

于 2009-06-16T18:12:14.183 回答