/*
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:
_______
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.
-*/
-/* If we start including very thin buildings, numerical accuracy errors can
- arise. Therefore, we ignore all buildings that are less than epsilon wide. */
-#define EPS 1e-5
+ From 2007 through 2012, buildings of width less than EPS were discarded,
+ citing numerical accuracy concerns. We remember that floating point
+ comparisons of nearly-equal values can be affected by rounding error.
+ Also, some target machines use the x87 floating point unit, which provides
+ extended precision for intermediate results held in registers. On this type
+ of hardware comparisons such as
+ double c = 1.0/3.0; boolean compare = (c == 1.0/3.0)
+ could go either way because the 1.0/3.0 is allowed to be kept
+ higher precision than the variable 'c'.
+ Alert to these considerations, we now accept buildings of zero-width.
+*/
static void
print_buildings (list<Building> const &b)
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;
}
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;
}
-// Returns the interval of horizontal shifts for which this
-// building (pointing up) overlaps the other building (pointing down).
-Interval
-Building::overlapping_shift_interval (Building const &other) const
-{
- Interval iv;
-
- // If one building is empty, there will never be an overlap.
- if (y_intercept_ == -infinity_f || other.y_intercept_ == -infinity_f)
- return iv;
-
- // There are two kinds of interesting positions:
- // - when the horizontal extents of the buildings just touch
- // - when an endpoint of one building intersects the roof of the other.
- // The interval we are looking for is the smallest one that
- // contains all of the interesting points.
-
-
- Real my_y1 = height (start_);
- Real my_y2 = height (end_);
- Real his_y1 = -other.height (other.start_); // "-" because OTHER points down
- Real his_y2 = -other.height (other.end_);
-
- // If both buildings are infinite in the same direction,
- // the return value is either empty or full.
- if ((isinf (start_) && isinf (other.start_))
- || (isinf (end_) && isinf (other.end_)))
- return (y_intercept_ > other.y_intercept_)
- ? Interval (-infinity_f, infinity_f) : Interval ();
-
- // ...when the horizontal extents of the buildings just touch...
- if (my_y1 >= his_y2)
- iv.add_point (other.end_ - start_);
- if (my_y2 >= his_y1)
- iv.add_point (other.start_ - end_);
-
- // ...when an endpoint of one building intersects the roof of the other.
- Real p1 = shift_to_intersect (other.start_, his_y1);
- Real p2 = shift_to_intersect (other.end_, his_y2);
- // "-my_y1" because OTHER points down:
- Real p3 = other.shift_to_intersect (start_, -my_y1);
- Real p4 = other.shift_to_intersect (end_, -my_y2);
- if (!isinf (p1))
- iv.add_point (p1);
- if (!isinf (p2))
- iv.add_point (p2);
- if (!isinf (p3))
- iv.add_point (p3);
- if (!isinf (p4))
- iv.add_point (p4);
-
- return iv;
-}
-
-static Real
-first_intersection (Building const &b, list<Building> *const s, Real start_x)
-{
- 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.y_intercept_ == -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;
-
- 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_;
-}
-
bool
-Building::conceals (Building const &other, Real x) const
+Building::above (Building const &other, Real x) const
{
- if (slope_ == other.slope_)
- return y_intercept_ > other.y_intercept_;
-
- /* their slopes were not equal, so there is an intersection point */
- Real i = intersection_x (other);
- return (i <= x && slope_ > other.slope_)
- || (i > x && slope_ < other.slope_);
+ 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.
{
bool last_empty = false;
list<Building>::iterator i;
+
for (i = buildings_.begin (); i != buildings_.end (); i++)
{
if (last_empty && i->y_intercept_ == -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->y_intercept_ == -infinity_f)
- {
- Real p1 = left->height (left->end_);
- Real p2 = right->height (right->start_);
- *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.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_ = 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 ())
+ /* 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 */
{
- 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);
}
-
- /* only include buildings wider than epsilon */
- if (end > x + EPS)
+ else /* b.end_ > c.end_ so finish with c */
{
- b.leading_part (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
static void
single_skyline (Building b, list<Building> *const ret)
{
- if (b.end_ > b.start_ + EPS)
- {
- ret->push_back (Building (-infinity_f, -infinity_f,
- -infinity_f, b.start_));
- ret->push_back (b);
- ret->push_back (Building (b.end_, -infinity_f,
- -infinity_f, infinity_f));
- }
- else
- {
- empty_skyline (ret);
- }
+ assert (b.end_ >= b.start_);
+
+ if (b.start_ != -infinity_f)
+ ret->push_back (Building (-infinity_f, -infinity_f,
+ -infinity_f, b.start_));
+ ret->push_back (b);
+ if (b.end_ != infinity_f)
+ ret->push_back (Building (b.end_, -infinity_f,
+ -infinity_f, infinity_f));
}
/* remove a non-overlapping set of boxes from BOXES and build a skyline
continue;
}
- if (x1 > last_end + EPS)
+ // Insert empty Buildings into any gaps. (TODO: is this needed? -KOH)
+ if (x1 > last_end)
result.push_back (Building (last_end, -infinity_f, -infinity_f, x1));
result.push_back (*i);
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;
/*
Build skyline from a set of boxes.
- Boxes should have fatness in the horizon_axis, otherwise they are ignored.
+ Boxes should be non-empty on both axes. Otherwise, they will be ignored
*/
Skyline::Skyline (vector<Box> const &boxes, Axis horizon_axis, Direction sky)
{
list<Building> buildings;
sky_ = sky;
- Axis vert_axis = other_axis (horizon_axis);
for (vsize i = 0; i < boxes.size (); i++)
- {
- Interval iv = boxes[i][horizon_axis];
- if (iv.length () > EPS && !boxes[i][vert_axis].is_empty ())
- buildings.push_front (Building (boxes[i], horizon_axis, sky));
- }
+ if (!boxes[i].is_empty (X_AXIS)
+ && !boxes[i].is_empty (Y_AXIS))
+ buildings.push_front (Building (boxes[i], horizon_axis, sky));
buildings_ = internal_build_skyline (&buildings);
normalize ();
/*
build skyline from a set of line segments.
- Buildings should have fatness in the horizon_axis, otherwise they are ignored.
+ Segments can be articulated from left to right or right to left.
+ In the case of the latter, they will be stored internally as left to right.
*/
Skyline::Skyline (vector<Drul_array<Offset> > const &segments, Axis horizon_axis, Direction sky)
{
Real y1 = left[other_axis (horizon_axis)] * sky;
Real y2 = right[other_axis (horizon_axis)] * sky;
- if (x1 + EPS < x2)
+ if (x1 <= x2)
buildings.push_back (Building (x1, y1, y2, x2));
}
Skyline::Skyline (Box const &b, Axis horizon_axis, Direction sky)
{
sky_ = sky;
- Building front (b, horizon_axis, sky);
- single_skyline (front, &buildings_);
+ if (!b.is_empty (X_AXIS) && !b.is_empty (Y_AXIS))
+ {
+ Building front (b, horizon_axis, sky);
+ single_skyline (front, &buildings_);
+ normalize ();
+ }
}
void
}
/* do the same filtering as in Skyline (vector<Box> const&, etc.) */
- Interval iv = b[a];
- if (iv.length () <= EPS || b[other_axis (a)].is_empty ())
+ if (b.is_empty (X_AXIS) || b.is_empty (Y_AXIS))
return;
my_bld.splice (my_bld.begin (), buildings_);
Skyline
Skyline::padded (Real horizon_padding) const
{
+ if (horizon_padding < 0.0)
+ warning ("Cannot have negative horizon padding. Junking.");
+
+ if (horizon_padding <= 0.0)
+ return *this;
+
list<Building> pad_buildings;
for (list<Building>::const_iterator i = buildings_.begin (); i != buildings_.end (); ++i)
{
return sky_ * ret;
}
+Direction
+Skyline::direction () const
+{
+ return sky_;
+}
+
+Real
+Skyline::left () const
+{
+ for (list<Building>::const_iterator i (buildings_.begin ());
+ i != buildings_.end (); i++)
+ if (i->y_intercept_ > -infinity_f)
+ return i->start_;
+
+ return infinity_f;
+}
+
+Real
+Skyline::right () const
+{
+ for (list<Building>::const_reverse_iterator i (buildings_.rbegin ());
+ i != buildings_.rend (); ++i)
+ if (i->y_intercept_ > -infinity_f)
+ return i->end_;
+
+ return -infinity_f;
+}
+
Real
Skyline::max_height_position () const
{
/****************************************************************/
-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 = unsmob<Skyline> (sky);
+ LY_ASSERT_SMOB (Skyline, sky, 1);
+ return scm_from_bool (s->is_empty ());
}
projects / lilypond.git / blobdiff