1 /* skyline.cc -- implement the Skyline class
3 source file of the GNU LilyPond music typesetter
5 (c) 2006 Joe Neeman <joeneeman@gmail.com>
10 #include "ly-smobs.icc"
12 /* A skyline is a sequence of non-overlapping buildings: something like
22 Each building has a starting position, and ending position, a starting
23 height and an ending height.
25 The following invariants are observed:
26 - the start of the first building is at -infinity
27 - the end of the last building is at infinity
28 - if a building has infinite length (ie. the first and last buildings),
29 then its starting height and ending height are equal
30 - the end of one building is the same as the beginning of the next
33 We also allow skylines to point down (the structure is exactly the same,
34 but we think of the part above the line as being filled with mass and the
35 part below as being empty). ::distance finds the minimum distance between
36 an UP skyline and a DOWN skyline.
38 Note that we store DOWN skylines upside-down. That is, in order to compare
39 a DOWN skyline with an UP skyline, we need to flip the DOWN skyline first.
40 This means that the merging routine doesn't need to be aware of direction,
41 but the distance routine does.
47 approx_equal (Real x, Real y)
49 return abs (x - y) < EPS || (isinf (x) && isinf (y) && ((x > 0) == (y > 0)));
53 approx_greater_than (Real x, Real y)
59 approx_less_than (Real x, Real y)
65 approx_less_equal (Real x, Real y)
71 approx_greater_equal (Real x, Real y)
77 Skyline::print () const
79 for (list<Building>::const_iterator i = buildings_.begin ();
80 i != buildings_.end (); i++)
87 Skyline::is_legal_skyline () const
89 list<Building>::const_iterator i;
90 Real last_x = -infinity_f;
91 for (i = buildings_.begin (); i != buildings_.end (); i++)
93 if (i->iv_[LEFT] != last_x)
95 last_x = i->iv_[RIGHT];
96 if (isinf (i->iv_.length ()) && i->height_[LEFT] != i->height_[RIGHT])
99 return last_x == infinity_f;
102 Building::Building (Real start, Real start_height, Real end_height, Real end)
105 height_[LEFT] = start_height;
106 height_[RIGHT] = end_height;
108 if (isinf (start) || isinf (end))
109 assert (start_height == end_height);
114 Building::Building (Box const &b, Real horizon_padding, Axis horizon_axis, Direction sky)
116 Real height = sky * b[other_axis (horizon_axis)][sky];
118 iv_ = b[horizon_axis];
119 iv_.widen (horizon_padding + EPS);
120 height_[LEFT] = height;
121 height_[RIGHT] = height;
128 Building::precompute ()
130 slope_ = (height_[RIGHT] - height_[LEFT]) / (iv_.length());
131 if (height_[LEFT] == height_[RIGHT]) /* in case they're both infinity */
134 assert (!isinf (slope_) && !isnan (slope_));
136 if (isinf (iv_[START]))
138 assert (slope_ == 0);
139 y_intercept_ = height_[LEFT];
142 y_intercept_ = height_[LEFT] - slope_ * iv_[START];
146 Building::height (Real x) const
149 return (x > 0) ? height_[RIGHT] : height_[LEFT];
150 return slope_*x + y_intercept_;
154 Building::print () const
156 printf ("X[%f,%f] -> Y[%f,%f]\n",
157 iv_[LEFT], iv_[RIGHT],
158 height_[LEFT], height_[RIGHT]);
162 Building::intersection (Building const &other) const
164 return (y_intercept_ - other.y_intercept_) / (other.slope_ - slope_);
168 Building::leading_part (Real chop)
170 assert (chop > iv_[LEFT] && chop <= iv_[RIGHT] && !approx_equal (chop, iv_[LEFT]));
172 height_[RIGHT] = height (chop);
176 Building::sloped_neighbour (Real horizon_padding, Direction d) const
179 Real right = iv_[d] + d * horizon_padding;
180 Real left_height = height_[d];
181 Real right_height = height_[d] - horizon_padding;
185 swap (left_height, right_height);
187 return Building (left, left_height, right_height, right);
191 Building::sane () const
193 return approx_less_than (iv_[LEFT], iv_[RIGHT])
194 && !isinf (height_[RIGHT])
195 && !isinf (height_[LEFT]);
199 skyline_trailing_part (list<Building> *sky, Real x)
201 if (approx_equal (x, sky->front ().iv_[RIGHT]))
204 assert (x < sky->front ().iv_[RIGHT]);
208 sky->front ().iv_[LEFT] = x;
209 sky->front ().height_[LEFT] = sky->front ().height (x);
214 Building::conceals_beginning (Building const &other) const
216 if (approx_equal (intersection (other), iv_[LEFT]) || approx_equal (height_[LEFT], other.height_[LEFT]))
217 return slope_ > other.slope_;
218 return height_[LEFT] > other.height_[LEFT];
222 Building::conceals (Building const &other) const
224 assert (iv_[LEFT] <= other.iv_[LEFT]);
225 return (iv_[RIGHT] >= other.iv_[RIGHT])
226 && approx_greater_equal (height (other.iv_[LEFT]), other.height_[LEFT])
227 && approx_greater_equal (height (other.iv_[RIGHT]), other.height_[RIGHT]);
231 Skyline::internal_merge_skyline (list<Building> *s1, list<Building> *s2,
232 list<Building> *const result)
234 while (!s1->empty ())
236 if (s2->front ().conceals_beginning (s1->front ()))
239 Building b = s1->front ();
240 while (!s2->empty () && b.conceals (s2->front ()))
244 result->push_front (b);
248 /* s2 either intersects with b or it ends after b */
249 Real end = infinity_f;
250 Real s2_start_height = s2->front ().height_[LEFT];
251 Real s2_end_height = s2->front ().height_[RIGHT];
252 Real s1_start_height = b.height (s2->front ().iv_[LEFT]);
253 Real s1_end_height = b.height (s2->front ().iv_[RIGHT]);
254 if (approx_greater_than (s2_start_height, s1_start_height))
255 end = s2->front ().iv_[LEFT];
256 else if (approx_greater_than (s2_end_height, s1_end_height))
257 end = b.intersection (s2->front ());
258 end = min (end, b.iv_[RIGHT]);
260 b.leading_part (end);
261 result->push_front (b);
263 skyline_trailing_part (s1, end);
264 skyline_trailing_part (s2, end);
270 empty_skyline (list<Building> *const ret)
272 ret->push_front (Building (-infinity_f, -infinity_f, -infinity_f, infinity_f));
276 single_skyline (Building b, Real horizon_padding, list<Building> *const ret)
278 b.iv_.widen (horizon_padding);
280 if (!isinf (b.iv_[RIGHT]))
281 ret->push_front (Building (b.iv_[RIGHT], -infinity_f,
282 -infinity_f, infinity_f));
283 if (horizon_padding > 0 && !isinf (b.iv_.length ()))
284 ret->push_front (b.sloped_neighbour (horizon_padding, RIGHT));
286 if (b.iv_[RIGHT] > b.iv_[LEFT])
289 if (horizon_padding > 0 && !isinf (b.iv_.length ()))
290 ret->push_front (b.sloped_neighbour (horizon_padding, LEFT));
291 if (!isinf (b.iv_[LEFT]))
292 ret->push_front (Building (-infinity_f, -infinity_f,
293 -infinity_f, b.iv_[LEFT]));
297 Skyline::internal_build_skyline (list<Building> *buildings, list<Building> *const result)
299 vsize size = buildings->size ();
303 empty_skyline (result);
308 single_skyline (buildings->front (), 0, result);
312 list<Building> right_half;
313 list<Building>::iterator i = buildings->begin ();
315 for (vsize s = 0; s < size/2; s++)
317 right_half.splice (right_half.end (), *buildings, i, buildings->end ());
319 list<Building> right;
321 internal_build_skyline (&right_half, &right);
322 internal_build_skyline (buildings, &left);
323 internal_merge_skyline (&right, &left, result);
329 empty_skyline (&buildings_);
332 Skyline::Skyline (Skyline const &src)
336 for (list<Building>::const_iterator i = src.buildings_.begin ();
337 i != src.buildings_.end (); i++)
339 buildings_.push_back (Building ((*i)));
343 Skyline::Skyline (Direction sky)
346 empty_skyline (&buildings_);
350 build skyline from a set of boxes. If horizon_padding > 0, expand all the boxes
351 by that amount and add 45-degree sloped boxes to the edges of each box (of
352 width horizon_padding). That is, the total amount of horizontal expansion is
353 horizon_padding*4, half of which is sloped and half of which is flat.
355 Boxes should have fatness in the horizon_axis (after they are expanded by
356 horizon_padding), otherwise they are ignored.
358 Skyline::Skyline (vector<Box> const &boxes, Real horizon_padding, Axis horizon_axis, Direction sky)
360 list<Building> bldgs;
363 for (vsize i = 0; i < boxes.size (); i++)
365 Building front (boxes[i], horizon_padding, horizon_axis, sky);
368 bldgs.push_front (front);
369 if (horizon_padding > 0 && !isinf (front.iv_.length ()))
371 bldgs.push_front (front.sloped_neighbour (horizon_padding, LEFT));
372 bldgs.push_front (front.sloped_neighbour (horizon_padding, RIGHT));
377 internal_build_skyline (&bldgs, &buildings_);
378 assert (is_legal_skyline ());
381 Skyline::Skyline (Box const &b, Real horizon_padding, Axis horizon_axis, Direction sky)
384 Building front (b, 0, horizon_axis, sky);
385 single_skyline (front, horizon_padding, &buildings_);
389 Skyline::merge (Skyline const &other)
391 assert (sky_ == other.sky_);
393 list<Building> other_bld (other.buildings_);
394 list<Building> my_bld;
395 my_bld.splice (my_bld.begin (), buildings_);
396 internal_merge_skyline (&other_bld, &my_bld, &buildings_);
397 assert (is_legal_skyline ());
401 Skyline::insert (Box const &b, Real horizon_padding, Axis a)
403 list<Building> other_bld;
404 list<Building> my_bld;
406 my_bld.splice (my_bld.begin (), buildings_);
407 single_skyline (Building (b, 0, a, sky_), horizon_padding, &other_bld);
408 internal_merge_skyline (&other_bld, &my_bld, &buildings_);
409 assert (is_legal_skyline ());
413 Skyline::raise (Real r)
415 list<Building>::iterator end = buildings_.end ();
416 for (list<Building>::iterator i = buildings_.begin (); i != end; i++)
418 i->height_[LEFT] += sky_ * r;
419 i->height_[RIGHT] += sky_ * r;
420 i->y_intercept_ += sky_ * r;
422 assert (is_legal_skyline ());
426 Skyline::shift (Real r)
428 list<Building>::iterator end = buildings_.end ();
429 for (list<Building>::iterator i = buildings_.begin (); i != end; i++)
437 Skyline::distance (Skyline const &other) const
439 assert (sky_ == -other.sky_);
440 list<Building>::const_iterator i = buildings_.begin ();
441 list<Building>::const_iterator j = other.buildings_.begin ();
443 Real dist = -infinity_f;
444 while (i != buildings_.end () && j != other.buildings_.end ())
446 Interval iv = intersection (i->iv_, j->iv_);
447 dist = max (dist, max (i->height (iv[LEFT]) + j->height (iv[LEFT]),
448 i->height (iv[RIGHT]) + j->height (iv[RIGHT])));
449 if (i->iv_[RIGHT] <= j->iv_[RIGHT])
458 Skyline::height (Real airplane) const
460 assert (!isinf (airplane));
462 list<Building>::const_iterator i;
463 for (i = buildings_.begin (); i != buildings_.end (); i++)
465 if (i->iv_[RIGHT] >= airplane)
466 return sky_ * i->height (airplane);
474 Skyline::max_height () const
477 s.set_minimum_height (0);
478 return sky_ * distance (s);
482 Skyline::set_minimum_height (Real h)
485 s.buildings_.front ().height_[LEFT] = h * sky_;
486 s.buildings_.front ().height_[RIGHT] = h * sky_;
487 s.buildings_.front ().y_intercept_ = h * sky_;
493 Skyline::to_points () const
497 for (list<Building>::const_iterator i (buildings_.begin ());
498 i != buildings_.end (); i++)
500 if (!isinf (i->iv_[LEFT]) && !isinf (i->height_[LEFT]))
501 out.push_back (Offset (i->iv_[LEFT], sky_ * i->height_[LEFT]));
502 if (!isinf (i->iv_[RIGHT]) && !isinf (i->height_[RIGHT]))
503 out.push_back (Offset (i->iv_[RIGHT], sky_ * i->height_[RIGHT]));
508 Skyline_pair::Skyline_pair ()
509 : skylines_ (Skyline (DOWN), Skyline (UP))
513 Skyline_pair::Skyline_pair (vector<Box> const &boxes, Real padding, Axis a)
514 : skylines_ (Skyline (boxes, padding, a, DOWN), Skyline (boxes, padding, a, UP))
518 Skyline_pair::Skyline_pair (Box const &b, Real padding, Axis a)
519 : skylines_ (Skyline (b, padding, a, DOWN), Skyline (b, padding, a, UP))
524 Skyline_pair::raise (Real r)
526 skylines_[UP].raise (r);
527 skylines_[DOWN].raise (r);
531 Skyline_pair::shift (Real r)
533 skylines_[UP].shift (r);
534 skylines_[DOWN].shift (r);
538 Skyline_pair::insert (Box const &b, Real padding, Axis a)
540 skylines_[UP].insert (b, padding, a);
541 skylines_[DOWN].insert (b, padding, a);
545 Skyline_pair::merge (Skyline_pair const &other)
547 skylines_[UP].merge (other[UP]);
548 skylines_[DOWN].merge (other[DOWN]);
552 Skyline_pair::operator [] (Direction d)
558 Skyline_pair::operator [] (Direction d) const
563 /****************************************************************/
566 IMPLEMENT_SIMPLE_SMOBS (Skyline);
567 IMPLEMENT_TYPE_P (Skyline, "ly:skyline?");
568 IMPLEMENT_DEFAULT_EQUAL_P (Skyline);
570 IMPLEMENT_SIMPLE_SMOBS (Skyline_pair);
571 IMPLEMENT_TYPE_P (Skyline_pair, "ly:skyline-pair?");
572 IMPLEMENT_DEFAULT_EQUAL_P (Skyline_pair);
575 Skyline::mark_smob (SCM)
581 Skyline::print_smob (SCM s, SCM port, scm_print_state *)
583 Skyline *r = (Skyline *) SCM_CELL_WORD_1 (s);
586 scm_puts ("#<Skyline>", port);
592 Skyline_pair::mark_smob (SCM)
598 Skyline_pair::print_smob (SCM s, SCM port, scm_print_state *)
600 Skyline_pair *r = (Skyline_pair *) SCM_CELL_WORD_1 (s);
603 scm_puts ("#<Skyline-pair>", port);