#define EPS 1e-10
static inline bool
-equal (Real x, Real y)
+approx_equal (Real x, Real y)
{
return abs (x - y) < EPS || (isinf (x) && isinf (y) && ((x > 0) == (y > 0)));
}
+static inline bool
+approx_greater_than (Real x, Real y)
+{
+ return x > y + EPS;
+}
+
+static inline bool
+approx_less_than (Real x, Real y)
+{
+ return x < y - EPS;
+}
+
+static inline bool
+approx_less_equal (Real x, Real y)
+{
+ return x <= y + EPS;
+}
+
+static inline bool
+approx_greater_equal (Real x, Real y)
+{
+ return x >= y - EPS;
+}
+
void
Skyline::print () const
{
{
list<Building>::const_iterator i;
Real last_x = -infinity_f;
- Real last_h = -infinity_f;
for (i = buildings_.begin (); i != buildings_.end (); i++)
{
if (i->iv_[LEFT] != last_x)
return false;
- if (i != buildings_.begin () && !equal (i->height_[LEFT], last_h))
- return false;
last_x = i->iv_[RIGHT];
- last_h = i->height_[RIGHT];
+ if (isinf (i->iv_.length ()) && i->height_[LEFT] != i->height_[RIGHT])
+ return false;
}
return last_x == infinity_f;
}
-Building::Building (Real start, Real start_height, Real end_height,
- Real end, Real max_slope)
+Building::Building (Real start, Real start_height, Real end_height, Real end)
: iv_ (start, end)
{
height_[LEFT] = start_height;
height_[RIGHT] = end_height;
- if (isinf (start))
- assert (isinf (start_height) || start_height == end_height);
- if (isinf (end))
- assert (isinf (end_height) || start_height == end_height);
+ if (isinf (start) || isinf (end))
+ assert (start_height == end_height);
- precompute (max_slope);
+ precompute ();
}
void
-Building::precompute (Real max_slope)
+Building::precompute ()
{
slope_ = (height_[RIGHT] - height_[LEFT]) / (iv_.length());
- if (height_[LEFT] == height_[RIGHT])
+ if (height_[LEFT] == height_[RIGHT]) /* in case they're both infinity */
slope_ = 0;
- if (isinf (slope_) || isnan (slope_))
- slope_ = max_slope * (height_[LEFT] < height_[RIGHT] ? 1 : -1);
-
-#if 0
- /*
- this check is sensitive to roundoff errors when converting to/from
- sequences of points.
- */
- assert (abs (slope_) <= max_slope + EPS);
-#endif
-
+
+ assert (!isinf (slope_) && !isnan (slope_));
+
if (isinf (iv_[START]))
{
- if (isinf (iv_[STOP]))
- zero_height_ = height_[LEFT];
- else
- zero_height_ = height_[RIGHT] - slope_ * iv_[STOP];
+ assert (slope_ == 0);
+ y_intercept_ = height_[LEFT];
}
else
- zero_height_ = height_[LEFT] - slope_ * iv_[START];
+ y_intercept_ = height_[LEFT] - slope_ * iv_[START];
}
Real
{
if (isinf (x))
return (x > 0) ? height_[RIGHT] : height_[LEFT];
- return slope_*x + zero_height_;
+ return slope_*x + y_intercept_;
}
void
Real
Building::intersection (Building const &other) const
{
- return (zero_height_ - other.zero_height_) / (other.slope_ - slope_);
+ return (y_intercept_ - other.y_intercept_) / (other.slope_ - slope_);
}
void
-Building::leading_part (Real chop, Real h)
+Building::leading_part (Real chop)
{
- assert (chop > iv_[LEFT] && chop <= iv_[RIGHT] && !equal (chop, iv_[LEFT]));
- assert (equal (h, height (chop)));
+ assert (chop > iv_[LEFT] && chop <= iv_[RIGHT] && !approx_equal (chop, iv_[LEFT]));
iv_[RIGHT] = chop;
- height_[RIGHT] = h;
+ height_[RIGHT] = height (chop);
+}
+
+Building
+Building::sloped_neighbour (Real horizon_padding, Direction d) const
+{
+ Real left = iv_[d];
+ Real right = iv_[d] + d * horizon_padding;
+ Real left_height = height_[d];
+ Real right_height = height_[d] - horizon_padding;
+ if (d == LEFT)
+ {
+ swap (left, right);
+ swap (left_height, right_height);
+ }
+ return Building (left, left_height, right_height, right);
}
static void
skyline_trailing_part (list<Building> *sky, Real x)
{
- if (equal (x, sky->front ().iv_[RIGHT]))
+ if (approx_equal (x, sky->front ().iv_[RIGHT]))
sky->pop_front ();
else
assert (x < sky->front ().iv_[RIGHT]);
}
bool
-Building::obstructs (Building const &other) const
+Building::conceals_beginning (Building const &other) const
{
- if (equal (intersection (other), iv_[LEFT]) || equal (height_[LEFT], other.height_[LEFT]))
- return slope_ > other.slope_ || (slope_ == other.slope_ && zero_height_ > other.zero_height_);
+ if (approx_equal (intersection (other), iv_[LEFT]) || approx_equal (height_[LEFT], other.height_[LEFT]))
+ return slope_ > other.slope_;
return height_[LEFT] > other.height_[LEFT];
}
+bool
+Building::conceals (Building const &other) const
+{
+ assert (iv_[LEFT] <= other.iv_[LEFT]);
+ return (iv_[RIGHT] >= other.iv_[RIGHT])
+ && approx_greater_equal (height (other.iv_[LEFT]), other.height_[LEFT])
+ && approx_greater_equal (height (other.iv_[RIGHT]), other.height_[RIGHT]);
+}
+
void
Skyline::internal_merge_skyline (list<Building> *s1, list<Building> *s2,
list<Building> *const result)
{
while (!s1->empty ())
{
- if (s2->front ().obstructs (s1->front ()))
+ if (s2->front ().conceals_beginning (s1->front ()))
swap (s1, s2);
Building b = s1->front ();
- while (s2->front ().iv_[RIGHT] < b.iv_[RIGHT]
- && s2->front ().height_[RIGHT] <= b.height (s2->front ().iv_[RIGHT]) + EPS)
+ while (!s2->empty () && b.conceals (s2->front ()))
s2->pop_front ();
+ if (s2->empty ())
+ {
+ result->push_front (b);
+ break;
+ }
- /* the front of s2 either intersects with b or it ends after b */
+ /* s2 either intersects with b or it ends after b */
Real end = infinity_f;
+ Real s2_start_height = s2->front ().height_[LEFT];
Real s2_end_height = s2->front ().height_[RIGHT];
+ Real s1_start_height = b.height (s2->front ().iv_[LEFT]);
Real s1_end_height = b.height (s2->front ().iv_[RIGHT]);
- if (s2_end_height > s1_end_height + EPS)
+ if (approx_greater_than (s2_start_height, s1_start_height))
+ end = s2->front ().iv_[LEFT];
+ else if (approx_greater_than (s2_end_height, s1_end_height))
end = b.intersection (s2->front ());
end = min (end, b.iv_[RIGHT]);
- Real height = b.height (end);
- b.leading_part (end, height);
+ b.leading_part (end);
result->push_front (b);
skyline_trailing_part (s1, end);
- if (!s1->empty ())
- s1->front ().height_[LEFT] = height;
skyline_trailing_part (s2, end);
}
result->reverse ();
static void
empty_skyline (list<Building> *const ret)
{
- ret->push_front (Building (-infinity_f, -infinity_f, -infinity_f, infinity_f, 0));
+ ret->push_front (Building (-infinity_f, -infinity_f, -infinity_f, infinity_f));
}
static void
-single_skyline (Building const &b, list<Building> *const ret, Real max_slope)
+single_skyline (Building b, Real horizon_padding, list<Building> *const ret)
{
+ b.iv_.widen (horizon_padding);
+
if (!isinf (b.iv_[RIGHT]))
- ret->push_front (Building (b.iv_[RIGHT], b.height_[RIGHT],
- -infinity_f, infinity_f, max_slope));
+ ret->push_front (Building (b.iv_[RIGHT], -infinity_f,
+ -infinity_f, infinity_f));
+ if (horizon_padding > 0)
+ ret->push_front (b.sloped_neighbour (horizon_padding, RIGHT));
+
if (b.iv_[RIGHT] > b.iv_[LEFT])
ret->push_front (b);
+
+ if (horizon_padding > 0)
+ ret->push_front (b.sloped_neighbour (horizon_padding, LEFT));
if (!isinf (b.iv_[LEFT]))
ret->push_front (Building (-infinity_f, -infinity_f,
- b.height_[LEFT], b.iv_[LEFT], max_slope));
+ -infinity_f, b.iv_[LEFT]));
}
void
}
else if (size == 1)
{
- single_skyline (buildings->front (), result, max_slope_);
+ single_skyline (buildings->front (), 0, result);
return;
}
Skyline::Skyline ()
{
- max_slope_ = 2;
sky_ = UP;
- empty_skyline (&buildings_);
-
-
+ empty_skyline (&buildings_);
}
Skyline::Skyline (Skyline const &src)
{
- max_slope_ = src.max_slope_;
sky_ = src.sky_;
for (list<Building>::const_iterator i = src.buildings_.begin ();
Skyline::Skyline (Direction sky)
{
- max_slope_ = 2;
sky_ = sky;
empty_skyline (&buildings_);
}
/*
- build skyline from a set of boxes.
+ build skyline from a set of boxes. If horizon_padding > 0, expand all the boxes
+ by that amount and add 45-degree sloped boxes to the edges of each box (of
+ width horizon_padding). That is, the total amount of horizontal expansion is
+ horizon_padding*4, half of which is sloped and half of which is flat.
- Boxes should have fatness in the horizon_axis, otherwise they are ignored.
+ Boxes should have fatness in the horizon_axis (after they are expanded by
+ horizon_padding), otherwise they are ignored.
*/
-Skyline::Skyline (vector<Box> const &boxes, Axis horizon_axis, Direction sky)
+Skyline::Skyline (vector<Box> const &boxes, Real horizon_padding, Axis horizon_axis, Direction sky)
{
list<Building> bldgs;
sky_ = sky;
- max_slope_ = 2;
for (vsize i = 0; i < boxes.size (); i++)
{
Interval iv = boxes[i][horizon_axis];
Real height = sky * boxes[i][other_axis (horizon_axis)][sky];
- if (!iv.is_empty () && !isinf (height) && !equal (iv[LEFT], iv[RIGHT]))
- bldgs.push_front (Building (iv[LEFT], height, height, iv[RIGHT],
- max_slope_));
+
+ iv.widen (horizon_padding);
+ if (!iv.is_empty () && !isinf (height) && !approx_equal (iv[LEFT], iv[RIGHT]))
+ {
+ iv.widen (EPS);
+ Building front = Building (iv[LEFT], height, height, iv[RIGHT]);
+ bldgs.push_front (front);
+ if (horizon_padding > 0)
+ {
+ bldgs.push_front (front.sloped_neighbour (horizon_padding, LEFT));
+ bldgs.push_front (front.sloped_neighbour (horizon_padding, RIGHT));
+ }
+ }
}
internal_build_skyline (&bldgs, &buildings_);
assert (is_legal_skyline ());
}
-Skyline::Skyline (vector<Offset> const &points, Real max_slope, Direction sky)
-{
- sky_ = sky;
- max_slope_ = max_slope;
-
- for (vsize i = 1; i < points.size (); i++)
- {
- buildings_.push_back (Building (points[i-1][X_AXIS], sky * points[i-1][Y_AXIS],
- sky * points[i][Y_AXIS],
-
- points[i][X_AXIS],
- max_slope));
-
- }
-
- assert (is_legal_skyline ());
-}
-
void
Skyline::merge (Skyline const &other)
{
}
void
-Skyline::insert (Box const &b, Axis a)
+Skyline::insert (Box const &b, Real horizon_padding, Axis a)
{
list<Building> other_bld;
list<Building> my_bld;
Real height = sky_ * b[other_axis (a)][sky_];
assert (!iv.is_empty ());
+ iv.widen (EPS);
my_bld.splice (my_bld.begin (), buildings_);
- single_skyline (Building (iv[LEFT], height, height, iv[RIGHT], max_slope_), &other_bld, max_slope_);
+ single_skyline (Building (iv[LEFT], height, height, iv[RIGHT]), horizon_padding, &other_bld);
internal_merge_skyline (&other_bld, &my_bld, &buildings_);
assert (is_legal_skyline ());
}
{
i->height_[LEFT] += sky_ * r;
i->height_[RIGHT] += sky_ * r;
- i->zero_height_ += sky_ * r;
+ i->y_intercept_ += sky_ * r;
}
assert (is_legal_skyline ());
}
Skyline s (sky_);
s.buildings_.front ().height_[LEFT] = h * sky_;
s.buildings_.front ().height_[RIGHT] = h * sky_;
- s.buildings_.front ().zero_height_ = h * sky_;
+ s.buildings_.front ().y_intercept_ = h * sky_;
merge (s);
}
{
vector<Offset> out;
- bool first = true;
for (list<Building>::const_iterator i (buildings_.begin ());
i != buildings_.end (); i++)
{
- if (first)
- out.push_back (Offset ((*i).iv_[LEFT], sky_ * (*i).height_[LEFT]));
-
- first = false;
- out.push_back (Offset ((*i).iv_[RIGHT], sky_ * (*i).height_[RIGHT]));
+ if (!isinf (i->iv_[LEFT]) && !isinf (i->height_[LEFT]))
+ out.push_back (Offset (i->iv_[LEFT], sky_ * i->height_[LEFT]));
+ if (!isinf (i->iv_[RIGHT]) && !isinf (i->height_[RIGHT]))
+ out.push_back (Offset (i->iv_[RIGHT], sky_ * i->height_[RIGHT]));
}
-
return out;
}
projects / lilypond.git / commitdiff