solvePositionFromXValue method

double solvePositionFromXValue(double xVal)

Computes the position t of a point on the curve given its x coordinate. That is, for an input xVal, finds t s.t. getPointX(t) = xVal. As such, the following should always be true up to some small epsilon: t ~ solvePositionFromXValue(getPointX(t)) for t in 0, 1. @param {number} xVal The x coordinate of the point to find on the curve. @return {number} The position t.

Implementation

double solvePositionFromXValue(double xVal)
{
  // Desired precision on the computation.
  double epsilon = 1e-6;

  // Initial estimate of t using linear interpolation.
  double t = (xVal - this.x0) / (this.x3 - this.x0);
  if (t <= 0) {
    return 0;
  }
  else if (t >= 1) {
    return 1;
  }

  // Try gradient descent to solve for t. If it works, it is very fast.
  double tMin = 0;
  double tMax = 1;
  double value = 0;
  for (double i = 0; i < 8; i++)
  {
    value = getPointX(t);
    double derivative = (getPointX(t + epsilon) - value) / epsilon;
    if ( (value - xVal).abs() < epsilon) {
      return t;
    }
    else if ( derivative.abs() < epsilon) {
      break;
    }
    else {
      if (value < xVal) {
        tMin = t;
      }
      else {
        tMax = t;
      }
      t -= (value - xVal) / derivative;
    }
  }

  // If the gradient descent got stuck in a local minimum, e.g. because
  // the derivative was close to 0, use a Dichotomy refinement instead.
  // We limit the number of interations to 8.
  for (double i = 0; (value - xVal).abs() > epsilon && i < 8; i++)
  {
    if (value < xVal) {
      tMin = t;
      t = (t + tMax) / 2;
    } else {
      tMax = t;
      t = (t + tMin) / 2;
    }
    value = getPointX(t);
  }
  return t;
}