将二维样条函数 f(t) 转换为 f(x)。

Question

所以我有一组特殊的三次样条曲线控制点，其2D控制点将始终导致曲线在x轴上不会相交。也就是说，这些曲线看起来像简单的多项式函数 y=f(x)。我希望能够有效地创建一个数组，其中包含沿着样条曲线均匀分布的x坐标对应的y坐标，该数组覆盖了样条曲线的整个长度。

我希望能够有效地找到沿着样条曲线的y坐标，例如x = 0.0、x = 0.1、x = 0.2等，或者换句话说，将f_x,y(t)类型的函数有效地转换为f(x)类型的函数。

我目前使用了一个4x4恒定矩阵和四个2D控制点来描述样条曲线，对于Hermite或Catmull-Rom样条，使用矩阵常量，并将它们插入到从0到1的t的三次函数中。

在已知矩阵和控制点的情况下，最好的方法是获取沿着x轴的这些y值是什么？

编辑：我应该补充说明一下，只要能够绘制出足够接近的近似曲线即可。

- vercellop

---

到目前为止，我发现最简单的方法就是在t的常规间隔处从曲线中取样点，然后在x轴上插值以收集f(x)值。这看起来大多数时候都可以，但有时会错过细节，因为很难知道尖角位于何处；增加采样频率有所帮助，但并不完全高效或令人满意。我相信有一种聪明的方式既具有计算效率，又不会丢失细节。 - vercellop

@vervellop，根据您修改后的问题，您目前的方法可能是最好的答案，因此我建议您将其发布为答案，如果没有更好的解决方案出现，您可以最终接受它。如果用户认为这是一个好的/适当的解决方案，他们可以给它点赞。 - MvG

你的问题可能存在矛盾：原始问题要求均匀间隔的 x 坐标，而编辑后需要适用于绘图的解决方案。在出现显著的尖点时，均匀采样可能无法捕捉到这些尖点。因此，我建议您将问题保留为原始状态，因为答案是针对原始问题的。您可能需要提出一个关于绘图问题的新问题，最好详细说明您想要实现的目标，即为什么简单绘制 2D 样条曲线不足够。 - MvG

啊，是的，澄清一下：该模块的输出是一系列均匀间隔的x坐标对应的y位置列表（类似于连续信号的幅度样本）。这里的目标只是生成这些f(x)点，因为我们不进行绘制。显然，使用这种方法将丢失任何比“采样频率”更细的细节 - 这没关系。它们的质量只需要“足够好以供绘制”，但不应错过曲线的任何重要特征。理想情况下，它只需评估曲线不超过~N次即可生成N个点（尽可能少的次数会更好）。 - vercellop

Answer 1

通常，如果数值近似足够好，人们会使用根查找算法（如牛顿法）。

- Jeff Gates

Answer 2

你可以解决 f_x(t)=x 的问题，这将是一个三次方程；虽然很丑陋但仍然可以明确地解决。如果你的样条曲线如你所描述的那样，那么两个解将是共轭复数，因此唯一剩下的解就是要采取的解。使用它来计算 y=f_y(t)。如果你想要精确解，我怀疑你不会有更简单的方法。

你可以使用维基百科上的通用公式来计算三次方程的解。

- MvG

---

谢谢，这很有帮助。确实，我看了一下关于t的解决方案，它们相当丑陋。肯定比我想要大量计算的任何东西都要丑陋。我已经添加了一个适用于绘制曲线作为f(x)函数的近似值就足够了。 - vercellop

@vercellop，我发布了一个链接，其中给出了解决三次方程的公式。 - MvG

Answer 3

您的问题指出您需要均匀分布x坐标，并且近似解也可以。因此，我提议使用以下算法：

• 决定您想要的网格点，例如每0.1个x单位。
• 从l=0和r=1开始。
• 计算fx（l）和fx（r），并考虑由这些端点表示的区间。
  • 如果该区间足够小且仅包含一个网格点，则使用中心参数t=（l+r）/ 2作为此网格点的良好近似值，并将其作为一个元素列表返回。
  • 如果该区间中至少有一个网格点，则使用（l+r）/ 2作为拆分点将其分成两部分，并连接两个计算结果生成的列表。
  • 如果该区间中没有网格点，则跳过当前计算分支，返回空列表。

这将放大网格点，在每个步骤中将参数空间一分为二，并为所有网格点提供适当的参数。

- MvG

---

这是二分法（链接），其中一种根查找方法。请查看维基百科，了解可能适用于类似问题的算法的优缺点，以确定哪些算法效果更好（或更差）。 - Jeff Gates