+ 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 < covered.size (); i++)
+ {
+ if (!covered[i]->is_live ())
+ continue;
+
+ if (Beam::has_interface (covered[i]) && is_cross_staff (covered[i]))
+ continue;
+
+ Box b;
+ for (Axis a = X_AXIS; a < NO_AXES; incr (a))
+ b[a] = covered[i]->extent (common[a], a);
+
+ if (b[X_AXIS].is_empty () || b[Y_AXIS].is_empty ())
+ continue;
+
+ if (intersection (b[X_AXIS], x_span).is_empty ())
+ continue;
+
+ filtered.push_back (covered[i]);
+ Grob *head_stem = Rhythmic_head::get_stem (covered[i]);
+ if (head_stem && Stem::is_normal_stem (head_stem)
+ && Note_head::has_interface (covered[i]))
+ {
+ if (Stem::get_beam (head_stem))
+ {
+ /*
+ We must assume that stems are infinitely long in this
+ case, as asking for the length of the stem typically
+ leads to circular dependencies.
+
+ This strategy assumes that we don't want to handle the
+ collision of beams in opposite non-forced directions
+ with this code, where shortening the stems of both
+ would resolve the problem, eg.
+
+ x x
+ | |
+ =====
+
+ =====
+ | |
+ x x
+
+ Such beams would need a coordinating grob to resolve
+ the collision, since both will likely want to occupy
+ the centerline.
+ */
+ Direction stemdir = get_grob_direction (head_stem);
+ b[Y_AXIS][stemdir] = stemdir * infinity_f;
+ }
+ else
+ {
+ // TODO - should we include the extent of the stem here?
+ }
+ }
+
+ if (b[Y_AXIS].length () < min_y_size)
+ continue;
+
+ Direction d = LEFT;
+ do
+ {
+ Real x = b[X_AXIS][d] - x_span[LEFT];
+ Real dy = slope * x;
+
+ Direction yd = DOWN;
+ Interval disallowed;
+ do
+ {
+ Real left_y = b[Y_AXIS][yd];
+
+ left_y -= dy;
+
+ // Translate back to beam as ref point.
+ left_y -= me->relative_coordinate (common[Y_AXIS], Y_AXIS);
+
+ disallowed[yd] = left_y;
+ }
+ while (flip (&yd) != DOWN);
+
+ forbidden_intervals.push_back (disallowed);
+ }
+ while (flip (&d) != LEFT);
+ }
+
+ Grob_array *arr
+ = Pointer_group_interface::get_grob_array (me,
+ ly_symbol2scm ("covered-grobs"));
+ arr->set_array (filtered);
+
+ vector_sort (forbidden_intervals, Interval::left_less);
+ Real epsilon = 1.0e-10;
+ 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 ())