+ /*
+ 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 epsilon = 1.0e-10;
+ Real beam_left_y = unquanted_y_[LEFT];
+ Interval feasible_beam_placements (beam_left_y, beam_left_y);
+
+ /*
+ forbidden_intervals contains a vector of intervals in which
+ the beam cannot start. it iterates through these intervals,
+ pushing feasible_beam_placements epsilon over or epsilon under a
+ collision. when this type of change happens, the loop is marked
+ as "dirty" and re-iterated.
+
+ TODO: figure out a faster ways that this loop can happen via
+ a better search algorithm and/or OOP.
+ */
+
+ bool dirty = false;
+ do
+ {
+ dirty = false;
+ for (vsize i = 0; i < forbidden_intervals.size (); i++)
+ {
+ Direction d = DOWN;
+ do
+ {
+ if (forbidden_intervals[i][d] == d * infinity_f)
+ feasible_beam_placements[d] = d * infinity_f;
+ else if (forbidden_intervals[i].contains (feasible_beam_placements[d]))
+ {
+ feasible_beam_placements[d] = d * epsilon + forbidden_intervals[i][d];
+ dirty = true;
+ }
+ }
+ while (flip (&d) != DOWN);
+ }
+ }
+ while (dirty);
+
+ // 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));