Creating smooth curves, which pass through points in a path, with cubic bezier curves.

cubic_bezier_spline.dart

import 'dart:ui';

/// Returns control points which can be used to create a bezier path which is smooth at the joins between [knots].
///
/// The result contains one less set of control points than there are [knots]. To construct a path start by moving to
/// the first knot and add cubic bezier segments for the other knots.
///
/// Ported from https://www.codeproject.com/Articles/31859/Draw-a-Smooth-Curve-through-a-Set-of-2D-Offsets-wit
List<List<Offset>> bezierSplineControlOffsets(List<Offset> knots) {
  assert(knots != null);
  assert(knots.length >= 2);

  int n = knots.length - 1;

  // Special case: Bezier curve should be a straight line.
  if (n == 1) {
    // 3P1 = 2P0 + P3
    final firstControlOffsets = <Offset>[
      Offset(
        (2 * knots[0].dx + knots[1].dx) / 3,
        (2 * knots[0].dy + knots[1].dy) / 3,
      )
    ];

    // P2 = 2P1 – P0
    final secondControlOffsets = <Offset>[
      Offset(
        2 * firstControlOffsets[0].dx - knots[0].dx,
        2 * firstControlOffsets[0].dy - knots[0].dy,
      )
    ];
    return [firstControlOffsets, secondControlOffsets];
  }

  // Calculate first Bezier control points
  // Right hand side vector
  final rhs = List<double>(n);

  // Set right hand side X values
  for (int i = 1; i < n - 1; ++i) rhs[i] = 4 * knots[i].dx + 2 * knots[i + 1].dx;
  rhs[0] = knots[0].dx + 2 * knots[1].dx;
  rhs[n - 1] = (8 * knots[n - 1].dx + knots[n].dx) / 2.0;
  // Get first control points dx-values
  final dx = _firstControlOffsets(rhs);

  // Set right hand side dy values
  for (int i = 1; i < n - 1; ++i) rhs[i] = 4 * knots[i].dy + 2 * knots[i + 1].dy;
  rhs[0] = knots[0].dy + 2 * knots[1].dy;
  rhs[n - 1] = (8 * knots[n - 1].dy + knots[n].dy) / 2.0;
  // Get first control points dy-values
  final dy = _firstControlOffsets(rhs);

  // Fill output arradys.
  final firstControlOffsets = List<Offset>(n);
  final secondControlOffsets = List<Offset>(n);
  for (int i = 0; i < n; ++i) {
    // First control point
    firstControlOffsets[i] = Offset(dx[i], dy[i]);
    // Second control point
    if (i < n - 1)
      secondControlOffsets[i] = Offset(
        2 * knots[i + 1].dx - dx[i + 1],
        2 * knots[i + 1].dy - dy[i + 1],
      );
    else
      secondControlOffsets[i] = Offset(
        (knots[n].dx + dx[n - 1]) / 2,
        (knots[n].dy + dy[n - 1]) / 2,
      );
  }

  return [firstControlOffsets, secondControlOffsets];
}

List<double> _firstControlOffsets(List<double> rhs) {
  final n = rhs.length;
  final x = List<double>(n); // Solution vector.
  final tmp = List<double>(n); // Temp workspace.

  var b = 2.0;
  x[0] = rhs[0] / b;

  // Decomposition and forward substitution.
  for (int i = 1; i < n; i++) {
    tmp[i] = 1 / b;
    b = (i < n - 1 ? 4.0 : 3.5) - tmp[i];
    x[i] = (rhs[i] - x[i - 1]) / b;
  }
  for (int i = 1; i < n; i++) x[n - i - 1] -= tmp[n - i] * x[n - i]; // Backsubstitution.

  return x;
}