/*
This file is part of LilyPond, the GNU music typesetter.
- Copyright (C) 2006--2012 Joe Neeman <joeneeman@gmail.com>
+ Copyright (C) 2006--2015 Joe Neeman <joeneeman@gmail.com>
LilyPond is free software: you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
#include <deque>
#include <cstdio>
-#include "ly-smobs.icc"
-
/* A skyline is a sequence of non-overlapping buildings: something like
this:
_______
assert (!isinf (slope_) && !isnan (slope_));
if (isinf (start))
- assert (start_height == end_height);
-
- start_height_ = start_height;
+ {
+ assert (start_height == end_height);
+ y_intercept_ = start_height;
+ }
+ else if (fabs (slope_) > 1e6)
+ // too steep to be stored in slope-intercept form, given round-off error
+ {
+ slope_ = 0.0;
+ y_intercept_ = max (start_height, end_height);
+ }
+ else
+ y_intercept_ = start_height - slope_ * start;
}
-// Because of the way slope is calculated as a ratio of usually small
-// differences, its precision is not sufficient for extrapolating
-// significantly from the original interval. For that reason, we
-// don't store the y0 value that would allow more precalculation by using
-// y = x * slope + y0
-// rather than
-// y = (x - xstart) * slope + ystart
-
inline Real
Building::height (Real x) const
{
- return (isinf (x) || isinf (start_)) ? start_height_
- : slope_ * (x - start_) + start_height_;
+ return isinf (x) ? y_intercept_ : slope_ * x + y_intercept_;
}
void
Building::print () const
{
- printf ("%f (x - x0) + %f from %f to %f\n", slope_, start_height_, start_, end_);
+ printf ("%f x + %f from %f to %f\n", slope_, y_intercept_, start_, end_);
}
inline Real
Building::intersection_x (Building const &other) const
{
- Real ret = start_
- - (other.start_height_ - start_height_
- - other.slope_ * (other.start_ - start_))
- /(other.slope_ - slope_);
- /* A numerically symmetric version would be
- x = (x1+x0)/2 - (y1-y0 - (s1+s0)(x1-x0)/2)/(s1-s0)
- */
+ Real ret = (y_intercept_ - other.y_intercept_) / (other.slope_ - slope_);
return isnan (ret) ? -infinity_f : ret;
}
-void
-Building::leading_part (Real chop)
-{
- assert (chop <= end_);
- end_ = chop;
-}
-
-static Real
-first_intersection (Building const &b, list<Building> *const s, Real start_x)
+// Returns a shift s such that (x + s, y) intersects the roof of
+// this building. If no such shift exists, returns infinity_f.
+Real
+Building::shift_to_intersect (Real x, Real y) const
{
- while (!s->empty () && start_x < b.end_)
- {
- Building c = s->front ();
-
- // conceals and intersection_x involve multiplication and
- // division. Avoid that, if we can.
- if (c.start_height_ == -infinity_f)
- {
- if (c.end_ > b.end_)
- return b.end_;
- start_x = c.end_;
- s->pop_front ();
- continue;
- }
-
- if (c.conceals (b, start_x))
- return start_x;
+ // Solve for s: y = (x + s)*m + b
+ Real ret = (y - y_intercept_ - slope_ * x) / slope_;
- Real i = b.intersection_x (c);
- if (i > start_x && i <= b.end_ && i <= c.end_)
- return i;
-
- start_x = c.end_;
- if (b.end_ > c.end_)
- s->pop_front ();
- }
- return b.end_;
+ if (ret >= start_ && ret <= end_ && !isinf (ret))
+ return ret;
+ return infinity_f;
}
-// conceals returns true if *this is strictly above other at x
-
bool
-Building::conceals (Building const &other, Real x) const
+Building::above (Building const &other, Real x) const
{
- return height (x) > other.height (x);
+ return (isinf (y_intercept_) || isinf (other.y_intercept_) || isinf (x))
+ ? y_intercept_ > other.y_intercept_
+ : (slope_ - other.slope_) * x + y_intercept_ > other.y_intercept_;
}
// Remove redundant empty buildings from the skyline.
for (i = buildings_.begin (); i != buildings_.end (); i++)
{
- if (last_empty && i->start_height_ == -infinity_f)
+ if (last_empty && i->y_intercept_ == -infinity_f)
{
list<Building>::iterator last = i;
last--;
buildings_.erase (i);
i = last;
}
- last_empty = (i->start_height_ == -infinity_f);
+ last_empty = (i->y_intercept_ == -infinity_f);
}
assert (buildings_.front ().start_ == -infinity_f);
}
void
-Skyline::deholify ()
-{
- // Since a skyline should always be normalized, we can
- // assume that there are never two adjacent empty buildings.
- // That is, if center is empty then left and right are not.
- list<Building>::iterator left = buildings_.begin ();
- list<Building>::iterator center = buildings_.begin ();
- list<Building>::iterator right;
-
- for (right = buildings_.begin (); right != buildings_.end (); right++)
- {
- if (center != buildings_.begin () && center->start_height_ == -infinity_f)
- {
- Real p1 = left->height (left->end_);
- Real p2 = right->start_height_;
- *center = Building (center->start_, p1, p2, center->end_);
-
- left = center;
- center = right;
- }
- }
-}
-
-void
-Skyline::internal_merge_skyline (list<Building> *s1, list<Building> *s2,
+Skyline::internal_merge_skyline (list<Building> *sb, list<Building> *sc,
list<Building> *const result) const
{
- if (s1->empty () || s2->empty ())
+ if (sb->empty () || sc->empty ())
{
programming_error ("tried to merge an empty skyline");
return;
}
- Real x = -infinity_f;
- Real last_end = -infinity_f;
- while (!s1->empty ())
+ Building b = sb->front ();
+ for (; !sc->empty (); sc->pop_front ())
{
- if (s2->front ().conceals (s1->front (), x))
- swap (s1, s2);
-
- Building b = s1->front ();
- Building c = s2->front ();
-
- // Optimization: if the other skyline is empty at this point,
- // we can avoid testing some intersections. Just grab as many
- // buildings from s1 as we can, and shove them onto the output.
- if (c.start_height_ == -infinity_f
- && c.end_ >= b.end_)
+ /* Building b is continuing from the previous pass through the loop.
+ Building c is newly-considered, and starts no earlier than b started.
+ The comments draw b as if its roof had zero slope ----.
+ with dashes where b lies above c.
+ The roof of c could rise / or fall \ through the roof of b,
+ or the vertical sides | of c could intersect the roof of b. */
+ Building c = sc->front ();
+ if (b.end_ < c.end_) /* finish with b */
{
- list<Building>::iterator i = s1->begin ();
- i++;
- while (i != s1->end () && i->end_ <= c.end_)
- i++;
-
- s1->front ().start_height_ = s1->front ().height (x);
- s1->front ().start_ = x;
- result->splice (result->end (), *s1, s1->begin (), i);
- x = result->back ().end_;
- last_end = x;
- continue;
- }
-
- Real end = first_intersection (b, s2, x);
- if (s2->empty ())
- {
- b.start_height_ = b.height (last_end);
- b.start_ = last_end;
- result->push_back (b);
- break;
+ if (b.end_ <= b.start_) /* we are already finished with b */
+ ;
+ else if (c.above (b, c.start_)) /* -| . | */
+ {
+ Building m (b);
+ m.end_ = c.start_;
+ if (m.end_ > m.start_)
+ result->push_back (m);
+ if (b.above (c, b.end_)) /* -|\--. */
+ {
+ Building n (c);
+ n.end_ = b.start_ = b.intersection_x (c);
+ result->push_back (n);
+ result->push_back (b);
+ }
+ }
+ else
+ {
+ if (c.above (b, b.end_)) /* ---/ . | */
+ b.end_ = b.intersection_x (c);
+ else /* -----. */
+ c.start_ = b.end_;
+ result->push_back (b);
+ }
+ /* 'c' continues further, so move it into 'b' for the next pass. */
+ b = c;
+ swap (sb, sc);
}
-
- if (end >= x)
+ else /* b.end_ > c.end_ so finish with c */
{
- b.leading_part (end);
- b.start_height_ = b.height (last_end);
- b.start_ = last_end;
- last_end = b.end_;
- result->push_back (b);
+ if (c.above (b, c.start_)) /* -| |---. */
+ {
+ Building m (b);
+ m.end_ = c.start_;
+ if (m.end_ > m.start_)
+ result->push_back (m);
+ if (b.above (c, c.end_)) /* -| \---. */
+ c.end_ = b.intersection_x (c);
+ }
+ else if (c.above (b, c.end_)) /* ---/|--. */
+ {
+ Building m (b);
+ c.start_ = m.end_ = b.intersection_x (c);
+ result->push_back (m);
+ }
+ else /* c is completely hidden by b */
+ continue;
+ result->push_back (c);
+ b.start_ = c.end_;
}
-
- if (end >= s1->front ().end_)
- s1->pop_front ();
-
- x = end;
}
+ if (b.end_ > b.start_)
+ result->push_back (b);
}
static void
while (i != buildings->end ())
{
Real x1 = i->start_;
- Real y1 = i->start_height_;
+ Real y1 = i->height (i->start_);
Real x2 = i->end_;
Real y2 = i->height (i->end_);
bool operator () (Building const &b1, Building const &b2)
{
return b1.start_ < b2.start_
- || (b1.start_ == b2.start_ && b1.start_height_ > b2.start_height_);
+ || (b1.start_ == b2.start_ && b1.height (b1.start_) > b2.height (b1.start_));
}
};
empty_skyline (&buildings_);
}
-Skyline::Skyline (Skyline const &src)
-{
- sky_ = src.sky_;
-
- /* doesn't a list's copy constructor do this? -- jneem */
- for (list<Building>::const_iterator i = src.buildings_.begin ();
- i != src.buildings_.end (); i++)
- {
- buildings_.push_back (Building ((*i)));
- }
-}
-
Skyline::Skyline (Direction sky)
{
sky_ = sky;
{
list<Building>::iterator end = buildings_.end ();
for (list<Building>::iterator i = buildings_.begin (); i != end; i++)
- i->start_height_ += sky_ * r;
+ i->y_intercept_ += sky_ * r;
}
void
{
i->start_ += s;
i->end_ += s;
+ i->y_intercept_ -= s * i->slope_;
}
}
{
if (i->start_ > -infinity_f)
{
- Real height = i->start_height_;
+ Real height = i->height (i->start_);
if (height > -infinity_f)
{
// Add the sloped building that pads the left side of the current building.
list<Building>::const_iterator i;
for (i = buildings_.begin (); i != buildings_.end (); ++i)
{
- ret = max (ret, i->start_height_);
+ ret = max (ret, i->height (i->start_));
ret = max (ret, i->height (i->end_));
}
{
for (list<Building>::const_iterator i (buildings_.begin ());
i != buildings_.end (); i++)
- if (i->start_height_ > -infinity_f)
+ if (i->y_intercept_ > -infinity_f)
return i->start_;
return infinity_f;
{
for (list<Building>::const_reverse_iterator i (buildings_.rbegin ());
i != buildings_.rend (); ++i)
- if (i->start_height_ > -infinity_f)
+ if (i->y_intercept_ > -infinity_f)
return i->end_;
return -infinity_f;
Skyline::set_minimum_height (Real h)
{
Skyline s (sky_);
- s.buildings_.front ().start_height_ = h * sky_;
+ s.buildings_.front ().y_intercept_ = h * sky_;
merge (s);
}
if (!buildings_.size ())
return true;
Building b = buildings_.front ();
- return b.end_ == infinity_f && b.start_height_ == -infinity_f;
+ return b.end_ == infinity_f && b.y_intercept_ == -infinity_f;
}
void
/****************************************************************/
-IMPLEMENT_SIMPLE_SMOBS (Skyline);
-IMPLEMENT_TYPE_P (Skyline, "ly:skyline?");
-IMPLEMENT_DEFAULT_EQUAL_P (Skyline);
-
-SCM
-Skyline::mark_smob (SCM s)
-{
- ASSERT_LIVE_IS_ALLOWED (s);
- return SCM_EOL;
-}
-
-int
-Skyline::print_smob (SCM s, SCM port, scm_print_state *)
-{
- Skyline *r = (Skyline *) SCM_CELL_WORD_1 (s);
- (void) r;
-
- scm_puts ("#<Skyline>", port);
-
- return 1;
-}
+const char * const Skyline::type_p_name_ = "ly:skyline?";
MAKE_SCHEME_CALLBACK_WITH_OPTARGS (Skyline, get_touching_point, 3, 1, "")
SCM
LY_ASSERT_SMOB (Skyline, other_skyline_scm, 1);
Real horizon_padding = 0;
- if (horizon_padding_scm != SCM_UNDEFINED)
+ if (!SCM_UNBNDP (horizon_padding_scm))
{
LY_ASSERT_TYPE (scm_is_number, horizon_padding_scm, 3);
horizon_padding = scm_to_double (horizon_padding_scm);
}
- Skyline *skyline = Skyline::unsmob (skyline_scm);
- Skyline *other_skyline = Skyline::unsmob (other_skyline_scm);
+ Skyline *skyline = unsmob<Skyline> (skyline_scm);
+ Skyline *other_skyline = unsmob<Skyline> (other_skyline_scm);
return scm_from_double (skyline->touching_point (*other_skyline, horizon_padding));
}
LY_ASSERT_SMOB (Skyline, other_skyline_scm, 1);
Real horizon_padding = 0;
- if (horizon_padding_scm != SCM_UNDEFINED)
+ if (!SCM_UNBNDP (horizon_padding_scm))
{
LY_ASSERT_TYPE (scm_is_number, horizon_padding_scm, 3);
horizon_padding = scm_to_double (horizon_padding_scm);
}
- Skyline *skyline = Skyline::unsmob (skyline_scm);
- Skyline *other_skyline = Skyline::unsmob (other_skyline_scm);
+ Skyline *skyline = unsmob<Skyline> (skyline_scm);
+ Skyline *other_skyline = unsmob<Skyline> (other_skyline_scm);
return scm_from_double (skyline->distance (*other_skyline, horizon_padding));
}
SCM
Skyline::get_max_height (SCM skyline_scm)
{
- return scm_from_double (Skyline::unsmob (skyline_scm)->max_height ());
+ return scm_from_double (unsmob<Skyline> (skyline_scm)->max_height ());
}
MAKE_SCHEME_CALLBACK (Skyline, get_max_height_position, 1)
SCM
Skyline::get_max_height_position (SCM skyline_scm)
{
- return scm_from_double (Skyline::unsmob (skyline_scm)->max_height_position ());
+ return scm_from_double (unsmob<Skyline> (skyline_scm)->max_height_position ());
}
MAKE_SCHEME_CALLBACK (Skyline, get_height, 2)
Skyline::get_height (SCM skyline_scm, SCM x_scm)
{
Real x = robust_scm2double (x_scm, 0.0);
- return scm_from_double (Skyline::unsmob (skyline_scm)->height (x));
+ return scm_from_double (unsmob<Skyline> (skyline_scm)->height (x));
}
LY_DEFINE (ly_skyline_empty_p, "ly:skyline-empty?",
1, 0, 0, (SCM sky),
"Return whether @var{sky} is empty.")
{
- Skyline *s = Skyline::unsmob (sky);
+ Skyline *s = unsmob<Skyline> (sky);
LY_ASSERT_SMOB (Skyline, sky, 1);
return scm_from_bool (s->is_empty ());
}