+ notes above and below the interval covered by 1st and last note.
+ */
+ for (vsize i = 1; i + 1 < positions.size (); i++)
+ {
+ above = above || (positions[i] > covering[UP]);
+ below = below || (positions[i] < covering[DOWN]);
+ }
+
+ concave = concave || (above && below);
+ /*
+ A note as close or closer to the beam than begin and end, but the
+ note is reached in the opposite direction as the last-first dy
+ */
+ int dy = positions.back () - positions[0];
+ int closest = max (beam_dir * positions.back (), beam_dir * positions[0]);
+ for (vsize i = 2; !concave && i + 1 < positions.size (); i++)
+ {
+ int inner_dy = positions[i] - positions[i - 1];
+ if (sign (inner_dy) != sign (dy)
+ && (beam_dir * positions[i] >= closest
+ || beam_dir * positions[i - 1] >= closest))
+ concave = true;
+ }
+
+ bool all_closer = true;
+ for (vsize i = 1; all_closer && i + 1 < positions.size (); i++)
+ {
+ all_closer = all_closer
+ && (beam_dir * positions[i] > closest);
+ }
+
+ concave = concave || all_closer;
+ return concave;
+}
+
+Real
+calc_positions_concaveness (vector<int> const &positions, Direction beam_dir)
+{
+ Real dy = positions.back () - positions[0];
+ Real slope = dy / Real (positions.size () - 1);
+ Real concaveness = 0.0;
+ for (vsize i = 1; i + 1 < positions.size (); i++)
+ {
+ Real line_y = slope * i + positions[0];
+
+ concaveness += max (beam_dir * (positions[i] - line_y), 0.0);
+ }
+
+ concaveness /= positions.size ();
+
+ /*
+ Normalize. For dy = 0, the slope ends up as 0 anyway, so the
+ scaling of concaveness doesn't matter much.
+ */
+ if (dy)
+ concaveness /= fabs (dy);
+ return concaveness;
+}
+
+Real
+Beam_scoring_problem::calc_concaveness ()
+{
+ SCM conc = beam_->get_property ("concaveness");
+ if (scm_is_number (conc))
+ return scm_to_double (conc);
+
+ if (is_knee_)
+ return 0.0;
+
+ Direction beam_dir = CENTER;
+ for (vsize i = is_normal_.size (); i--;)
+ if (is_normal_[i] && stem_infos_[i].dir_)
+ beam_dir = stem_infos_[i].dir_;
+
+ if (normal_stem_count_ <= 2)
+ return 0.0;
+
+ vector<int> close_positions;
+ vector<int> far_positions;
+ for (vsize i = 0; i < is_normal_.size (); i++)
+ if (is_normal_[i])
+ {
+ /*
+ For chords, we take the note head that is closest to the beam.
+
+ Hmmm.. wait, for the beams in the last measure of morgenlied,
+ this doesn't look so good. Let's try the heads farthest from
+ the beam.
+ */
+
+ close_positions.push_back ((int) rint (head_positions_[i][beam_dir]));
+ far_positions.push_back ((int) rint (head_positions_[i][-beam_dir]));
+ }
+
+ Real concaveness = 0.0;
+
+ if (is_concave_single_notes (beam_dir == UP ? close_positions : far_positions, beam_dir))
+ {
+ concaveness = 10000;
+ }
+ else
+ {
+ concaveness = (calc_positions_concaveness (far_positions, beam_dir)
+ + calc_positions_concaveness (close_positions, beam_dir)) / 2;
+ }
+
+ return concaveness;
+}
+
+void
+Beam_scoring_problem::slope_damping ()
+{
+ if (normal_stem_count_ <= 1)
+ return;
+
+ SCM s = beam_->get_property ("damping");
+ Real damping = scm_to_double (s);
+ Real concaveness = calc_concaveness ();
+ if (concaveness >= 10000)
+ {
+ unquanted_y_[LEFT] = unquanted_y_[RIGHT];
+ musical_dy_ = 0;
+ damping = 0;
+ }
+
+ if (damping)
+ {
+ Real dy = unquanted_y_[RIGHT] - unquanted_y_[LEFT];
+
+ Real slope = dy && x_span_ ? dy / x_span_ : 0;
+
+ slope = 0.6 * tanh (slope) / (damping + concaveness);
+
+ Real damped_dy = slope * x_span_;
+
+ set_minimum_dy (beam_, &damped_dy);
+
+ unquanted_y_[LEFT] += (dy - damped_dy) / 2;
+ unquanted_y_[RIGHT] -= (dy - damped_dy) / 2;
+ }
+}
+
+void
+Beam_scoring_problem::shift_region_to_valid ()
+{
+ if (!normal_stem_count_)
+ return;
+
+ Real beam_dy = unquanted_y_[RIGHT] - unquanted_y_[LEFT];
+ Real slope = x_span_ ? beam_dy / x_span_ : 0.0;
+
+ /*
+ Shift the positions so that we have a chance of finding good
+ quants (i.e. no short stem failures.)
+ */
+ Interval feasible_left_point;
+ feasible_left_point.set_full ();
+
+ for (vsize i = 0; i < stem_infos_.size (); i++)
+ {
+ // TODO - check for invisible here...
+ Real left_y
+ = stem_infos_[i].shortest_y_
+ - slope * stem_xpositions_ [i];
+
+ /*
+ left_y is now relative to the stem S. We want relative to
+ ourselves, so translate:
+ */
+ left_y += stem_ypositions_[i];
+ Interval flp;
+ flp.set_full ();
+ flp[-stem_infos_[i].dir_] = left_y;
+
+ feasible_left_point.intersect (flp);
+ }
+
+ vector<Grob *> filtered;
+ /*
+ We only update these for objects that are too large for quanting
+ to find a workaround. Typically, these are notes with
+ stems, and timesig/keysig/clef, which take out the entire area
+ inside the staff as feasible.
+
+ The code below disregards the thickness and multiplicity of the
+ beam. This should not be a problem, as the beam quanting will
+ take care of computing the impact those exactly.
+ */
+ Real min_y_size = 2.0;
+
+ // A list of intervals into which beams may not fall
+ vector<Interval> forbidden_intervals;
+
+ for (vsize i = 0; i < collisions_.size (); i++)
+ {
+ if (collisions_[i].x_ < 0 || collisions_[i].x_ > x_span_)
+ continue;
+
+ if (collisions_[i].y_.length () < min_y_size)
+ continue;
+
+ Direction d = LEFT;
+ do
+ {
+ Real dy = slope * collisions_[i].x_;
+
+ Direction yd = DOWN;
+ Interval disallowed;
+ do
+ {
+ Real left_y = collisions_[i].y_[yd] - dy;
+ disallowed[yd] = left_y;
+ }
+ while (flip (&yd) != DOWN);
+
+ forbidden_intervals.push_back (disallowed);
+ }
+ while (flip (&d) != LEFT);
+ }
+
+ vector_sort (forbidden_intervals, Interval::left_less);
+ Real beam_left_y = unquanted_y_[LEFT];
+ Interval feasible_beam_placements (beam_left_y, beam_left_y);
+
+ Interval_minefield minefield (feasible_beam_placements, 0.0);
+ for (vsize i = 0; i < forbidden_intervals.size (); i++)
+ minefield.add_forbidden_interval (forbidden_intervals[i]);
+ minefield.solve ();
+ feasible_beam_placements = minefield.feasible_placements ();
+
+ // if the beam placement falls out of the feasible region, we push it
+ // to infinity so that it can never be a feasible candidate below
+ Direction d = DOWN;
+ do
+ {
+ if (!feasible_left_point.contains (feasible_beam_placements[d]))
+ feasible_beam_placements[d] = d * infinity_f;
+ }
+ while (flip (&d) != DOWN);
+
+ if ((feasible_beam_placements[UP] == infinity_f && feasible_beam_placements[DOWN] == -infinity_f) && !feasible_left_point.is_empty ())
+ {
+ // We are somewhat screwed: we have a collision, but at least
+ // there is a way to satisfy stem length constraints.
+ beam_left_y = point_in_interval (feasible_left_point, 2.0);
+ }
+ else if (!feasible_left_point.is_empty ())
+ {
+ // Only one of them offers is feasible solution. Pick that one.
+ if (abs (beam_left_y - feasible_beam_placements[DOWN]) > abs (beam_left_y - feasible_beam_placements[UP]))
+ beam_left_y = feasible_beam_placements[UP];
+ else
+ beam_left_y = feasible_beam_placements[DOWN];
+ }
+ else
+ {
+ // We are completely screwed.
+ beam_->warning (_ ("no viable initial configuration found: may not find good beam slope"));
+ }
+
+ unquanted_y_ = Drul_array<Real> (beam_left_y, (beam_left_y + beam_dy));
+}
+
+void
+Beam_scoring_problem::generate_quants (vector<Beam_configuration *> *scores) const
+{
+ int region_size = (int) parameters_.REGION_SIZE;
+
+ // Knees and collisions are harder, lets try some more possibilities
+ if (is_knee_)
+ region_size += 2;
+ if (collisions_.size ())