Here's a patch for introducing skyline vertical spacing. The bulk of
the changes are to rewrite skyline so that
1) merging is linear (in the sum of the lengths of the skylines) time
2) building a skyline from boxes is O(n lg(n)) time
3) we support sloped-roof skylines. This isn't used yet, but I think
it can be used for skylines where more accuracy is needed (for example
in horizontal spacing). In any case, it only adds a constant factor to
the complexity.
It would be nice if someone could review my changes particularly in
tie-formatting-problem and accidental-placement. output-distance.py is
OK with the changes, but I don't really understand the code there.
Cheers,
Joe
------------------------------------------------------------------------
diff --git a/lily/accidental-placement.cc b/lily/accidental-placement.cc
index 02f0c52..c943c9c 100644
--- a/lily/accidental-placement.cc
+++ b/lily/accidental-placement.cc
@@ -110,8 +110,8 @@ Accidental_placement::get_relevant_accid
struct Accidental_placement_entry
{
- vector<Skyline_entry> left_skyline_;
- vector<Skyline_entry> right_skyline_;
+ Skyline left_skyline_;
+ Skyline right_skyline_;
Interval vertical_extent_;
vector<Box> extents_;
vector<Grob*> grobs_;
@@ -307,22 +307,16 @@ Accidental_placement::calc_positioning_d
for (vsize i = apes.size (); i--;)
{
Accidental_placement_entry *ape = apes[i];
- ape->left_skyline_ = empty_skyline (LEFT);
- ape->right_skyline_ = empty_skyline (RIGHT);
for (vsize j = apes[i]->grobs_.size (); j--;)
{
Grob *a = apes[i]->grobs_[j];
-
vector<Box> boxes = Accidental_interface::accurate_boxes (a, common);
ape->extents_.insert (ape->extents_.end (), boxes.begin (), boxes.end ());
- for (vsize j = boxes.size (); j--;)
- {
- insert_extent_into_skyline (&ape->left_skyline_, boxes[j],
Y_AXIS, LEFT);
- insert_extent_into_skyline (&ape->right_skyline_, boxes[j],
Y_AXIS, RIGHT);
- }
}
+ ape->left_skyline_ = Skyline (ape->extents_, Y_AXIS, LEFT);
+ ape->right_skyline_ = Skyline (ape->extents_, Y_AXIS, RIGHT);
}
Interval total;
@@ -340,16 +334,11 @@ Accidental_placement::calc_positioning_d
Accidental_placement_entry *head_ape = new Accidental_placement_entry;
common[X_AXIS] = common_refpoint_of_array (heads, common[X_AXIS], X_AXIS);
- vector<Skyline_entry> head_skyline (empty_skyline (LEFT));
vector<Box> head_extents;
for (vsize i = heads.size (); i--;)
- {
- Box b (heads[i]->extent (common[X_AXIS], X_AXIS),
- heads[i]->extent (common[Y_AXIS], Y_AXIS));
-
- insert_extent_into_skyline (&head_skyline, b, Y_AXIS, LEFT);
- }
+ head_extents.push_back (Box (heads[i]->extent (common[X_AXIS], X_AXIS),
+ heads[i]->extent (common[Y_AXIS], Y_AXIS)));
vector<Grob *> stems;
for (vsize i = 0; i < heads.size (); i++)
@@ -364,27 +353,24 @@ Accidental_placement::calc_positioning_d
{
int very_large = INT_MAX;
- Box b (heads[i]->extent (common[X_AXIS], X_AXIS),
- heads[i]->pure_height (common[Y_AXIS], 0, very_large));
-
- insert_extent_into_skyline (&head_skyline, b, Y_AXIS, LEFT);
+ head_extents.push_back (Box (heads[i]->extent (common[X_AXIS], X_AXIS),
+ heads[i]->pure_height (common[Y_AXIS], 0,
very_large)));
}
-
- head_ape->left_skyline_ = head_skyline;
+
+ head_ape->left_skyline_ = Skyline (head_extents, Y_AXIS, LEFT);
head_ape->offset_ = 0.0;
Real padding = robust_scm2double (me->get_property ("padding"), 0.2);
- vector<Skyline_entry> left_skyline = head_ape->left_skyline_;
- heighten_skyline (&left_skyline,
- -robust_scm2double (me->get_property ("right-padding"), 0));
+ Skyline left_skyline = head_ape->left_skyline_;
+ left_skyline.raise (-robust_scm2double (me->get_property ("right-padding"),
0))
+;
/*
Add accs entries right-to-left.
*/
for (vsize i = apes.size (); i-- > 0;)
{
- Real offset
- = -skyline_meshing_distance (apes[i]->right_skyline_, left_skyline);
+ Real offset = -apes[i]->right_skyline_.distance (left_skyline);
if (isinf (offset))
offset = (i < apes.size () - 1) ? apes[i + 1]->offset_ : 0.0;
else
@@ -392,9 +378,9 @@ Accidental_placement::calc_positioning_d
apes[i]->offset_ = offset;
- vector<Skyline_entry> new_left_skyline = apes[i]->left_skyline_;
- heighten_skyline (&new_left_skyline, apes[i]->offset_);
- merge_skyline (&new_left_skyline, left_skyline, LEFT);
+ Skyline new_left_skyline = apes[i]->left_skyline_;
+ new_left_skyline.raise (apes[i]->offset_);
+ new_left_skyline.merge (left_skyline);
left_skyline = new_left_skyline;
}
diff --git a/lily/include/skyline.hh b/lily/include/skyline.hh
index fc8d3ac..f086969 100644
--- a/lily/include/skyline.hh
+++ b/lily/include/skyline.hh
@@ -1,41 +1,63 @@
/*
- skyline.hh -- declare Skyline_entry and funcbs.
+ skyline.hh -- declare Skyline class.
source file of the GNU LilyPond music typesetter
- (c) 2002--2006 Han-Wen Nienhuys <address@hidden>
+ (c) 2006 Joe Neeman <address@hidden>
*/
#ifndef SKYLINE_HH
#define SKYLINE_HH
-#include "std-vector.hh"
+#include <list>
+#include "axis.hh"
#include "box.hh"
+#include "interval.hh"
+#include "direction.hh"
+#include "std-vector.hh"
-struct Skyline_entry
+struct Building
{
- Interval width_;
- Real height_;
- Skyline_entry ();
- Skyline_entry (Interval, Real);
+ Interval iv_;
+ Real start_height_;
+ Real end_height_;
+ Real m_;
+ Real b_;
+
+ Building (Real start, Real start_height, Real end_height, Real end);
+
+ Real height (Real x) const;
+ Real intersection (Building const &other) const;
+ void leading_part (Real chop);
+ bool obstructs (Building const &other) const;
};
-void
-merge_skyline (vector<Skyline_entry> *a1, vector<Skyline_entry> const &a2,
- Direction);
-void insert_extent_into_skyline (vector<Skyline_entry> *line, Box b, Axis
line_axis,
- Direction d);
-vector<Skyline_entry>
-extents_to_skyline (vector<Box> const &extents, Axis a, Direction d);
-vector<Skyline_entry> empty_skyline (Direction d);
-void heighten_skyline (vector<Skyline_entry> *buildings, Real ground);
-Real
-skyline_meshing_distance (vector<Skyline_entry> const &buildings,
- vector<Skyline_entry> const &clouds);
-
-Real
-skyline_height (vector<Skyline_entry> const &buildings,
- Real airplane, Direction sky_dir);
+class Skyline
+{
+public:
+private:
+ list<Building> buildings_;
+ Direction sky_;
+ Real last_visible_point (Building const &b, list<Building> *const sky);
+ void internal_merge_skyline (list<Building>*, list<Building>*,
+ list<Building> *const result);
+ void internal_build_skyline (list<Building>*,
+ list<Building> *const result);
+ bool is_legal_skyline () const;
+
+public:
+ Skyline ();
+ Skyline (Direction sky);
+ Skyline (vector<Box> const &bldgs, Axis a, Direction sky);
+
+ void merge (Skyline const &);
+ void insert (Box const &, Axis);
+ void raise (Real);
+ Real distance (Skyline const &) const;
+ Real height (Real airplane) const;
+ Real max_height () const;
+ void set_minimum_height (Real height);
+};
#endif /* SKYLINE_HH */
diff --git a/lily/include/system.hh b/lily/include/system.hh
index 2fe740f..f10b9b7 100644
--- a/lily/include/system.hh
+++ b/lily/include/system.hh
@@ -11,6 +11,7 @@ #define SYSTEM_HH
#include "column-x-positions.hh"
#include "spanner.hh"
#include "grob-array.hh"
+#include "skyline.hh"
/*
If you keep following offset reference points, you will always end
@@ -21,6 +22,8 @@ class System : public Spanner
{
int rank_;
Grob_array *all_elements_;
+ Drul_array<Skyline> skylines_;
+ void build_skylines ();
void init_elements ();
friend class Paper_score; // ugh.
Paper_score *pscore_; // ugh.
diff --git a/lily/include/tie-column-format.hh
b/lily/include/tie-column-format.hh
index 1c82c42..3206e32 100644
--- a/lily/include/tie-column-format.hh
+++ b/lily/include/tie-column-format.hh
@@ -13,7 +13,7 @@ #define TIE_COLUMN_FORMAT_HH
#include "lily-proto.hh"
#include "tie-configuration.hh"
-void set_chord_outline (vector<Skyline_entry> *skyline,
+void set_chord_outline (Skyline *skyline,
vector<Item*> bounds,
Grob *common,
Direction d);
@@ -25,7 +25,7 @@ void final_shape_adjustment (Tie_configu
Tie_formatting_problem const&,
Grob *staff_referencer);
void
-set_chord_outlines (Drul_array< vector<Skyline_entry> > *skyline_drul,
+set_chord_outlines (Drul_array<Skyline> *skyline_drul,
vector<Grob*> ties,
Grob *common);
diff --git a/lily/include/tie-formatting-problem.hh b/lily/include/tie-formatting-problem.hh
index 5d46129..7d48995 100644
--- a/lily/include/tie-formatting-problem.hh
+++ b/lily/include/tie-formatting-problem.hh
@@ -47,7 +47,7 @@ struct Tie_configuration_variation
Tie_configuration_variation ();
};
-typedef map < Tuple<int, 2>, vector<Skyline_entry> > Chord_outline_map;
+typedef map < Tuple<int, 2>, Skyline> Chord_outline_map;
typedef map < Tuple<int, 2>, Box> Column_extent_map;
class Tie_formatting_problem
{
diff --git a/lily/skyline.cc b/lily/skyline.cc
index f72ea5b..d508450 100644
--- a/lily/skyline.cc
+++ b/lily/skyline.cc
@@ -1,202 +1,385 @@
-/*
- skyline.cc -- implement Skyline_entry and funcs.
+/* skyline.cc -- implement the Skyline class
- source file of the GNU LilyPond music typesetter
-
- (c) 2002--2006 Han-Wen Nienhuys <address@hidden>
+ source file of the GNU LilyPond music typesetter
+
+ (c) 2006 Joe Neeman <address@hidden>
*/
#include "skyline.hh"
-/*
- A skyline is a shape of the form:
+/* A skyline is a sequence of non-overlapping buildings: something like
+ this:
+ _________
+ | | ________
+ | | _________| |
+ /| | \ | |
+ / |------- \ | |
+ / \ | |
+ / --------------- -------
+ --
+ Each building has a starting position, and ending position, a starting
+ height and an ending height.
+
+ The following invariants are observed:
+ - the start of the first building is at -infinity
+ - the end of the last building is at infinity
+ - if a building has infinite length (ie. the first and last buildings),
+ then its starting height and ending height are equal
+ - the end of one building is the same as the beginning of the next
+ building
+
+ We also allow skylines to point down (the structure is exactly the same,
+ but we think of the part above the line as being filled with mass and the
+ part below as being empty). ::distance finds the minimum distance between
+ an UP skyline and a DOWN skyline.
+
+ Note that we store DOWN skylines upside-down. That is, in order to compare
+ a DOWN skyline with an UP skyline, we need to flip the DOWN skyline first.
+ This means that the merging routine doesn't need to be aware of direction,
+ but the distance routine does.
+*/
+#define EPS 1e-10
- * ----
- * | |
- * ---------| |
- * | |
- * | |
- * | |______
- * --------| |___
- *
+static inline bool
+equal (Real x, Real y)
+{
+ return abs (x - y) < EPS || (isinf (x) && isinf (y) && ((x > 0) == (y > 0)));
+}
- This file deals with building such skyline structure, and computing
- the minimum distance between two opposing skylines.
+bool
+Skyline::is_legal_skyline () const
+{
+ list<Building>::const_iterator i;
+ Real last_x = -infinity_f;
+ for (i = buildings_.begin (); i != buildings_.end (); i++)
+ {
+ if (isinf (i->start_height_) != isinf (i->end_height_))
+ return false;
+ if (i->iv_[LEFT] != last_x)
+ return false;
+ if (isinf (i->iv_.length ()) && i->start_height_ != i->end_height_)
+ return false;
+ last_x = i->iv_[RIGHT];
+ }
+ return last_x == infinity_f;
+}
- Invariants for a skyline:
+Building::Building (Real start, Real start_height, Real end_height, Real end)
+ : iv_ (start, end)
+{
+ start_height_ = start_height;
+ end_height_ = end_height;
- skyline[...].width_ forms a partition of the real interval, where
- the segments are adjacent, and ascending. Hence we have
+ if (isinf (start_height) || isinf (start) || isinf (end))
+ end_height_ = start_height;
+ else if (isinf (end_height))
+ start_height_ = end_height;
- skyline.back ().width_[RIGHT] = inf
- skyline[0].width_[LEFT] = -inf
-*/
+ m_ = (end_height - start_height) / (end - start);
+ b_ = start_height - m_*start;
-const Real EPS = 1e-12;
+ if (isinf (start_height) || isinf (start) || isinf (end))
+ {
+ m_ = 0;
+ b_ = start_height;
+ }
+}
-/*
- TODO: avoid unnecessary fragmentation.
+Real
+Building::height (Real x) const
+{
+ if (isinf (x))
+ return start_height_;
+ return m_*x + b_;
+}
+
+Real
+Building::intersection (Building const &other) const
+{
+ return (b_ - other.b_) / (other.m_ - m_);
+}
- This is O (n^2), searching and insertion. Could be O (n log n) with
- binsearch.
-*/
void
-insert_extent_into_skyline (vector<Skyline_entry> *line, Box b, Axis line_axis,
- Direction d)
+Building::leading_part (Real chop)
{
- Interval extent = b[line_axis];
- if (extent.is_empty ())
- return;
+ assert (chop > iv_[LEFT] && chop <= iv_[RIGHT] && !equal (chop, iv_[LEFT]));
+ iv_[RIGHT] = chop;
+ end_height_ = height (chop);
+}
- Real stick_out = b[other_axis (line_axis)][d];
+static void
+skyline_trailing_part (list<Building> *sky, Real x)
+{
+ if (equal (x, sky->front ().iv_[RIGHT]))
+ sky->pop_front ();
+ else
+ assert (x < sky->front ().iv_[RIGHT]);
- /*
- Intersect each segment of LINE with EXTENT, and if non-empty, insert
relevant segments.
- */
- for (vsize i = line->size (); i--;)
+ if (!sky->empty ())
{
- Interval w = line->at (i).width_;
- w.intersect (extent);
+ sky->front ().iv_[LEFT] = x;
+ sky->front ().start_height_ = sky->front ().height (x);
+ }
+}
+
+bool
+Building::obstructs (Building const &other) const
+{
+ if (equal (intersection (other), iv_[LEFT]) || equal (start_height_,
other.start_height_))
+ return m_ > other.m_;
+ return start_height_ > other.start_height_;
+}
- if (extent[LEFT] >= w[RIGHT])
- break;
- Real my_height = line->at (i).height_;
+/* precondition: the building should be visible above the first
+ building in skyline. The building and the skyline should
+ start at the same point.
- if (!w.is_empty ()
- && w.length () > EPS
- && d * (my_height - stick_out) < 0)
- {
- Interval e1 (line->at (i).width_[LEFT], extent[LEFT]);
- Interval e3 (extent[RIGHT], line->at (i).width_[RIGHT]);
+ return the point at which the building b is no longer visible,
+ either because it has ended or because the skyline has risen
+ above it. Truncate the skyline at that point.
+*/
+Real
+Skyline::last_visible_point (Building const &b, list<Building> *const skyline)
+{
+ assert (!skyline->front ().obstructs (b));
+ while (1)
+ {
+ Building other = skyline->front ();
- if (!e3.is_empty () && e3.length () > EPS)
- line->insert (line->begin () + i + 1, Skyline_entry (e3,
my_height));
+ /* there are 3 interesting cases:
+ 1) the roofs intersect within the spans of the buildings */
+ Real intersect = b.intersection (other);
+ if (intersection (b.iv_, other.iv_).contains (intersect))
+ {
+ if (equal (intersect, b.iv_[LEFT]))
+ {
+ /* if the buildings have almost the same starting height, we can
find
+ that their intersection "equals" the start point. In this
case, we
+ just skip the intersection.
+ */
+ assert (b.m_ >= other.m_);
+ }
+ else
+ {
+ skyline_trailing_part (skyline, intersect);
+ return intersect;
+ }
+ }
- line->at (i).height_ = stick_out;
- line->at (i).width_ = w;
- if (!e1.is_empty () && e1.length () > EPS)
- line->insert (line->begin () + i, Skyline_entry (e1, my_height));
+ /* 2) the first building ends. This is guaranteed to happen before
+ the skyline becomes empty because it has to end at infinity */
+ if (skyline->empty () && !other.iv_.contains (b.iv_[RIGHT]))
+ assert (0);
+ if (other.iv_.contains (b.iv_[RIGHT]))
+ {
+ skyline_trailing_part (skyline, b.iv_[RIGHT]);
+ return b.iv_[RIGHT];
}
+
+ assert (!skyline->empty ());
+ skyline->pop_front ();
+ other = skyline->front ();
+
+ /* 3) the next building in the skyline starts above b */
+ if (other.start_height_ > b.height (other.iv_[LEFT]))
+ return other.iv_[LEFT];
}
}
void
-merge_skyline (vector<Skyline_entry> *a1,
- vector<Skyline_entry> const &a2,
- Direction dir)
+Skyline::internal_merge_skyline (list<Building> *s1, list<Building> *s2,
+ list<Building> *const result)
{
- for (vsize i = 0; i < a2.size (); i++)
+ while (!s1->empty ())
{
- Box b;
- b[X_AXIS] = a2[i].width_;
- b[Y_AXIS][dir] = a2[i].height_;
- b[Y_AXIS][-dir] = dir * infinity_f;
+ if (s2->front ().obstructs (s1->front ()))
+ swap (s1, s2);
+
+ Building b = s1->front ();
+ Real end = last_visible_point (b, s2);
+
+ b.leading_part (end);
+ result->push_front (b);
- insert_extent_into_skyline (a1, b, X_AXIS, dir);
+ skyline_trailing_part (s1, end);
}
+ result->reverse ();
}
-vector<Skyline_entry>
-empty_skyline (Direction d)
+static void
+empty_skyline (list<Building> *const ret)
{
- vector<Skyline_entry> skyline;
+ ret->push_front (Building (-infinity_f, -infinity_f, -infinity_f,
infinity_f));
+}
- Interval i;
- i.set_empty ();
- i.swap ();
- Skyline_entry e;
- e.width_ = i;
- e.height_ = -d * infinity_f;
- skyline.push_back (e);
- return skyline;
+static void
+single_skyline (Building const &b, list<Building> *const ret)
+{
+ if (!isinf (b.iv_[RIGHT]))
+ ret->push_front (Building (b.iv_[RIGHT], -infinity_f, -infinity_f,
infinity_f));
+ ret->push_front (b);
+ if (!isinf (b.iv_[LEFT]))
+ ret->push_front (Building (-infinity_f, -infinity_f, -infinity_f,
b.iv_[LEFT]));
}
-vector<Skyline_entry>
-extents_to_skyline (vector<Box> const &extents, Axis a, Direction d)
+void
+Skyline::internal_build_skyline (list<Building> *buildings, list<Building>
*const result)
{
+ vsize size = buildings->size ();
- vector<Skyline_entry> skyline = empty_skyline (d);
+ if (size == 0)
+ {
+ empty_skyline (result);
+ return;
+ }
+ else if (size == 1)
+ {
+ single_skyline (buildings->front (), result);
+ return;
+ }
- /*
- This makes a cubic algorithm (array insertion is O (n),
- searching the array dumbly is O (n), and for n items, we get O (n^3).)
+ list<Building> right_half;
+ list<Building>::iterator i = buildings->begin ();
- We could do a lot better (n log (n), using a balanced tree) but
- that seems overkill for now.
- */
- for (vsize j = extents.size (); j--;)
- insert_extent_into_skyline (&skyline, extents[j], a, d);
+ for (vsize s = 0; s < size/2; s++)
+ i++;
+ right_half.splice (right_half.end (), *buildings, i, buildings->end ());
- return skyline;
+ list<Building> right;
+ list<Building> left;
+ internal_build_skyline (&right_half, &right);
+ internal_build_skyline (buildings, &left);
+ internal_merge_skyline (&right, &left, result);
}
-/*
- minimum distance that can be achieved between baselines. "Clouds" is
- a skyline pointing down.
+Skyline::Skyline ()
+{
+ sky_ = UP;
+ empty_skyline (&buildings_);
+}
- This is an O (n) algorithm.
-*/
-Real
-skyline_meshing_distance (vector<Skyline_entry> const &buildings,
- vector<Skyline_entry> const &clouds)
+Skyline::Skyline (Direction sky)
{
- int i = buildings.size () -1;
- int j = clouds.size () -1;
+ sky_ = sky;
+ empty_skyline (&buildings_);
+}
- Real distance = -infinity_f;
+Skyline::Skyline (vector<Box> const &boxes, Axis a, Direction sky)
+{
+ list<Building> bldgs;
+ sky_ = sky;
- while (i > 0 || j > 0)
+ for (vsize i = 0; i < boxes.size (); i++)
{
- Interval w = buildings[i].width_;
- w.intersect (clouds[j].width_);
-
- if (!w.is_empty ())
- distance = max (distance, (buildings[i].height_ - clouds[j].height_));
-
- if (i > 0 && buildings[i].width_[LEFT] >= clouds[j].width_[LEFT])
- i--;
- else if (j > 0 && buildings[i].width_[LEFT] <= clouds[j].width_[LEFT])
- j--;
+ Interval iv = boxes[i][a];
+ Real height = sky * boxes[i][other_axis (a)][sky];
+ if (!iv.is_empty () && !isinf (height) && !equal (iv[LEFT], iv[RIGHT]))
+ bldgs.push_front (Building (iv[LEFT], height, height, iv[RIGHT]));
}
-
- return distance;
+ internal_build_skyline (&bldgs, &buildings_);
+ assert (is_legal_skyline ());
}
-Skyline_entry::Skyline_entry ()
+void
+Skyline::merge (Skyline const &other)
{
- height_ = 0.0;
+ assert (sky_ == other.sky_);
+
+ list<Building> other_bld (other.buildings_);
+ list<Building> my_bld;
+ my_bld.splice (my_bld.begin (), buildings_);
+ internal_merge_skyline (&other_bld, &my_bld, &buildings_);
+ assert (is_legal_skyline ());
}
-Skyline_entry::Skyline_entry (Interval i, Real r)
+void
+Skyline::insert (Box const &b, Axis a)
{
- width_ = i;
- height_ = r;
+ list<Building> other_bld;
+ list<Building> my_bld (buildings_);
+ Interval iv = b[a];
+ Real height = sky_ * b[other_axis (a)][sky_];
+
+ single_skyline (Building (iv[LEFT], height, height, iv[RIGHT]), &other_bld);
+ internal_merge_skyline (&other_bld, &my_bld, &buildings_);
+ assert (is_legal_skyline ());
}
void
-heighten_skyline (vector<Skyline_entry> *buildings, Real ground)
+Skyline::raise (Real r)
+{
+ list<Building>::iterator end = buildings_.end ();
+ for (list<Building>::iterator i = buildings_.begin (); i != end; i++)
+ {
+ i->start_height_ += sky_ * r;
+ i->end_height_ += sky_ * r;
+ i->b_ += sky_ * r;
+ }
+ assert (is_legal_skyline ());
+}
+
+Real
+Skyline::distance (Skyline const &other) const
{
- for (vsize i = 0; i < buildings->size (); i++)
- buildings->at (i).height_ += ground;
+ assert (sky_ == -other.sky_);
+ list<Building>::const_iterator i = buildings_.begin ();
+ list<Building>::const_iterator j = other.buildings_.begin ();
+
+ Real dist = -infinity_f;
+ for (; i != buildings_.end () && j != other.buildings_.end (); i++)
+ {
+ while (j->iv_[RIGHT] < i->iv_[LEFT])
+ j++;
+
+ list<Building>::const_iterator k;
+ for (k = j; k->iv_[LEFT] <= i->iv_[RIGHT] && k != other.buildings_.end
(); k++)
+ {
+ Interval iv = intersection (i->iv_, k->iv_);
+ dist = max (dist, max (i->height (iv[LEFT]) + k->height (iv[LEFT]),
+ i->height (iv[RIGHT]) + k->height
(iv[RIGHT])));
+ }
+ }
+ return dist;
}
Real
-skyline_height (vector<Skyline_entry> const &buildings,
- Real airplane,
- Direction sky_dir)
+Skyline::height (Real airplane) const
{
- Real h = - sky_dir * infinity_f;
+ assert (!isinf (airplane));
+
+ list<Building>::const_iterator i;
+ for (i = buildings_.begin (); i != buildings_.end (); i++)
+ {
+ if (i->iv_[RIGHT] > airplane)
+ return sky_ * i->height (airplane);
+ if (i->iv_[RIGHT] == airplane)
+ {
+ assert (i != buildings_.end ());
+ list<Building>::const_iterator j = i;
+ j++;
+ return sky_ * (max (i->end_height_, j->start_height_));
+ }
+ }
+ assert (0);
+ return 0;
+}
- /*
- Ugh! linear, should be O(log n).
- */
- for (vsize i = 0; i < buildings.size (); i++)
- if (buildings[i].width_.contains (airplane))
- h = sky_dir * max (sky_dir * h,
- sky_dir * buildings[i].height_);
-
- return h;
+Real
+Skyline::max_height () const
+{
+ Skyline s (-sky_);
+ s.set_minimum_height (0);
+ return sky_ * distance (s);
}
+void
+Skyline::set_minimum_height (Real h)
+{
+ Skyline s (sky_);
+ s.buildings_.front ().start_height_ = h*sky_;
+ s.buildings_.front ().end_height_ = h*sky_;
+ s.buildings_.front ().b_ = h*sky_;
+ merge (s);
+}
diff --git a/lily/system.cc b/lily/system.cc
index 0649849..3337a77 100644
--- a/lily/system.cc
+++ b/lily/system.cc
@@ -186,6 +186,13 @@ System::get_paper_systems ()
System *system = dynamic_cast<System *> (broken_intos_[i]);
system->post_processing ();
+ system->build_skylines ();
+ if (i > 0)
+ {
+ System *prev = dynamic_cast<System*> (broken_intos_[i-1]);
+ Real r = prev->skylines_[DOWN].distance (system->skylines_[UP]);
+ system->set_property ("skyline-distance", scm_from_double (r));
+ }
scm_vector_set_x (lines, scm_from_int (i),
system->get_paper_system ());
@@ -399,6 +406,7 @@ System::get_paper_system ()
/* information that the page breaker might need */
Grob *right_bound = this->get_bound (RIGHT);
+ pl->set_property ("skyline-distance", get_property ("skyline-distance"));
pl->set_property ("page-break-permission", right_bound->get_property
("page-break-permission"));
pl->set_property ("page-turn-permission", right_bound->get_property
("page-turn-permission"));
pl->set_property ("page-break-penalty", right_bound->get_property
("page-break-penalty"));
@@ -499,6 +507,25 @@ get_root_system (Grob *me)
return dynamic_cast<System*> (system_grob);
}
+void
+System::build_skylines ()
+{
+ vector<Box> boxes;
+ for (vsize i = 0; i < all_elements_->size (); i++)
+ {
+ Grob *g = all_elements_->grob (i);
+ if (!unsmob_stencil (g->get_property ("stencil")))
+ continue;
+
+ Interval xiv = g->extent (this, X_AXIS);
+ Interval yiv = g->extent (this, Y_AXIS);
+ if (!xiv.is_empty () && !yiv.is_empty ())
+ boxes.push_back (Box (xiv, yiv));
+ }
+
+ skylines_[UP] = Skyline (boxes, X_AXIS, UP);
+ skylines_[DOWN] = Skyline (boxes, X_AXIS, DOWN);
+}
ADD_INTERFACE (System, "system-interface",
@@ -510,4 +537,5 @@ ADD_INTERFACE (System, "system-interface
"columns "
"pure-Y-extent "
"spaceable-staves "
+ "skyline-distance "
)
diff --git a/lily/tie-formatting-problem.cc b/lily/tie-formatting-problem.cc
index d22d54b..bb314a6 100644
--- a/lily/tie-formatting-problem.cc
+++ b/lily/tie-formatting-problem.cc
@@ -51,7 +51,7 @@ Tie_formatting_problem::get_attachment (
if (i == chord_outlines_.end ())
programming_error ("Can't find chord outline");
else
- attachments[d] = skyline_height ((*i).second, y, -d);
+ attachments[d] = i->second.height (y);
}
while (flip (&d) != LEFT);
@@ -115,28 +115,6 @@ Tie_formatting_problem::set_column_chord
}
Tuple2<int> key (column_rank, int (dir));
-
- chord_outlines_[key] = empty_skyline (-dir);
-
- if (bounds[0]->break_status_dir ())
- {
- Real x = robust_relative_extent (bounds[0], x_refpoint_, X_AXIS)[-dir];
- chord_outlines_[key].at (0).height_ = x;
- }
- else
- {
- Interval x;
- for (vsize j = 0; j < head_boxes.size (); j++)
- {
- x.unite (head_boxes[j][X_AXIS]);
- }
-
- chord_outlines_[key].at (0).height_ = x[dir];
- }
-
- for (vsize i = 0; i < boxes.size (); i++)
- insert_extent_into_skyline (&chord_outlines_[key] ,
- boxes[i], Y_AXIS, -dir);
if (stem
&& !Stem::is_invisible (stem))
@@ -150,8 +128,8 @@ Tie_formatting_problem::set_column_chord
Direction stemdir = get_grob_direction (stem);
y.add_point (Stem::head_positions (stem)[-stemdir]
* staff_space * .5);
-
- insert_extent_into_skyline (&chord_outlines_[key], Box (x,y), Y_AXIS, -dir);
+
+ boxes.push_back (Box (x, y));
stem_extents_[key].unite (Box (x,y));
@@ -159,8 +137,7 @@ Tie_formatting_problem::set_column_chord
{
Box flag_box = Stem::get_translated_flag (stem).extent_box ();
flag_box.translate( Offset (x[RIGHT], X_AXIS));
- insert_extent_into_skyline (&chord_outlines_[key], flag_box,
- Y_AXIS, -dir);
+ boxes.push_back (flag_box);
}
}
else if (stem)
@@ -176,10 +153,8 @@ Tie_formatting_problem::set_column_chord
Interval y_ext;
for (vsize j = 0; j < head_boxes.size (); j++)
y_ext.unite (head_boxes[j][Y_AXIS]);
-
- insert_extent_into_skyline (&chord_outlines_[key],
- Box (x_ext, y_ext),
- Y_AXIS, -dir);
+
+ boxes.push_back (Box (x_ext, y_ext));
}
Direction updowndir = DOWN;
@@ -197,12 +172,27 @@ Tie_formatting_problem::set_column_chord
}
if (!x.is_empty ())
- insert_extent_into_skyline (&chord_outlines_[key],
- Box (x,y),
- Y_AXIS, -dir);
+ boxes.push_back (Box (x, y));
}
while (flip (&updowndir) != DOWN);
+ chord_outlines_[key] = Skyline (boxes, Y_AXIS, -dir);
+ if (bounds[0]->break_status_dir ())
+ {
+ Real x = robust_relative_extent (bounds[0], x_refpoint_, X_AXIS)[-dir];
+ chord_outlines_[key].set_minimum_height (x);
+ }
+ else
+ {
+ Interval x;
+ for (vsize j = 0; j < head_boxes.size (); j++)
+ {
+ x.unite (head_boxes[j][X_AXIS]);
+ }
+
+ chord_outlines_[key].set_minimum_height (x[dir]);
+ }
+
head_extents_[key].set_empty ();
for (vsize i = 0; i < head_boxes.size (); i++)
{
@@ -344,22 +334,12 @@ Tie_formatting_problem::from_semi_ties (
set_chord_outline (heads, head_dir);
- Real extremal = head_dir * infinity_f;
-
Tuple2<int> head_key (column_rank, head_dir);
Tuple2<int> open_key (column_rank, -head_dir);
-
- for (vsize i = 0; i < chord_outlines_[head_key].size (); i++)
- {
- extremal = head_dir * min (head_dir * extremal,
- head_dir *
chord_outlines_[head_key][i].height_);
- }
+ Real extremal = chord_outlines_[head_key].max_height ();
- Skyline_entry right_entry;
- right_entry.width_.set_full ();
- right_entry.height_ = extremal - head_dir * 1.5;
-
- chord_outlines_[open_key].push_back (right_entry);
+ chord_outlines_[open_key] = Skyline (head_dir);
+ chord_outlines_[open_key].set_minimum_height (extremal - head_dir * 1.5);
}
diff --git a/scm/define-grob-properties.scm b/scm/define-grob-properties.scm
index dddcef9..47f0b8c 100644
--- a/scm/define-grob-properties.scm
+++ b/scm/define-grob-properties.scm
@@ -549,7 +549,7 @@ than a whole rest.")
(spaceable-staves ,ly:grob-array? "Objects to be spaced during page layout.")
-
+ (skyline-distance ,number? "The distance between this staff and the next one,
as determined by a skyline algorithm.")
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; ancient notation
diff --git a/scm/layout-page-layout.scm b/scm/layout-page-layout.scm
index e370a17..090ad06 100644
--- a/scm/layout-page-layout.scm
+++ b/scm/layout-page-layout.scm
@@ -73,9 +73,10 @@ (define (line-minimum-distance line next
"Minimum distance between `line' reference position and `next-line'
reference position. If next-line is #f, return #f."
(and next-line
- (max 0 (- (+ (interval-end (paper-system-extent next-line Y))
- (if ignore-padding 0 (line-next-padding line next-line
layout)))
- (interval-start (paper-system-extent line Y))))))
+ (let ((non-skyline-distance (- (interval-end (paper-system-extent
next-line Y))
+ (interval-start (paper-system-extent line
Y)))))
+ (max 0 (+ (ly:prob-property next-line 'skyline-distance
non-skyline-distance)
+ (if ignore-padding 0 (line-next-padding line next-line
layout)))))))
(define (line-ideal-distance line next-line layout ignore-padding)
"Ideal distance between `line' reference position and `next-line'
------------------------------------------------------------------------
_______________________________________________
lilypond-devel mailing list
address@hidden
http://lists.gnu.org/mailman/listinfo/lilypond-devel