/*
This file is part of LilyPond, the GNU music typesetter.
- Copyright (C) 2006--2014 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
return isnan (ret) ? -infinity_f : ret;
}
-void
-Building::leading_part (Real chop)
-{
- assert (chop <= end_);
- end_ = chop;
-}
-
// Returns a shift s such that (x + s, y) intersects the roof of
// this building. If no such shift exists, returns infinity_f.
Real
return infinity_f;
}
-static Real
-first_intersection (Building const &b, list<Building> *s, Real start_x)
-/* Return the first x (start_x <= x <= b.end)
- * where skyline s is clear of Building b.
- * Removes buildings from s that are fully concealed by b. */
+bool
+Building::above (Building const &other, Real x) const
{
- for ( ; !s->empty (); s->pop_front ())
- {
- Building c = s->front ();
-
- start_x = max (start_x, c.start_);
- if (start_x >= b.end_)
- return b.end_;
-
- // height and intersection_x involve multiplication and
- // division. Avoid that, if we can.
- if (c.y_intercept_ != -infinity_f)
- {
- if (c.height (start_x) > b.height (start_x))
- return start_x;
-
- if (c.height (b.end_) > b.height (b.end_))
- {
- Real i = b.intersection_x (c);
- if (i <= b.end_ && i <= c.end_)
- return max (start_x, i);
- }
- }
- if (c.end_ >= b.end_)
- return b.end_; // leave this c on the list s
- }
- return b.end_;
+ 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.
}
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 ())
- programming_error ("tried to merge two empty skylines");
-
- bool s2_pending = false;
- Real last_end = -infinity_f;
- while (!s1->empty () && !s2->empty ())
+ if (sb->empty () || sc->empty ())
{
- Building b = s1->front ();
- Building c = s2->front ();
- if (s2_pending // the head of s2 starts before the head of s1
- || c.height (last_end) > b.height (last_end))
- {
- swap (s1, s2);
- swap (b, c);
- }
- // Now b, the head of s1, starts earlier or lies above s2.
-
- // 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.y_intercept_ == -infinity_f
- && c.end_ >= b.end_)
- {
- list<Building>::iterator i = s1->begin ();
- i++;
- while (i != s1->end () && i->end_ <= c.end_)
- i++;
-
- s1->front ().start_ = last_end;
- result->splice (result->end (), *s1, s1->begin (), i);
- last_end = result->back ().end_;
- continue;
- }
- // first_intersection() removes buildings from s2 if b hides them
- Real x = first_intersection (b, s2, last_end);
- if (s2->empty ())
- break;
-
- if (x > last_end)
- {
- b.leading_part (x); // chops b, leaving the part up to x
- b.start_ = last_end;
- last_end = b.end_;
- result->push_back (b);
- }
-
- b = s1->front ();
- c = s2->front ();
- if (b.end_ <= c.end_)
- {
- // Any trailing part of b is concealed by c
- s1->pop_front ();
- // Consider c next for inclusion in the merged skyline
- s2_pending = true;
- }
- else
- {
- // the trailing part of c is fully exposed, goes directly to merged
- s2->pop_front ();
- c.start_ = last_end;
- last_end = c.end_;
- result->push_back (c);
- }
+ programming_error ("tried to merge an empty skyline");
+ return;
}
- if (last_end < infinity_f)
+
+ Building b = sb->front ();
+ for (; !sc->empty (); sc->pop_front ())
{
- if (!s1->empty ())
+ /* 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 */
{
- s1->front ().start_ = last_end;
- result->splice (result->end (), *s1);
+ 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);
}
- else if (!s2->empty ())
+ else /* b.end_ > c.end_ so finish with c */
{
- s2->front ().start_ = last_end;
- result->splice (result->end (), *s2);
+ 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 (b.end_ > b.start_)
+ result->push_back (b);
}
static void
/****************************************************************/
-const char Skyline::type_p_name_[] = "ly:skyline?";
+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 ());
}