Introduce a maximum depth for markup evaluation

[lilypond.git] / lily / bezier.cc

diff --git a/lily/bezier.cc b/lily/bezier.cc
index f230d1057d49b0ddb608f87af9d65b9eedbadc70..0a0f4cfc6ff3f18962548c44bf391e9ba99762ad 100644 (file)
--- a/lily/bezier.cc
+++ b/lily/bezier.cc
@@ -81,6 +81,17 @@ Bezier::get_other_coordinate (Axis a, Real x) const
   return curve_coordinate (ts[0], other);
 }
 
+vector<Real>
+Bezier::get_other_coordinates (Axis a, Real x) const
+{
+  Axis other = other_axis (a);
+  vector<Real> ts = solve_point (a, x);
+  vector<Real> sols;
+  for (vsize i = 0; i < ts.size (); i++)
+    sols.push_back (curve_coordinate (ts[i], other));
+  return sols;
+}
+
 Real
 Bezier::curve_coordinate (Real t, Axis a) const
 {
@@ -202,6 +213,61 @@ Bezier::solve_point (Axis ax, Real coordinate) const
   return filter_solutions (sol);
 }
 
+/**
+   Assuming AX is X_AXIS, and D is UP, finds the
+   maximum value of curve_coordinate(t, Y_AXIS) subject to
+   l <= curve_coordinate(t, X_AXIS) <= r.
+*/
+Real
+Bezier::minmax (Axis ax, Real l, Real r, Direction d) const
+{
+  Axis other = other_axis (ax);
+  Interval lr (l, r);
+  vector<Real> solutions;
+
+  // Possible solutions are:
+  // t = 0 or 1, or...
+  solutions.push_back (0);
+  solutions.push_back (1);
+
+  // t is a critical point for the other-axis polynomial, or...
+  Polynomial p_prime (polynomial (other));
+  p_prime.differentiate ();
+  vector<Real> criticals = p_prime.solve ();
+  solutions.insert (solutions.end (), criticals.begin (), criticals.end ());
+
+  // t solves curve_coordinate(t, X_AXIS) = l or r.
+  Direction dir = LEFT;
+  do
+    {
+      Polynomial p (polynomial (ax));
+      p.coefs_[0] -= lr[dir];
+
+      vector<Real> sol = p.solve ();
+      solutions.insert (solutions.end (), sol.begin (), sol.end ());
+    }
+  while (flip (&dir) != LEFT);
+
+  Polynomial p (polynomial (ax));
+  Polynomial other_p (polynomial (other));
+  vector<Real> values;
+  for (vsize i = solutions.size (); i--;)
+    {
+      Real t = solutions[i];
+      if (t >= 0 && t <= 1 && p.eval (t) >= l && p.eval (t) <= r)
+        values.push_back (other_p.eval (t));
+    }
+
+  if (values.empty ())
+    {
+      programming_error ("no solution found for Bezier intersection");
+      return 0.0;
+    }
+
+  vector_sort (values, less<Real> ());
+  return (d == DOWN) ? values[0] : values.back ();
+}
+
 /**
    Compute the bounding box dimensions in direction of A.
 */