From 04ce84386dc022316c347ee0c5049c852eea3421 Mon Sep 17 00:00:00 2001 From: David Kastrup Date: Thu, 6 Jun 2013 17:37:44 +0200 Subject: [PATCH] Issue3383: old-straight-flag + smaller Stem.thickness gives no output and huge over This replaces the numerically imprudent y_intercept_ in buildings with start_height_ and adapts calculations. --- lily/include/skyline.hh | 3 +- lily/skyline.cc | 87 ++++++++++++++++++++--------------------- 2 files changed, 43 insertions(+), 47 deletions(-) diff --git a/lily/include/skyline.hh b/lily/include/skyline.hh index 9a5473ddd5..23aaba30bf 100644 --- a/lily/include/skyline.hh +++ b/lily/include/skyline.hh @@ -34,7 +34,7 @@ struct Building { Real start_; Real end_; - Real y_intercept_; + Real start_height_; Real slope_; void precompute (Real start, Real start_height, Real end_height, Real end); @@ -46,7 +46,6 @@ struct Building Real intersection_x (Building const &other) const; void leading_part (Real chop); bool conceals (Building const &other, Real x) const; - Real shift_to_intersect (Real x, Real y) const; }; class Skyline diff --git a/lily/skyline.cc b/lily/skyline.cc index 5073e69e14..624334ab79 100644 --- a/lily/skyline.cc +++ b/lily/skyline.cc @@ -121,30 +121,42 @@ Building::precompute (Real start, Real start_height, Real end_height, Real end) assert (!isinf (slope_) && !isnan (slope_)); if (isinf (start)) - { - assert (start_height == end_height); - y_intercept_ = start_height; - } - else - y_intercept_ = start_height - slope_ * start; + assert (start_height == end_height); + + start_height_ = start_height; } +// 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) ? y_intercept_ : slope_ * x + y_intercept_; + return (isinf (x) || isinf (start_)) ? start_height_ + : slope_ * (x - start_) + start_height_; } void Building::print () const { - printf ("%f x + %f from %f to %f\n", slope_, y_intercept_, start_, end_); + printf ("%f (x - x0) + %f from %f to %f\n", slope_, start_height_, start_, end_); } inline Real Building::intersection_x (Building const &other) const { - Real ret = (y_intercept_ - other.y_intercept_) / (other.slope_ - slope_); + 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) + */ return isnan (ret) ? -infinity_f : ret; } @@ -155,19 +167,6 @@ Building::leading_part (Real chop) 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 *const s, Real start_x) { @@ -177,7 +176,7 @@ first_intersection (Building const &b, list *const s, Real start_x) // conceals and intersection_x involve multiplication and // division. Avoid that, if we can. - if (c.y_intercept_ == -infinity_f) + if (c.start_height_ == -infinity_f) { if (c.end_ > b.end_) return b.end_; @@ -200,16 +199,12 @@ first_intersection (Building const &b, list *const s, Real start_x) return b.end_; } +// conceals returns true if *this is strictly above other at x + bool Building::conceals (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 height (x) > other.height (x); } // Remove redundant empty buildings from the skyline. @@ -223,7 +218,7 @@ Skyline::normalize () for (i = buildings_.begin (); i != buildings_.end (); i++) { - if (last_empty && i->y_intercept_ == -infinity_f) + if (last_empty && i->start_height_ == -infinity_f) { list::iterator last = i; last--; @@ -231,7 +226,7 @@ Skyline::normalize () buildings_.erase (i); i = last; } - last_empty = (i->y_intercept_ == -infinity_f); + last_empty = (i->start_height_ == -infinity_f); } assert (buildings_.front ().start_ == -infinity_f); @@ -250,10 +245,10 @@ Skyline::deholify () for (right = buildings_.begin (); right != buildings_.end (); right++) { - if (center != buildings_.begin () && center->y_intercept_ == -infinity_f) + if (center != buildings_.begin () && center->start_height_ == -infinity_f) { Real p1 = left->height (left->end_); - Real p2 = right->height (right->start_); + Real p2 = right->start_height_; *center = Building (center->start_, p1, p2, center->end_); left = center; @@ -285,7 +280,7 @@ Skyline::internal_merge_skyline (list *s1, list *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 + if (c.start_height_ == -infinity_f && c.end_ >= b.end_) { list::iterator i = s1->begin (); @@ -293,6 +288,7 @@ Skyline::internal_merge_skyline (list *s1, list *s2, 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_; @@ -303,6 +299,7 @@ Skyline::internal_merge_skyline (list *s1, list *s2, 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; @@ -311,6 +308,7 @@ Skyline::internal_merge_skyline (list *s1, list *s2, 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); @@ -358,7 +356,7 @@ non_overlapping_skyline (list *const buildings) while (i != buildings->end ()) { Real x1 = i->start_; - Real y1 = i->height (i->start_); + Real y1 = i->start_height_; Real x2 = i->end_; Real y2 = i->height (i->end_); @@ -401,7 +399,7 @@ public: bool operator () (Building const &b1, Building const &b2) { return b1.start_ < b2.start_ - || (b1.start_ == b2.start_ && b1.height (b1.start_) > b2.height (b1.start_)); + || (b1.start_ == b2.start_ && b1.start_height_ > b2.start_height_); } }; @@ -611,7 +609,7 @@ Skyline::raise (Real r) { list::iterator end = buildings_.end (); for (list::iterator i = buildings_.begin (); i != end; i++) - i->y_intercept_ += sky_ * r; + i->start_height_ += sky_ * r; } void @@ -622,7 +620,6 @@ Skyline::shift (Real s) { i->start_ += s; i->end_ += s; - i->y_intercept_ -= s * i->slope_; } } @@ -667,7 +664,7 @@ Skyline::padded (Real horizon_padding) const { if (i->start_ > -infinity_f) { - Real height = i->height (i->start_); + Real height = i->start_height_; if (height > -infinity_f) { // Add the sloped building that pads the left side of the current building. @@ -771,7 +768,7 @@ Skyline::max_height () const list::const_iterator i; for (i = buildings_.begin (); i != buildings_.end (); ++i) { - ret = max (ret, i->height (i->start_)); + ret = max (ret, i->start_height_); ret = max (ret, i->height (i->end_)); } @@ -789,7 +786,7 @@ Skyline::left () const { for (list::const_iterator i (buildings_.begin ()); i != buildings_.end (); i++) - if (i->y_intercept_ > -infinity_f) + if (i->start_height_ > -infinity_f) return i->start_; return infinity_f; @@ -800,7 +797,7 @@ Skyline::right () const { for (list::const_reverse_iterator i (buildings_.rbegin ()); i != buildings_.rend (); ++i) - if (i->y_intercept_ > -infinity_f) + if (i->start_height_ > -infinity_f) return i->end_; return -infinity_f; @@ -818,7 +815,7 @@ void Skyline::set_minimum_height (Real h) { Skyline s (sky_); - s.buildings_.front ().y_intercept_ = h * sky_; + s.buildings_.front ().start_height_ = h * sky_; merge (s); } @@ -849,7 +846,7 @@ Skyline::is_empty () const if (!buildings_.size ()) return true; Building b = buildings_.front (); - return b.end_ == infinity_f && b.y_intercept_ == -infinity_f; + return b.end_ == infinity_f && b.start_height_ == -infinity_f; } void -- 2.39.2