在立方Bezier曲线上，已知X求Y如何计算？

Question

在立方Bezier曲线上，已知X求Y如何计算？

c++beziercurvecubic

13

我需要一种方法，能够让我找到三次贝塞尔曲线上的一个点Y坐标，给定X坐标。

我发现很多地方都告诉我要将其视为三次函数然后尝试找到根，这一点我理解。但是三次贝塞尔曲线的方程是（对于x-coords）：

X(t)=(1-t)^3*X0 + 3*(1-t)^2*t*X1 + 3*(1-t)*t^2*X2 + t^3*X3

使我困惑的是添加了(1-t)值。例如，如果我用一些随机数字填充X值：

400=(1-t)^3*100+3*(1-t)^2*t*600+3*(1-t)*t^2*800+t^3*800

然后重新排列：

800t^3+3*(1-t)*800t^2+3*(1-t)^2*600t+(1-t)^3*100-400=0

我仍然不知道(1-t)系数的值。当(1-t)仍然未知时，我该如何解决方程？

- Captain Awesome

1

更多是一个数学问题... - Oliver Charlesworth

1

好的，那我去问数学专业的人。我认为它在计算机领域中使用，所以想这里的人可能会知道。谢谢。 - Captain Awesome

1

即使在2018年，这个问题仍然频繁出现，需要一个真正的答案。因此，我在https://dev59.com/-q3la4cB1Zd3GeqPQrLx#51883347上编写了获取符号解的代码，并提供了第二个答案，给出了不太精确但通常足够好的二分搜索解决方案。 - Mike 'Pomax' Kamermans

5个回答

2

我认为这是一个公平的计算机科学问题，所以我尝试展示我的解决方法。请注意，给定的"x"可能有超过一个与之相关联的"y"值。在我需要它的情况下，保证不存在这种情况，因此您需要确定要选择哪个。

我遍历了"t"生成了一个包含"x"和"y"值的数组。我为了我的目的在相当高的精度下进行了迭代。(我正在寻找生成8位查找表，所以使用了约1000个点) 我只需将"t"插入到贝塞尔方程中，得到下一个"x"和下一个"y"坐标，然后将其存储在数组中。一旦我生成了整个数据，我就扫描数组以查找两个最近的"x"值。(如果有完全匹配，则使用该值。) 然后，我对那个非常小的线段进行线性插值，以获得我所需的"y"值。

- user1118321

1

进一步开发表达式应该可以摆脱 (1 - t) 因子

如果你运行：

expand(800*t^3 + 3*(1-t)*800*t^2 + 3*(1-t)^2*600*t + (1-t)^3*100 -400 = 0);

在wxMaxima或Maple中（尽管在后者中您必须添加参数t），您将获得：

100*t^3 - 900*t^2 + 1500*t - 300 = 0

解决新的三次方程式以求得 t（您可以使用三次方程式公式），在获得 t 后，您可以通过以下方式找到 x：

x = (x4 - x0) * t      (asuming x4 > x0)

- higuaro

0

贝塞尔曲线方程（获取x值）：

Bx = (-t^3 + 3*t^2 - 3*t + 1) * P0x + 
     (3*t^3 - 6*t^2 + 3*t) * P1x + 
     (-3*t^3 + 3*t^2) * P2x + 
     (t^3) * P3x

将其重排为t的三次方式

0  = (-P0x + 3*P1x - 3*P2x + P3x) * t^3+ 
     (3*P0x - 6*P1x + 3*P2x) * t^2 + 
     (-3*P0x + 3*P1x) * t + 
     (P0x) * P3x - Bx

使用三次公式解决此问题，以找到t的值。可能存在多个t的实际值（如果曲线两次穿过相同的x点）。在我的情况下，我处理的是每个x值只有一个y值的情况。因此，我可以将唯一的实根作为t的值。

a = -P0x + 3.0 * P1x - 3.0 * P2x + P3x;
b = 3.0 * P0x - 6.0 * P1x + 3.0 * P2x;
c = -3.0 * P0x + 3.0 * P1x;
d = P0x;
t = CubicFormula(a, b, c, d);

接下来将t的值放回到Bezier曲线中计算y的值

By = (1-t)^3 * P0x + 
     3t(1-t)^2 * P1x + 
     3t^2(1-t) * P2x + 
     t^3 * P3x

- Reuben Carter

“使用三次方程式解决这个问题”是在数学.stackexchange上的一个好答案，但对于Stackoverflow上的C++问题来说则不是。如果没有展示三次公式实现的代码，那么这就是一个不完整的答案。 - Mike 'Pomax' Kamermans

在三次方程式中，最后一项应该是“(P0x) - Bx”而不是“(P0x) * P3x - Bx”吗？并且d的公式应该是“P0x - Bx”，而不仅仅是“P0x”吗？ - BoCoKeith

-1

所以我一直在寻找一种方法，在给定贝塞尔曲线上的x坐标时，能够找到对应的Y坐标。

考虑一个由点(0, 0)和(0, 100)连接的三次贝塞尔曲线，控制点分别为(0, 33)和(0, 66)。对于给定的X值，这里存在无数个Y值。因此，没有任何方程可以解决任意三次贝塞尔曲线中给定X值求解Y值的问题。

为了得到一个稳健的解决方案，你可能需要从德卡斯特利乌算法开始。

通过递归地将曲线分割成各个近似直线的片段，然后可以检测这些线段是否与你所查找的X相交，或者它们是垂直线段，其X值与你所查找的X相符（如上面的例子）。

- MrO

但请记住，仅因为没有通用解决方案，并不意味着所有情况下都没有解决方案。如果曲线是可逆的，则肯定存在解决方案，并且此问题的答案在 https://dev59.com/-q3la4cB1Zd3GeqPQrLx#51883347 中进行了讨论。 - Mike 'Pomax' Kamermans

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Michael Anderson · Accepted Answer

有三种常见的表达立方贝塞尔曲线的方式。

首先，将x表示为t的函数：

x(t) = sum( f_i(t) x_i )
     = (1-t)^3 * x0 + 3*(1-t)^2 * t * x1 + 3*(1-t) * t^2 * x2 + t^3 * x3

其次，将y视为x的函数。

y(x) = sum( f_i(x) a_i )
     = (1-x)^3 * y0 + 3*(1-x)^2 * x * y1 + 3*(1-x) * x^2 * y2 + x^3 * y3

这两个公式从数学上讲是相同的，只是使用了不同的变量名称。

根据您的描述“在三次贝塞尔曲线上找到给定x坐标的Y坐标。”我猜测您正在使用第二个方程式，并试图重新排列第一个方程式来帮助您解决问题，而事实上您应该使用第二个方程式。如果是这种情况，则不需要重新排列或解决-只需将您的x值插入即可得到解决方案。

可能您有一个第三种情况的方程式，这是复杂且困难的情况。其中x和y参数都是第三个变量t的三次贝塞尔曲线方程式。

x(t) = sum( f_i(t) x_i )
y(t) = sum( f_i(t) y_i )

如果这是您的情况，请让我知道，我可以详细说明解决方法。