generateSamples method

Iterable<Curve2DSample> generateSamples({
  1. double start = 0.0,
  2. double end = 1.0,
  3. double tolerance = 1e-10,
})

Generates a list of samples with a recursive subdivision until a tolerance of tolerance is reached.

Samples are generated in order.

Samples can be used to render a curve efficiently, since the samples constitute line segments which vary in size with the curvature of the curve. They can also be used to quickly approximate the value of the curve by searching for the desired range in X and linearly interpolating between samples to obtain an approximation of Y at the desired X value. The implementation of CatmullRomCurve uses samples for this purpose internally.

The tolerance is computed as the area of a triangle formed by a new point and the preceding and following point.

See also:

Implementation

Iterable<Curve2DSample> generateSamples({
  double start = 0.0,
  double end = 1.0,
  double tolerance = 1e-10,
}) {
  // The sampling algorithm is:
  // 1. Evaluate the area of the triangle (a proxy for the "flatness" of the
  //    curve) formed by two points and a test point.
  // 2. If the area of the triangle is small enough (below tolerance), then
  //    the two points form the final segment.
  // 3. If the area is still too large, divide the interval into two parts
  //    using a random subdivision point to avoid aliasing.
  // 4. Recursively sample the two parts.
  //
  // This algorithm concentrates samples in areas of high curvature.
  assert(end > start);
  // We want to pick a random seed that will keep the result stable if
  // evaluated again, so we use the first non-generated control point.
  final math.Random rand = math.Random(samplingSeed);
  bool isFlat(Offset p, Offset q, Offset r) {
    // Calculates the area of the triangle given by the three points.
    final Offset pr = p - r;
    final Offset qr = q - r;
    final double z = pr.dx * qr.dy - qr.dx * pr.dy;
    return (z * z) < tolerance;
  }

  final Curve2DSample first = Curve2DSample(start, transform(start));
  final Curve2DSample last = Curve2DSample(end, transform(end));
  final List<Curve2DSample> samples = <Curve2DSample>[first];
  void sample(Curve2DSample p, Curve2DSample q, {bool forceSubdivide = false}) {
    // Pick a random point somewhat near the center, which avoids aliasing
    // problems with periodic curves.
    final double t = p.t + (0.45 + 0.1 * rand.nextDouble()) * (q.t - p.t);
    final Curve2DSample r = Curve2DSample(t, transform(t));

    if (!forceSubdivide && isFlat(p.value, q.value, r.value)) {
      samples.add(q);
    } else {
      sample(p, r);
      sample(r, q);
    }
  }
  // If the curve starts and ends on the same point, then we force it to
  // subdivide at least once, because otherwise it will terminate immediately.
  sample(
    first,
    last,
    forceSubdivide: (first.value.dx - last.value.dx).abs() < tolerance && (first.value.dy - last.value.dy).abs() < tolerance,
  );
  return samples;
}