web: add news about GSoC 2012

[lilypond.git] / lily / beam-quanting.cc

diff --git a/lily/beam-quanting.cc b/lily/beam-quanting.cc
index 57cf25853dbbc49fd6ce3073b0f0f18172e76604..f2c35973e4b8600fa71593095fd65bb0353dc824 100644 (file)
--- a/lily/beam-quanting.cc
+++ b/lily/beam-quanting.cc
@@ -1,7 +1,7 @@
 /*
   This file is part of LilyPond, the GNU music typesetter.
 
-  Copyright (C) 1997--2011 Han-Wen Nienhuys <hanwen@xs4all.nl>
+  Copyright (C) 1997--2012 Han-Wen Nienhuys <hanwen@xs4all.nl>
   Jan Nieuwenhuizen <janneke@gnu.org>
 
   LilyPond is free software: you can redistribute it and/or modify
@@ -33,6 +33,7 @@ using namespace std;
 #include "grob-array.hh"
 #include "item.hh"
 #include "international.hh"
+#include "interval-minefield.hh"
 #include "least-squares.hh"
 #include "libc-extension.hh"
 #include "main.hh"
@@ -282,6 +283,7 @@ void Beam_scoring_problem::init_instance_variables (Grob *me, Drul_array<Real> y
           base_lengths_.push_back (y / staff_space_);
           stem_xpositions_.push_back (s->relative_coordinate (common[X_AXIS], X_AXIS) - x_pos[LEFT] + x_span_);
           stem_ypositions_.push_back (s->relative_coordinate (common[Y_AXIS], Y_AXIS) - my_y);
+
           if (is_normal_.back ())
             {
               if (beam_width[LEFT] == -1.0)
@@ -349,6 +351,7 @@ void Beam_scoring_problem::init_instance_variables (Grob *me, Drul_array<Real> y
             continue;
 
           b[X_AXIS] += (x_span_ - x_pos[LEFT]);
+          b[Y_AXIS] -= my_y;
           Real width = b[X_AXIS].length ();
           Real width_factor = sqrt (width / staff_space_);
 
@@ -373,7 +376,7 @@ void Beam_scoring_problem::init_instance_variables (Grob *me, Drul_array<Real> y
           Interval y;
           y.set_full ();
           y[-stem_dir] = Stem::chord_start_y (*it) + (*it)->relative_coordinate (common[Y_AXIS], Y_AXIS)
-                         - beams[i]->relative_coordinate (common[Y_AXIS], Y_AXIS);
+                         - my_y;
 
           Real factor = parameters_.STEM_COLLISION_FACTOR;
           if (!unsmob_grob (s->get_object ("beam")))
@@ -811,42 +814,14 @@ Beam_scoring_problem::shift_region_to_valid ()
     }
 
   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);
+  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