三次贝塞尔曲线-在给定的X处获得Y-在控制点X不断增加的特殊情况下 [英] Cubic bezier curves - get Y for given X - special case where X of control points is increasing

问题描述

我已阅读 a 讨论，关于在X处为三次贝塞尔曲线找到Y，并且还阅读了

I've read a few discussions regarding finding Y at X for a cubic Bezier curve, and have also read this article regarding the matter.

我的案件比一般案件更受限制，我想知道是否有比上述讨论中提到的一般方案更好的解决方案.

My case is more constrained than the general one, and I wonder if there's a better solution than the general ones mentioned in the above discussions.

我的案子:

• 不同的控制点 的X值正在增加. IE: X3 > X2 > X1 > X0.
• 此外，由于上述原因，X(t)也严格单调递增.

• The X value of the different control points is increasing. Ie: X3 > X2 > X1 > X0.
• Also, as a result of above, X(t) is strictly monotonically increasing as well.

有没有一种有效的算法可以将此类约束条件考虑在内?

Is there any efficient algorithm that takes such constraints into account?

推荐答案

首先:该答案仅适用于您，因为您的控制点约束意味着我们始终在处理与常规函数等效的参数.在这种情况下，这显然是您想要的，但是将来找到该答案的任何人都应该意识到，此答案是基于这样的假设，即任何给定的x值都只有一个一个 y值.当然:

First off: this answer only works because your control point constraint means we're always dealing with a parametric equivalent of a normal function. Which is obviously what you want in this case, but anyone who finds this answer in the future should be aware that this answer is based on the assumption that there is only one y value for any given x value. And of course:

对于一般的贝塞尔曲线绝对不是这样

话虽如此，我们知道，即使我们已将该曲线表示为二维的参数曲线，我们仍在处理一条曲线，该曲线对于所有意图和目的都必须具有某种形式为.我们也知道，只要知道唯一地属于特定x的"t"值(这是唯一的情况，因为您严格单调增加的系数属性)，我们就可以将y计算为y = By(t)，因此问题是:给定一些已知的x值，我们能否计算需要插入By(t)的t值?

With that said, we know that—even though we've expressed this curve as a parametric curve in two dimensions—we're dealing with a curve that for all intents and purposes must have some unknown function of the form y = f(x). We also know that as long as we know the "t" value that uniquely belongs to a specific x (which is only the case because of your strictly monotonically increasing coefficients property), we can compute y as y = By(t), so the question is: can we compute the t value that we need to plug into By(t), given some known x value?

答案是:是的，我们可以.

To which the answer is: yes, we can.

首先，可以说我们开始使用的任何x值都来自x = Bx(t)，因此，鉴于我们知道x，我们应该能够找到相应的t值导致该x.

First, any x value we start off with can be said to come from x = Bx(t), so given that we know x, we should be able to find the corresponding value(s) of t that leads to that x.

让我们看一下x(t)的函数:

let's look at the function for x(t):

x(t) = a(1-t)³ + 3b(1-t)²t + 3c(1-t)t² + dt³

我们可以将其重写为简单的多项式形式:

We can rewrite this to a plain polynomial form as:

x(t) = (-a + 3b- 3c + d)t³ + (3a - 6b + 3c)t² + (-3a + 3b)t + a

这是一个标准的三次多项式，只有已知的常数为系数，我们可以轻松地将其重写为:

This is a standard cubic polynomial, with only known constants as coefficients, and we can trivially rewrite this to:

(-a + 3b- 3c + d)t³ + (3a - 6b + 3c)t² + (-3a + 3b)t + (a-x) = 0

您可能想知道对于所有其他值a，b，c和d，所有-x都放在哪里?"答案是它们都被抵消了，所以我们实际上最终唯一需要减去的就是最后一个.方便！

You might be wondering "where did all the -x go for the other values a, b, c, and d?" and the answer there is that they all cancel out, so the only one we actually end up needing to subtract is the one all the way at the end. Handy!

所以现在我们...解决了这个方程:除了t以外，我们都知道一切，我们只需要一些数学见解即可告诉我们如何实现.

So now we just... solve this equation: we know everything except t, we just need some mathematical insight to tell us how to do this.

...当然，这里的"just"当然不是正确的限定词，关于找到三次函数的根没有什么"just"，但值得庆幸的是，

...Of course "just" is not the right qualifier here, there is nothing "just" about finding the roots of a cubic function, but thankfully, Gerolano Cardano laid the ground works to determining the roots back in the 16^th century, using complex numbers. Before anyone had even invented complex numbers. Quite a feat! But this is a programming answer, not a history lesson, so let's get implementing:

给定x的一些已知值，并了解我们的坐标a，b，c和d，我们可以按以下方式实现寻根:

Given some known value for x, and a knowledge of our coordinates a, b, c, and d, we can implement our root-finding as follows:

