/*
This file is part of LilyPond, the GNU music typesetter.
- Copyright (C) 2006--2012 Joe Neeman <joeneeman@gmail.com>
+ Copyright (C) 2006--2014 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
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;
}
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
+Building::shift_to_intersect (Real x, Real y) const
+{
+ // Solve for s: y = (x + s)*m + b
+ Real ret = (y - y_intercept_ - slope_ * x) / slope_;
+
+ if (ret >= start_ && ret <= end_ && !isinf (ret))
+ return ret;
+ return infinity_f;
+}
+
static Real
-first_intersection (Building const &b, list<Building> *const s, Real start_x)
+first_intersection (Building const &b, list<Building> *s, Real start_x)
+/* Return the first x >= start_x where skyline s above Building b.
+ * Removes buildings from s that are concealed by b. */
{
while (!s->empty () && start_x < b.end_)
{
// conceals and intersection_x involve multiplication and
// division. Avoid that, if we can.
- if (c.start_height_ == -infinity_f)
+ if (c.y_intercept_ == -infinity_f)
{
if (c.end_ > b.end_)
return b.end_;
return b.end_;
}
-// conceals returns true if *this is strictly above other at x
-
bool
Building::conceals (Building const &other, Real x) const
{
- return height (x) > other.height (x);
+ 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_);
}
// 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);
for (right = buildings_.begin (); right != buildings_.end (); right++)
{
- if (center != buildings_.begin () && center->start_height_ == -infinity_f)
+ if (center != buildings_.begin () && center->y_intercept_ == -infinity_f)
{
Real p1 = left->height (left->end_);
- Real p2 = right->start_height_;
+ Real p2 = right->height (right->start_);
*center = Building (center->start_, p1, p2, center->end_);
left = center;
// 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
+ if (c.y_intercept_ == -infinity_f
&& c.end_ >= b.end_)
{
list<Building>::iterator i = s1->begin ();
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;
}
-
+ // first_intersection() removes buildings from s2 if b hides them
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;
}
+ // Should be (end > x), during ver2.19. end == x happens fairly often,
+ // and we do not need to keep vertical segments within a skyline.
if (end >= x)
{
b.leading_part (end);
- b.start_height_ = b.height (last_end);
b.start_ = last_end;
last_end = b.end_;
result->push_back (b);
if (end >= s1->front ().end_)
s1->pop_front ();
+ // Should add during ver2.19 (to avoid an endless loop
+ // when merging identical skylines with a vertical segment)
+ // if (end >= s2->front().end_) s2->pop_front();
x = end;
}
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
projects / lilypond.git / blobdiff