lily/box-quarantine.cc

   1 /*
   2   This file is part of LilyPond, the GNU music typesetter.
   3
   4   Copyright (C) 2011--2012 Mike Solomon <mike@mikesolomon.org>
   5   Jan Nieuwenhuizen <janneke@gnu.org>
   6
   7   LilyPond is free software: you can redistribute it and/or modify
   8   it under the terms of the GNU General Public License as published by
   9   the Free Software Foundation, either version 3 of the License, or
  10   (at your option) any later version.
  11
  12   LilyPond is distributed in the hope that it will be useful,
  13   but WITHOUT ANY WARRANTY; without even the implied warranty of
  14   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15   GNU General Public License for more details.
  16
  17   You should have received a copy of the GNU General Public License
  18   along with LilyPond.  If not, see <http://www.gnu.org/licenses/>.
  19 */
  20
  21 #include "box-quarantine.hh"
  22 #include <functional>
  23
  24 Box_quarantine::Box_quarantine (Real padding, Axis a)
  25   : padding_ (padding), a_ (a)
  26 {
  27 }
  28
  29 void
  30 Box_quarantine::add_box_to_quarantine (Box infected)
  31 {
  32   Box nbox (infected);
  33   nbox[a_].widen (padding_ / 2);
  34   boxes_to_quarantine_.push_back (nbox);
  35 }
  36
  37 vector<Box>
  38 Box_quarantine::quarantined_boxes ()
  39 {
  40   return boxes_to_quarantine_;
  41 }
  42
  43 struct Intersection_info
  44 {
  45   vsize index_;
  46   Real amount_;
  47   int mid_;
  48   Intersection_info (vsize index, Real amount, int mid);
  49 };
  50
  51 Intersection_info::Intersection_info (vsize index, Real amount, int mid)
  52   : index_ (index), amount_ (amount), mid_ (mid)
  53 {
  54 }
  55
  56 /*
  57   boxes_to_quarantine_ contains a vector of boxes that may
  58   or may not overlap.  it iterates through these boxes,
  59   pushing quarantined_boxes_ epsilon over or epsilon under a
  60   collision.  when this type of change happens, the loop is marked
  61   as "dirty" and re-iterated.
  62
  63   TODO: not sure if this loop causes infinite behavior...
  64 */
  65
  66 bool
  67 sort_towards_middle(Intersection_info ii0, Intersection_info ii1)
  68 {
  69   // ugh...with C++11, we'll just be able to do a factory instead of
  70   // bundling mid with the Intersection_info
  71   int mid = ii0.mid_;
  72   assert ((double)(ii0.index_ - mid) >= 0.0);
  73   assert ((double)(ii1.index_ - mid) >= 0.0);
  74   return fabs (ii0.index_ - mid) < fabs (ii1.index_ - mid);
  75 }
  76
  77 void
  78 Box_quarantine::solve ()
  79 {
  80   int mid = boxes_to_quarantine_.size () / 2;
  81   Real epsilon = 1.0e-4;
  82   bool dirty = false;
  83   do
  84     {
  85       dirty = false;
  86       vector<Intersection_info> ii;
  87       for (vsize i = 0; i < boxes_to_quarantine_.size () - 1; i++)
  88         {
  89           Box scratch (boxes_to_quarantine_[i]);
  90           scratch.intersect (boxes_to_quarantine_[i + 1]);
  91           if (!scratch.is_empty ())
  92             ii.push_back (Intersection_info (i, scratch[a_].length (), mid));
  93         }
  94       vector_sort (ii, sort_towards_middle);
  95       if (ii.size () > 0)
  96         {
  97           Offset shift (-(epsilon + ii[0].amount_ / 2.0), 0.0);
  98           if (a_ == Y_AXIS)
  99             shift = shift.swapped ();
 100           boxes_to_quarantine_[ii[0].index_].translate (shift);
 101           shift[a_] = -shift[a_];
 102           boxes_to_quarantine_[ii[0].index_ + 1].translate (shift);
 103           dirty = true;
 104         }
 105     }
 106   while (dirty);
 107 }