// Find the roots for a cubic polynomial with bernstein coefficients
// {pa, pb, pc, pd}. The function will first convert those to the
// standard polynomial coefficients, and then run through Cardano's
// formula for finding the roots of a depressed cubic curve.
double[] findRoots(double x, double pa, double pb, double pc, double pd) {
  double
    pa3 = 3 * pa,
    pb3 = 3 * pb,
    pc3 = 3 * pc,
    a = -pa  +   pb3 - pc3 + pd,     
    b =  pa3 - 2*pb3 + pc3, 
    c = -pa3 +   pb3, 
    d =  pa  -     x;

  // Fun fact: any Bezier curve may (accidentally or on purpose)
  // perfectly model any lower order curve, so we want to test 
  // for that: lower order curves are much easier to root-find.
  if (approximately(a, 0)) {
    // this is not a cubic curve.
    if (approximately(b, 0)) {
      // in fact, this is not a quadratic curve either.
      if (approximately(c, 0)) {
        // in fact in fact, there are no solutions.
        return new double[]{};
      }
      // linear solution:
      return new double[]{-d / c};
    }
    // quadratic solution:
    double
      q = sqrt(c * c - 4 * b * d), 
      b2 = 2 * b;
    return new double[]{
      (q - c) / b2, 
      (-c - q) / b2
    };
  }

  // At this point, we know we need a cubic solution,
  // and the above a/b/c/d values were technically
  // a pre-optimized set because a might be zero and
  // that would cause the following divisions to error.

  b /= a;
  c /= a;
  d /= a;

  double
    b3 = b / 3,
    p = (3 * c - b*b) / 3, 
    p3 = p / 3, 
    q = (2 * b*b*b - 9 * b * c + 27 * d) / 27, 
    q2 = q / 2, 
    discriminant = q2*q2 + p3*p3*p3, 
    u1, v1;

  // case 1: three real roots, but finding them involves complex
  // maths. Since we don't have a complex data type, we use trig
  // instead, because complex numbers have nice geometric properties.
  if (discriminant < 0) {
    double
      mp3 = -p/3,
      r = sqrt(mp3*mp3*mp3), 
      t = -q / (2 * r), 
      cosphi = t < -1 ? -1 : t > 1 ? 1 : t, 
      phi = acos(cosphi), 
      crtr = crt(r), 
      t1 = 2 * crtr;
    return new double[]{
      t1 * cos(phi / 3) - b3,
      t1 * cos((phi + TAU) / 3) - b3,
      t1 * cos((phi + 2 * TAU) / 3) - b3
    };
  }

  // case 2: three real roots, but two form a "double root",
  // and so will have the same resultant value. We only need
  // to return two values in this case.
  else if (discriminant == 0) {
    u1 = q2 < 0 ? crt(-q2) : -crt(q2);
    return new double[]{
      2 * u1 - b3,
      -u1 - b3
    };
  }

  // case 3: one real root, 2 complex roots. We don't care about
  // complex results so we just ignore those and directly compute
  // that single real root.
  else {
    double sd = sqrt(discriminant);
    u1 = crt(-q2 + sd);
    v1 = crt(q2 + sd);
    return new double[]{u1 - v1 - b3};
  }
}

好的，那是一段代码，还有很多附加功能:

Okay, that's quite the slab of code, with quite a few additionals:

• crt()是cuberoot函数.实际上，在这种情况下，我们实际上并不关心复数，因此实现此功能的更简单方法是使用def，宏，三元数或您选择的语言提供的任何速记形式:crt(x) = x < 0 ? -pow(-x, 1f/3f) : pow(x, 1f/3f);.
• tau仅为2π.在进行几何编程时，闲逛是很有用的.
• approximately是一种将值与目标周围很小的间隔比较的函数，因为IEEE浮点数是 jerks .基本上，我们在谈论approximately(a,b) = return abs(a-b) < 0.000001之类的东西.

• crt() is the cuberoot function. We actually don't care about complex numbers in this case so the easier way to implement this is with a def, or macro, or ternary, or whatever shorthand your language of choice offers: crt(x) = x < 0 ? -pow(-x, 1f/3f) : pow(x, 1f/3f);.
• tau is just 2π. It's useful to have around when you're doing geometry programming.
• approximately is a function that compares a value to a very small interval around the target because IEEE floating point numerals are jerks. Basically we're talking about approximately(a,b) = return abs(a-b) < 0.000001 or something.

如果有一点Java风格(我正在使用处理这类事情.)

The rest should be fairly self-explanatory, if a little java-esque (I'm using Processing for these kind of things).

使用此实现，我们可以编写实现以在给定x的情况下找到y.与三次调用相比，涉及的内容要多得多，因为立方根是复杂的事物.您最多可以恢复三个根源.但是其中只有一个适用于我们的"t时间间隔" [0,1]:

With this implementation, we can write our implementation to find y, given x. Which is a little more involved than just calling the function because cubic roots are complicated things. You can get up to three roots back. But only one of them will be applicable to our "t interval" [0,1]:

double x = some value we know!
double[] roots = getTforX(x);
double t;
if (roots.length > 0) {
  for (double _t: roots) {
    if (_t<0 || _t>1) continue;
    t = _t;
    break;
  }
}

就这样，我们完成了:现在，我们有了"t"值，可以用来获取相关的"y"值.

And that's it, we're done: we now have the "t" value that we can use to get the associated "y" value.

这篇关于三次贝塞尔曲线-在给定的X处获得Y-在控制点X不断增加的特殊情况下的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！