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.
49 typedef list<Skyline_point> Skyline;
56 this is a cleaner representation, as it doesn't duplicate the X, and
57 doesn't need bogus buildings at infinity --hwn.
60 * All the messing around with EPS is very fishy. There are no
61 complicated numerical algorithms involved, so EPS should not be
72 approx_equal (Real x, Real y)
74 return abs (x - y) < EPS || (isinf (x) && isinf (y) && ((x > 0) == (y > 0)));
78 approx_greater_than (Real x, Real y)
84 approx_less_than (Real x, Real y)
90 approx_less_equal (Real x, Real y)
96 approx_greater_equal (Real x, Real y)
102 Skyline::print () const
104 for (list<Building>::const_iterator i = buildings_.begin ();
105 i != buildings_.end (); i++)
112 Skyline::is_legal_skyline () const
114 list<Building>::const_iterator i;
115 Real last_x = -infinity_f;
116 for (i = buildings_.begin (); i != buildings_.end (); i++)
118 if (i->iv_[LEFT] != last_x)
120 last_x = i->iv_[RIGHT];
121 if (isinf (i->iv_.length ()) && i->height_[LEFT] != i->height_[RIGHT])
124 return last_x == infinity_f;
127 Building::Building (Real start, Real start_height, Real end_height, Real end)
130 height_[LEFT] = start_height;
131 height_[RIGHT] = end_height;
133 if (isinf (start) || isinf (end))
134 assert (start_height == end_height);
139 Building::Building (Box const &b, Real horizon_padding, Axis horizon_axis, Direction sky)
141 Real height = sky * b[other_axis (horizon_axis)][sky];
143 iv_ = b[horizon_axis];
144 iv_.widen (horizon_padding + EPS);
145 height_[LEFT] = height;
146 height_[RIGHT] = height;
153 Building::precompute ()
155 slope_ = (height_[RIGHT] - height_[LEFT]) / (iv_.length());
156 if (height_[LEFT] == height_[RIGHT]) /* in case they're both infinity */
159 assert (!isinf (slope_) && !isnan (slope_));
161 if (isinf (iv_[START]))
163 assert (slope_ == 0);
164 y_intercept_ = height_[LEFT];
167 y_intercept_ = height_[LEFT] - slope_ * iv_[START];
171 Building::height (Real x) const
174 return (x > 0) ? height_[RIGHT] : height_[LEFT];
175 return slope_*x + y_intercept_;
179 Building::print () const
181 printf ("X[%f,%f] -> Y[%f,%f]\n",
182 iv_[LEFT], iv_[RIGHT],
183 height_[LEFT], height_[RIGHT]);
187 Building::intersection_x (Building const &other) const
189 return (y_intercept_ - other.y_intercept_) / (other.slope_ - slope_);
193 Building::leading_part (Real chop)
195 assert (chop > iv_[LEFT] && chop <= iv_[RIGHT] && !approx_equal (chop, iv_[LEFT]));
197 height_[RIGHT] = height (chop);
201 Building::sloped_neighbour (Real horizon_padding, Direction d) const
204 Real right = iv_[d] + d * horizon_padding;
205 Real left_height = height_[d];
206 Real right_height = height_[d] - horizon_padding;
210 swap (left_height, right_height);
212 return Building (left, left_height, right_height, right);
216 Building::sane () const
218 return approx_less_than (iv_[LEFT], iv_[RIGHT])
219 && !isinf (height_[RIGHT])
220 && !isinf (height_[LEFT]);
224 skyline_trailing_part (list<Building> *sky, Real x)
226 if (approx_equal (x, sky->front ().iv_[RIGHT]))
229 assert (x < sky->front ().iv_[RIGHT]);
233 sky->front ().iv_[LEFT] = x;
234 sky->front ().height_[LEFT] = sky->front ().height (x);
239 Building::conceals_beginning (Building const &other) const
242 Real h = other.height (iv_[LEFT]);
243 if (approx_equal (height_[LEFT], h))
244 w = slope_ > other.slope_;
245 else if (height_[LEFT] > h)
254 Building::conceals (Building const &other) const
256 assert (iv_[LEFT] <= other.iv_[LEFT]);
257 return (iv_[RIGHT] >= other.iv_[RIGHT])
258 && approx_greater_equal (height (other.iv_[LEFT]), other.height_[LEFT])
259 && approx_greater_equal (height (other.iv_[RIGHT]), other.height_[RIGHT]);
263 Skyline::internal_merge_skyline (list<Building> *s1, list<Building> *s2,
264 list<Building> *const result)
266 while (!s1->empty ())
268 if (s2->front ().conceals_beginning (s1->front ()))
271 Building b = s1->front ();
272 while (!s2->empty () && b.conceals (s2->front ()))
276 result->push_front (b);
280 /* s2 either intersects with b or it ends after b */
281 Real end = infinity_f;
282 Real s2_start_height = s2->front ().height_[LEFT];
283 Real s2_end_height = s2->front ().height_[RIGHT];
284 Real s1_start_height = b.height (s2->front ().iv_[LEFT]);
285 Real s1_end_height = b.height (s2->front ().iv_[RIGHT]);
286 if (approx_greater_than (s2_start_height, s1_start_height))
287 end = s2->front ().iv_[LEFT];
288 else if (approx_greater_than (s2_end_height, s1_end_height))
289 end = b.intersection_x (s2->front ());
290 end = min (end, b.iv_[RIGHT]);
292 b.leading_part (end);
293 result->push_front (b);
295 skyline_trailing_part (s1, end);
296 skyline_trailing_part (s2, end);
302 empty_skyline (list<Building> *const ret)
304 ret->push_front (Building (-infinity_f, -infinity_f, -infinity_f, infinity_f));
308 single_skyline (Building b, Real horizon_padding, list<Building> *const ret)
310 b.iv_.widen (horizon_padding);
312 if (!isinf (b.iv_[RIGHT]))
313 ret->push_front (Building (b.iv_[RIGHT], -infinity_f,
314 -infinity_f, infinity_f));
315 if (horizon_padding > 0 && !isinf (b.iv_.length ()))
316 ret->push_front (b.sloped_neighbour (horizon_padding, RIGHT));
318 if (b.iv_[RIGHT] > b.iv_[LEFT])
321 if (horizon_padding > 0 && !isinf (b.iv_.length ()))
322 ret->push_front (b.sloped_neighbour (horizon_padding, LEFT));
323 if (!isinf (b.iv_[LEFT]))
324 ret->push_front (Building (-infinity_f, -infinity_f,
325 -infinity_f, b.iv_[LEFT]));
329 Skyline::internal_build_skyline (list<Building> *buildings, list<Building> *const result)
331 vsize size = buildings->size ();
335 empty_skyline (result);
340 single_skyline (buildings->front (), 0, result);
344 list<Building> right_half;
345 list<Building>::iterator i = buildings->begin ();
347 for (vsize s = 0; s < size/2; s++)
349 right_half.splice (right_half.end (), *buildings, i, buildings->end ());
351 list<Building> right;
353 internal_build_skyline (&right_half, &right);
354 internal_build_skyline (buildings, &left);
355 internal_merge_skyline (&right, &left, result);
361 empty_skyline (&buildings_);
364 Skyline::Skyline (Skyline const &src)
368 for (list<Building>::const_iterator i = src.buildings_.begin ();
369 i != src.buildings_.end (); i++)
371 buildings_.push_back (Building ((*i)));
375 Skyline::Skyline (Direction sky)
378 empty_skyline (&buildings_);
382 build skyline from a set of boxes. If horizon_padding > 0, expand all the boxes
383 by that amount and add 45-degree sloped boxes to the edges of each box (of
384 width horizon_padding). That is, the total amount of horizontal expansion is
385 horizon_padding*4, half of which is sloped and half of which is flat.
387 Boxes should have fatness in the horizon_axis (after they are expanded by
388 horizon_padding), otherwise they are ignored.
390 Skyline::Skyline (vector<Box> const &boxes, Real horizon_padding, Axis horizon_axis, Direction sky)
392 list<Building> bldgs;
395 for (vsize i = 0; i < boxes.size (); i++)
397 Building front (boxes[i], horizon_padding, horizon_axis, sky);
400 bldgs.push_front (front);
401 if (horizon_padding > 0 && !isinf (front.iv_.length ()))
403 bldgs.push_front (front.sloped_neighbour (horizon_padding, LEFT));
404 bldgs.push_front (front.sloped_neighbour (horizon_padding, RIGHT));
409 internal_build_skyline (&bldgs, &buildings_);
410 assert (is_legal_skyline ());
413 Skyline::Skyline (Box const &b, Real horizon_padding, Axis horizon_axis, Direction sky)
416 Building front (b, 0, horizon_axis, sky);
417 single_skyline (front, horizon_padding, &buildings_);
421 Skyline::merge (Skyline const &other)
423 assert (sky_ == other.sky_);
425 list<Building> other_bld (other.buildings_);
426 list<Building> my_bld;
427 my_bld.splice (my_bld.begin (), buildings_);
428 internal_merge_skyline (&other_bld, &my_bld, &buildings_);
429 assert (is_legal_skyline ());
433 Skyline::insert (Box const &b, Real horizon_padding, Axis a)
435 list<Building> other_bld;
436 list<Building> my_bld;
438 my_bld.splice (my_bld.begin (), buildings_);
439 single_skyline (Building (b, 0, a, sky_), horizon_padding, &other_bld);
440 internal_merge_skyline (&other_bld, &my_bld, &buildings_);
441 assert (is_legal_skyline ());
445 Skyline::raise (Real r)
447 list<Building>::iterator end = buildings_.end ();
448 for (list<Building>::iterator i = buildings_.begin (); i != end; i++)
450 i->height_[LEFT] += sky_ * r;
451 i->height_[RIGHT] += sky_ * r;
452 i->y_intercept_ += sky_ * r;
454 assert (is_legal_skyline ());
458 Skyline::shift (Real r)
460 list<Building>::iterator end = buildings_.end ();
461 for (list<Building>::iterator i = buildings_.begin (); i != end; i++)
469 Skyline::distance (Skyline const &other) const
471 assert (sky_ == -other.sky_);
472 list<Building>::const_iterator i = buildings_.begin ();
473 list<Building>::const_iterator j = other.buildings_.begin ();
475 Real dist = -infinity_f;
476 while (i != buildings_.end () && j != other.buildings_.end ())
478 Interval iv = intersection (i->iv_, j->iv_);
479 dist = max (dist, max (i->height (iv[LEFT]) + j->height (iv[LEFT]),
480 i->height (iv[RIGHT]) + j->height (iv[RIGHT])));
481 if (i->iv_[RIGHT] <= j->iv_[RIGHT])
490 Skyline::height (Real airplane) const
492 assert (!isinf (airplane));
494 list<Building>::const_iterator i;
495 for (i = buildings_.begin (); i != buildings_.end (); i++)
497 if (i->iv_[RIGHT] >= airplane)
498 return sky_ * i->height (airplane);
506 Skyline::max_height () const
509 s.set_minimum_height (0);
510 return sky_ * distance (s);
514 Skyline::set_minimum_height (Real h)
517 s.buildings_.front ().height_[LEFT] = h * sky_;
518 s.buildings_.front ().height_[RIGHT] = h * sky_;
519 s.buildings_.front ().y_intercept_ = h * sky_;
525 Skyline::to_points () const
529 for (list<Building>::const_iterator i (buildings_.begin ());
530 i != buildings_.end (); i++)
532 if (!isinf (i->iv_[LEFT]) && !isinf (i->height_[LEFT]))
533 out.push_back (Offset (i->iv_[LEFT], sky_ * i->height_[LEFT]));
534 if (!isinf (i->iv_[RIGHT]) && !isinf (i->height_[RIGHT]))
535 out.push_back (Offset (i->iv_[RIGHT], sky_ * i->height_[RIGHT]));
540 Skyline_pair::Skyline_pair ()
541 : skylines_ (Skyline (DOWN), Skyline (UP))
545 Skyline_pair::Skyline_pair (vector<Box> const &boxes, Real padding, Axis a)
546 : skylines_ (Skyline (boxes, padding, a, DOWN), Skyline (boxes, padding, a, UP))
550 Skyline_pair::Skyline_pair (Box const &b, Real padding, Axis a)
551 : skylines_ (Skyline (b, padding, a, DOWN), Skyline (b, padding, a, UP))
556 Skyline_pair::raise (Real r)
558 skylines_[UP].raise (r);
559 skylines_[DOWN].raise (r);
563 Skyline_pair::shift (Real r)
565 skylines_[UP].shift (r);
566 skylines_[DOWN].shift (r);
570 Skyline_pair::insert (Box const &b, Real padding, Axis a)
572 skylines_[UP].insert (b, padding, a);
573 skylines_[DOWN].insert (b, padding, a);
577 Skyline_pair::merge (Skyline_pair const &other)
579 skylines_[UP].merge (other[UP]);
580 skylines_[DOWN].merge (other[DOWN]);
584 Skyline_pair::operator [] (Direction d)
590 Skyline_pair::operator [] (Direction d) const
595 /****************************************************************/
598 IMPLEMENT_SIMPLE_SMOBS (Skyline);
599 IMPLEMENT_TYPE_P (Skyline, "ly:skyline?");
600 IMPLEMENT_DEFAULT_EQUAL_P (Skyline);
602 IMPLEMENT_SIMPLE_SMOBS (Skyline_pair);
603 IMPLEMENT_TYPE_P (Skyline_pair, "ly:skyline-pair?");
604 IMPLEMENT_DEFAULT_EQUAL_P (Skyline_pair);
607 Skyline::mark_smob (SCM)
613 Skyline::print_smob (SCM s, SCM port, scm_print_state *)
615 Skyline *r = (Skyline *) SCM_CELL_WORD_1 (s);
618 scm_puts ("#<Skyline>", port);
624 Skyline_pair::mark_smob (SCM)
630 Skyline_pair::print_smob (SCM s, SCM port, scm_print_state *)
632 Skyline_pair *r = (Skyline_pair *) SCM_CELL_WORD_1 (s);
635 scm_puts ("#<Skyline-pair>", port);