X-Git-Url: https://git.donarmstrong.com/?a=blobdiff_plain;ds=sidebyside;f=lily%2Fbeam-quanting.cc;h=f2c35973e4b8600fa71593095fd65bb0353dc824;hb=32b9cd030a1917570346e9b9ea267fe409156b2f;hp=774cf1b02b89e15c35bd9d8a1eb5ca3e3fa43c73;hpb=3cfcd0df1125efe0eddc1f361f9bf24243ed12b7;p=lilypond.git

diff --git a/lily/beam-quanting.cc b/lily/beam-quanting.cc
index 774cf1b02b..f2c35973e4 100644
--- 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"
@@ -260,7 +261,7 @@ void Beam_scoring_problem::init_instance_variables (Grob *me, Drul_array<Real> y
 
       Real my_y = beams[i]->relative_coordinate (common[Y_AXIS], Y_AXIS);
 
-      Interval beam_width (-1.0,-1.0);
+      Interval beam_width (-1.0, -1.0);
       for (vsize j = 0; j < stems.size (); j++)
         {
           Grob *s = stems[j];
@@ -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)
@@ -301,8 +303,8 @@ void Beam_scoring_problem::init_instance_variables (Grob *me, Drul_array<Real> y
 
       staff_radius_ = Staff_symbol_referencer::staff_radius (beams[i]);
       edge_beam_counts_ = Drul_array<int>
-                         (Stem::beam_multiplicity (stems[0]).length () + 1,
-                          Stem::beam_multiplicity (stems.back ()).length () + 1);
+                          (Stem::beam_multiplicity (stems[0]).length () + 1,
+                           Stem::beam_multiplicity (stems.back ()).length () + 1);
 
       // TODO - why are we dividing by staff_space_?
       beam_translation_ = Beam::get_beam_translation (beams[i]) / staff_space_;
@@ -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")))
@@ -682,7 +685,7 @@ Beam_scoring_problem::calc_concaveness ()
 
         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;
 
@@ -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
@@ -1347,8 +1322,8 @@ Beam_scoring_problem::score_collisions (Beam_configuration *config) const
                     beam_y.distance (collision_y[UP]));
 
       Real scale_free
-        = max (parameters_.COLLISION_PADDING - dist, 0.0) /
-          parameters_.COLLISION_PADDING;
+        = max (parameters_.COLLISION_PADDING - dist, 0.0)
+          / parameters_.COLLISION_PADDING;
       demerits
       += collisions_[i].base_penalty_ *
          pow (scale_free, 3) * parameters_.COLLISION_PENALTY;