From 251a3b012c71a7d5d4ae64a2c89dfb5d6869ab07 Mon Sep 17 00:00:00 2001 From: Mike Solomon Date: Sat, 26 Jan 2013 08:02:15 +0100 Subject: [PATCH] Deletes Box_quarantine. Implements this functionality in fingering-column.cc, using Keith O'Hara's algorithm, which handles corner cases better. --- lily/box-quarantine.cc | 107 --------------------------------- lily/fingering-column.cc | 81 ++++++++++--------------- lily/include/box-quarantine.hh | 41 ------------- 3 files changed, 33 insertions(+), 196 deletions(-) delete mode 100644 lily/box-quarantine.cc delete mode 100644 lily/include/box-quarantine.hh diff --git a/lily/box-quarantine.cc b/lily/box-quarantine.cc deleted file mode 100644 index dff8587601..0000000000 --- a/lily/box-quarantine.cc +++ /dev/null @@ -1,107 +0,0 @@ -/* - This file is part of LilyPond, the GNU music typesetter. - - Copyright (C) 2011--2012 Mike Solomon - Jan Nieuwenhuizen - - LilyPond is free software: you can redistribute it and/or modify - it under the terms of the GNU General Public License as published by - the Free Software Foundation, either version 3 of the License, or - (at your option) any later version. - - LilyPond is distributed in the hope that it will be useful, - but WITHOUT ANY WARRANTY; without even the implied warranty of - MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - GNU General Public License for more details. - - You should have received a copy of the GNU General Public License - along with LilyPond. If not, see . -*/ - -#include "box-quarantine.hh" -#include - -Box_quarantine::Box_quarantine (Real padding, Axis a) - : padding_ (padding), a_ (a) -{ -} - -void -Box_quarantine::add_box_to_quarantine (Box infected) -{ - Box nbox (infected); - nbox[a_].widen (padding_ / 2); - boxes_to_quarantine_.push_back (nbox); -} - -vector -Box_quarantine::quarantined_boxes () -{ - return boxes_to_quarantine_; -} - -struct Intersection_info -{ - vsize index_; - Real amount_; - int mid_; - Intersection_info (vsize index, Real amount, int mid); -}; - -Intersection_info::Intersection_info (vsize index, Real amount, int mid) - : index_ (index), amount_ (amount), mid_ (mid) -{ -} - -/* - boxes_to_quarantine_ contains a vector of boxes that may - or may not overlap. it iterates through these boxes, - pushing quarantined_boxes_ epsilon over or epsilon under a - collision. when this type of change happens, the loop is marked - as "dirty" and re-iterated. - - TODO: not sure if this loop causes infinite behavior... -*/ - -bool -sort_towards_middle(Intersection_info ii0, Intersection_info ii1) -{ - // ugh...with C++11, we'll just be able to do a factory instead of - // bundling mid with the Intersection_info - int mid = ii0.mid_; - assert ((double)(ii0.index_ - mid) >= 0.0); - assert ((double)(ii1.index_ - mid) >= 0.0); - return fabs (ii0.index_ - mid) < fabs (ii1.index_ - mid); -} - -void -Box_quarantine::solve () -{ - int mid = boxes_to_quarantine_.size () / 2; - Real epsilon = 1.0e-4; - bool dirty = false; - do - { - dirty = false; - vector ii; - for (vsize i = 0; i < boxes_to_quarantine_.size () - 1; i++) - { - Box scratch (boxes_to_quarantine_[i]); - scratch.intersect (boxes_to_quarantine_[i + 1]); - if (!scratch.is_empty ()) - ii.push_back (Intersection_info (i, scratch[a_].length (), mid)); - } - vector_sort (ii, sort_towards_middle); - if (ii.size () > 0) - { - Offset shift (-(epsilon + ii[0].amount_ / 2.0), 0.0); - if (a_ == Y_AXIS) - shift = shift.swapped (); - boxes_to_quarantine_[ii[0].index_].translate (shift); - shift[a_] = -shift[a_]; - boxes_to_quarantine_[ii[0].index_ + 1].translate (shift); - dirty = true; - } - } - while (dirty); -} diff --git a/lily/fingering-column.cc b/lily/fingering-column.cc index 76c7bd3b89..1cc6c12b11 100644 --- a/lily/fingering-column.cc +++ b/lily/fingering-column.cc @@ -19,35 +19,11 @@ #include "grob.hh" #include "fingering-column.hh" -#include "box-quarantine.hh" #include "pointer-group-interface.hh" #include "staff-symbol-referencer.hh" #include "item.hh" #include "paper-column.hh" -#include - -// The sorting algorithm may not preserve the order of the -// original fingerings. We use Fingering_position_info to retain -// this order. - -struct Fingering_position_info { - Box box_; - vsize idx_; - Fingering_position_info (Box, vsize); -}; - -Fingering_position_info::Fingering_position_info (Box box, vsize idx) - : box_ (box), idx_ (idx) -{ -} - -bool -fingering_position_less (Fingering_position_info fpi0, Fingering_position_info fpi1) -{ - return Interval::left_less (fpi0.box_[Y_AXIS], fpi1.box_[Y_AXIS]); -} - MAKE_SCHEME_CALLBACK (Fingering_column, calc_positioning_done, 1); SCM Fingering_column::calc_positioning_done (SCM smob) @@ -56,8 +32,6 @@ Fingering_column::calc_positioning_done (SCM smob) if (!me->is_live ()) return SCM_BOOL_T; - map shifted; - me->set_property ("positioning-done", SCM_BOOL_T); extract_grob_set (me, "fingerings", const_fingerings); @@ -77,32 +51,43 @@ Fingering_column::calc_positioning_done (SCM smob) common_refpoint_of_array (fingerings, me, Y_AXIS)}; Real padding = robust_scm2double (me->get_property ("padding"), 0.2); - Box_quarantine bq (padding, Y_AXIS); - vector origs; - for (vsize i = 0; i < fingerings.size (); i++) - { - Interval x_ext = fingerings[i]->extent (common[X_AXIS], X_AXIS); - // center on Y parent - fingerings[i]->translate_axis (-fingerings[i]->extent (fingerings[i], Y_AXIS).length () / 2.0, Y_AXIS); - Interval y_ext = fingerings[i]->extent (fingerings[i], Y_AXIS) - + fingerings[i]->get_parent (Y_AXIS) - ->relative_coordinate (common[Y_AXIS], Y_AXIS); - origs.push_back(Fingering_position_info (Box (x_ext, y_ext), i)); - } // order the fingerings from bottom to top - vector_sort (origs, fingering_position_less); - - for (vsize i = 0; i < origs.size (); i++) - bq.add_box_to_quarantine (Box (origs[i].box_)); + vector_sort (fingerings, pure_position_less); + + vector shift(fingerings.size()); + + // Try stacking the fingerings top-to-bottom, and then bottom-to-top. + // Use the average of the resulting stacked locations as the final positions + for (UP_and_DOWN (d)) + { + Real stack_end = -d * infinity_f; + Interval prev_x_ext; + for (vsize i = (d == UP)? 0 : fingerings.size() - 1; + i < fingerings.size (); + i += d) + { + Interval x_ext = fingerings[i]->extent(common[X_AXIS], X_AXIS); + Interval y_ext = fingerings[i]->extent(fingerings[i], Y_AXIS); + Real parent_y = fingerings[i]->get_parent(Y_AXIS) + ->relative_coordinate(common[Y_AXIS], Y_AXIS); + + // Checking only between sequential neighbors, seems good enough + if (!intersection(x_ext, prev_x_ext).is_empty()) + stack_end += d * (y_ext.length() + padding); + // minmax() returns whichever is further along in direction d + stack_end = minmax(d, stack_end, parent_y); + + shift[i] += 0.5 * (stack_end - y_ext[d] - parent_y); + + prev_x_ext = x_ext; + } + } - bq.solve (); - vector news (bq.quarantined_boxes ()); - - for (vsize i = 0; i < origs.size (); i++) - fingerings[origs[i].idx_]->translate_axis (news[i][Y_AXIS][DOWN] - origs[i].box_[Y_AXIS][DOWN], Y_AXIS); + for (vsize i = 0; i < fingerings.size (); i++) + fingerings[i]->translate_axis(shift[i], Y_AXIS); - return SCM_BOOL_T; + return SCM_BOOL_T; } void diff --git a/lily/include/box-quarantine.hh b/lily/include/box-quarantine.hh deleted file mode 100644 index 3673a959bd..0000000000 --- a/lily/include/box-quarantine.hh +++ /dev/null @@ -1,41 +0,0 @@ -/* - This file is part of LilyPond, the GNU music typesetter. - - Copyright (C) 2012 Mike Solomon - - LilyPond is free software: you can redistribute it and/or modify - it under the terms of the GNU General Public License as published by - the Free Software Foundation, either version 3 of the License, or - (at your option) any later version. - - LilyPond is distributed in the hope that it will be useful, - but WITHOUT ANY WARRANTY; without even the implied warranty of - MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - GNU General Public License for more details. - - You should have received a copy of the GNU General Public License - along with LilyPond. If not, see . -*/ - -#ifndef BOX_QUARANTINE_HH -#define BOX_QUARANTINE_HH - -#include "lily-proto.hh" -#include "std-vector.hh" -#include "box.hh" - -class Box_quarantine -{ -public: - Box_quarantine (Real, Axis); - void add_box_to_quarantine (Box); - void solve (); - vector quarantined_boxes (); - -private: - vector boxes_to_quarantine_; - Real padding_; - Axis a_; -}; - -#endif // BOX_QUARANTINE_HH -- 2.39.2