+ 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 ())
+ {
+ // 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];