1 /* skyline.cc -- implement the Skyline class
3 source file of the GNU LilyPond music typesetter
5 (c) 2006--2007 Joe Neeman <joeneeman@gmail.com>
11 #include "ly-smobs.icc"
13 /* A skyline is a sequence of non-overlapping buildings: something like
23 Each building has a starting position, and ending position, a starting
24 height and an ending height.
26 The following invariants are observed:
27 - the start of the first building is at -infinity
28 - the end of the last building is at infinity
29 - if a building has infinite length (ie. the first and last buildings),
30 then its starting height and ending height are equal
31 - the end of one building is the same as the beginning of the next
34 We also allow skylines to point down (the structure is exactly the same,
35 but we think of the part above the line as being filled with mass and the
36 part below as being empty). ::distance finds the minimum distance between
37 an UP skyline and a DOWN skyline.
39 Note that we store DOWN skylines upside-down. That is, in order to compare
40 a DOWN skyline with an UP skyline, we need to flip the DOWN skyline first.
41 This means that the merging routine doesn't need to be aware of direction,
42 but the distance routine does.
45 /* If we start including very thin buildings, numerical accuracy errors can
46 arise. Therefore, we ignore all buildings that are less than epsilon wide. */
50 print_buildings (list<Building> const &b)
52 for (list<Building>::const_iterator i = b.begin (); i != b.end (); i++)
57 Skyline::print () const
59 print_buildings (buildings_);
62 Building::Building (Real start, Real start_height, Real end_height, Real end)
64 if (isinf (start) || isinf (end))
65 assert (start_height == end_height);
68 precompute (start, start_height, end_height, end);
71 Building::Building (Box const &b, Real horizon_padding, Axis horizon_axis, Direction sky)
73 Real start = b[horizon_axis][LEFT] - horizon_padding;
74 Real end = b[horizon_axis][RIGHT] + horizon_padding;
75 Real height = sky * b[other_axis (horizon_axis)][sky];
78 precompute (start, height, height, end);
82 Building::precompute (Real start, Real start_height, Real end_height, Real end)
84 slope_ = (end_height - start_height) / (end - start);
85 if (start_height == end_height) /* if they were both infinite, we would get nan, not 0, from the prev line */
88 assert (!isinf (slope_) && !isnan (slope_));
92 assert (start_height == end_height);
93 y_intercept_ = start_height;
96 y_intercept_ = start_height - slope_ * start;
100 Building::height (Real x) const
102 return isinf (x) ? y_intercept_ : slope_*x + y_intercept_;
106 Building::print () const
108 printf ("%f x + %f ends at %f\n", slope_, y_intercept_, end_);
112 Building::intersection_x (Building const &other) const
114 Real ret = (y_intercept_ - other.y_intercept_) / (other.slope_ - slope_);
115 return isnan (ret) ? -infinity_f : ret;
119 Building::leading_part (Real chop)
121 assert (chop <= end_);
126 Building::sloped_neighbour (Real start, Real horizon_padding, Direction d) const
128 Real x = (d == LEFT) ? start : end_;
130 Real right = x + d * horizon_padding;
131 Real left_height = height (x);
132 Real right_height = left_height - horizon_padding;
136 swap (left_height, right_height);
138 return Building (left, left_height, right_height, right);
142 first_intersection (Building const &b, list<Building> *const s, Real start_x)
144 while (!s->empty () && start_x < b.end_)
146 Building c = s->front ();
147 if (c.conceals (b, start_x))
150 Real i = b.intersection_x (c);
151 if (i > start_x && i <= b.end_ && i <= c.end_)
162 Building::conceals (Building const &other, Real x) const
164 if (slope_ == other.slope_)
165 return y_intercept_ > other.y_intercept_;
167 /* their slopes were not equal, so there is an intersection point */
168 Real i = intersection_x (other);
169 return (i <= x && slope_ > other.slope_)
170 || (i > x && slope_ < other.slope_);
174 Skyline::internal_merge_skyline (list<Building> *s1, list<Building> *s2,
175 list<Building> *const result)
177 if (s1->empty () || s2->empty ())
179 programming_error ("tried to merge an empty skyline");
183 Real x = -infinity_f;
184 while (!s1->empty ())
186 if (s2->front ().conceals (s1->front (), x))
189 Building b = s1->front ();
190 Real end = first_intersection (b, s2, x);
194 result->push_front (b);
198 /* only include buildings wider than epsilon */
201 b.leading_part (end);
202 result->push_front (b);
205 if (end >= s1->front ().end_)
214 empty_skyline (list<Building> *const ret)
216 ret->push_front (Building (-infinity_f, -infinity_f, -infinity_f, infinity_f));
220 single_skyline (Building b, Real start, Real horizon_padding, list<Building> *const ret)
222 bool sloped_neighbours = horizon_padding > 0 && !isinf (start) && !isinf (b.end_);
224 ret->push_front (Building (b.end_ + horizon_padding, -infinity_f,
225 -infinity_f, infinity_f));
226 if (sloped_neighbours)
227 ret->push_front (b.sloped_neighbour (start, horizon_padding, RIGHT));
229 if (b.end_ > start + EPS)
232 if (sloped_neighbours)
233 ret->push_front (b.sloped_neighbour (start, horizon_padding, LEFT));
236 ret->push_front (Building (-infinity_f, -infinity_f,
237 -infinity_f, start - horizon_padding));
240 /* remove a non-overlapping set of boxes from BOXES and build a skyline
242 static list<Building>
243 non_overlapping_skyline (list<Box> *const boxes, Real horizon_padding, Axis horizon_axis, Direction sky)
245 list<Building> result;
246 Real last_end = -infinity_f;
247 list<Box>::iterator i = boxes->begin ();
248 while (i != boxes->end ())
250 Interval iv = (*i)[horizon_axis];
252 if (iv[LEFT] - horizon_padding < last_end)
258 if (iv[LEFT] - horizon_padding > last_end + EPS)
259 result.push_front (Building (last_end, -infinity_f, -infinity_f, iv[LEFT] - horizon_padding));
261 Building b (*i, horizon_padding, horizon_axis, sky);
262 bool sloped_neighbours = horizon_padding > 0 && !isinf (iv.length ());
263 if (sloped_neighbours)
264 result.push_front (b.sloped_neighbour (iv[LEFT] - horizon_padding, horizon_padding, LEFT));
265 result.push_front (b);
266 if (sloped_neighbours)
267 result.push_front (b.sloped_neighbour (iv[LEFT] - horizon_padding, horizon_padding, RIGHT));
269 list<Box>::iterator j = i++;
271 last_end = result.front ().end_;
273 if (last_end < infinity_f)
274 result.push_front (Building (last_end, -infinity_f, -infinity_f, infinity_f));
289 bool operator() (Box const &b1, Box const &b2)
291 return b1[a_][LEFT] < b2[a_][LEFT];
296 Skyline::internal_build_skyline (list<Box> *boxes, Real horizon_padding, Axis horizon_axis, Direction sky)
298 vsize size = boxes->size ();
302 list<Building> result;
303 empty_skyline (&result);
308 list<Building> result;
309 single_skyline (Building (boxes->front (), horizon_padding, horizon_axis, sky),
310 boxes->front ()[horizon_axis][LEFT], horizon_axis, &result);
314 deque<list<Building> > partials;
315 boxes->sort (LessThanBox (horizon_axis));
316 while (!boxes->empty ())
317 partials.push_back (non_overlapping_skyline (boxes, horizon_padding, horizon_axis, sky));
319 /* we'd like to say while (partials->size () > 1) but that's O (n).
320 Instead, we exit in the middle of the loop */
321 while (!partials.empty ())
323 list<Building> merged;
324 list<Building> one = partials.front ();
325 partials.pop_front ();
326 if (partials.empty ())
329 list<Building> two = partials.front ();
330 partials.pop_front ();
331 internal_merge_skyline (&one, &two, &merged);
332 partials.push_back (merged);
335 return list<Building> ();
341 empty_skyline (&buildings_);
344 Skyline::Skyline (Skyline const &src)
348 /* doesn't a list's copy constructor do this? -- jneem */
349 for (list<Building>::const_iterator i = src.buildings_.begin ();
350 i != src.buildings_.end (); i++)
352 buildings_.push_back (Building ((*i)));
356 Skyline::Skyline (Direction sky)
359 empty_skyline (&buildings_);
363 build skyline from a set of boxes. If horizon_padding > 0, expand all the boxes
364 by that amount and add 45-degree sloped boxes to the edges of each box (of
365 width horizon_padding). That is, the total amount of horizontal expansion is
366 horizon_padding*4, half of which is sloped and half of which is flat.
368 Boxes should have fatness in the horizon_axis (after they are expanded by
369 horizon_padding), otherwise they are ignored.
371 Skyline::Skyline (vector<Box> const &boxes, Real horizon_padding, Axis horizon_axis, Direction sky)
373 list<Box> filtered_boxes;
376 Axis vert_axis = other_axis (horizon_axis);
377 for (vsize i = 0; i < boxes.size (); i++)
379 Interval iv = boxes[i][horizon_axis];
380 iv.widen (horizon_padding);
381 if (iv.length () > EPS && !boxes[i][vert_axis].is_empty ())
382 filtered_boxes.push_front (boxes[i]);
385 buildings_ = internal_build_skyline (&filtered_boxes, horizon_padding, horizon_axis, sky);
388 Skyline::Skyline (Box const &b, Real horizon_padding, Axis horizon_axis, Direction sky)
391 Building front (b, horizon_padding, horizon_axis, sky);
392 single_skyline (front, b[horizon_axis][LEFT], horizon_padding, &buildings_);
396 Skyline::merge (Skyline const &other)
398 assert (sky_ == other.sky_);
400 list<Building> other_bld (other.buildings_);
401 list<Building> my_bld;
402 my_bld.splice (my_bld.begin (), buildings_);
403 internal_merge_skyline (&other_bld, &my_bld, &buildings_);
407 Skyline::insert (Box const &b, Real horizon_padding, Axis a)
409 list<Building> other_bld;
410 list<Building> my_bld;
412 /* do the same filtering as in Skyline (vector<Box> const&, etc.) */
414 iv.widen (horizon_padding);
415 if (iv.length () <= EPS || b[other_axis (a)].is_empty ())
418 my_bld.splice (my_bld.begin (), buildings_);
419 single_skyline (Building (b, horizon_padding, a, sky_), b[a][LEFT], horizon_padding, &other_bld);
420 internal_merge_skyline (&other_bld, &my_bld, &buildings_);
424 Skyline::raise (Real r)
426 list<Building>::iterator end = buildings_.end ();
427 for (list<Building>::iterator i = buildings_.begin (); i != end; i++)
428 i->y_intercept_ += sky_ * r;
432 Skyline::shift (Real s)
434 list<Building>::iterator end = buildings_.end ();
435 for (list<Building>::iterator i = buildings_.begin (); i != end; i++)
438 i->y_intercept_ -= s * i->slope_;
443 Skyline::distance (Skyline const &other) const
445 assert (sky_ == -other.sky_);
446 list<Building>::const_iterator i = buildings_.begin ();
447 list<Building>::const_iterator j = other.buildings_.begin ();
449 Real dist = -infinity_f;
450 Real start = -infinity_f;
451 while (i != buildings_.end () && j != other.buildings_.end ())
453 Real end = min (i->end_, j->end_);
454 Real start_dist = i->height (start) + j->height (start);
455 Real end_dist = i->height (end) + j->height (end);
456 dist = max (dist, max (start_dist, end_dist));
457 if (i->end_ <= j->end_)
467 Skyline::height (Real airplane) const
469 assert (!isinf (airplane));
471 list<Building>::const_iterator i;
472 for (i = buildings_.begin (); i != buildings_.end (); i++)
474 if (i->end_ >= airplane)
475 return sky_ * i->height (airplane);
483 Skyline::max_height () const
486 s.set_minimum_height (0);
487 return sky_ * distance (s);
491 Skyline::set_minimum_height (Real h)
494 s.buildings_.front ().y_intercept_ = h * sky_;
500 Skyline::to_points (Axis a) const
504 Real start = -infinity_f;
505 for (list<Building>::const_iterator i (buildings_.begin ());
506 i != buildings_.end (); i++)
508 out.push_back (Offset (start, sky_ * i->height (start)));
509 out.push_back (Offset (i->end_, sky_ * i->height (i->end_)));
514 for (vsize i = 0; i < out.size (); i++)
515 out[i] = Offset (out[i][Y_AXIS], out[i][X_AXIS]);
521 Skyline::is_empty () const
523 return buildings_.empty ();
526 Skyline_pair::Skyline_pair ()
527 : skylines_ (Skyline (DOWN), Skyline (UP))
531 Skyline_pair::Skyline_pair (vector<Box> const &boxes, Real padding, Axis a)
532 : skylines_ (Skyline (boxes, padding, a, DOWN), Skyline (boxes, padding, a, UP))
536 Skyline_pair::Skyline_pair (Box const &b, Real padding, Axis a)
537 : skylines_ (Skyline (b, padding, a, DOWN), Skyline (b, padding, a, UP))
542 Skyline_pair::raise (Real r)
544 skylines_[UP].raise (r);
545 skylines_[DOWN].raise (r);
549 Skyline_pair::shift (Real r)
551 skylines_[UP].shift (r);
552 skylines_[DOWN].shift (r);
556 Skyline_pair::insert (Box const &b, Real padding, Axis a)
558 skylines_[UP].insert (b, padding, a);
559 skylines_[DOWN].insert (b, padding, a);
563 Skyline_pair::merge (Skyline_pair const &other)
565 skylines_[UP].merge (other[UP]);
566 skylines_[DOWN].merge (other[DOWN]);
570 Skyline_pair::is_empty () const
572 return skylines_[UP].is_empty ()
573 && skylines_[DOWN].is_empty ();
577 Skyline_pair::operator [] (Direction d)
583 Skyline_pair::operator [] (Direction d) const
588 /****************************************************************/
591 IMPLEMENT_SIMPLE_SMOBS (Skyline);
592 IMPLEMENT_TYPE_P (Skyline, "ly:skyline?");
593 IMPLEMENT_DEFAULT_EQUAL_P (Skyline);
595 IMPLEMENT_SIMPLE_SMOBS (Skyline_pair);
596 IMPLEMENT_TYPE_P (Skyline_pair, "ly:skyline-pair?");
597 IMPLEMENT_DEFAULT_EQUAL_P (Skyline_pair);
600 Skyline::mark_smob (SCM)
602 ASSERT_LIVE_IS_ALLOWED ();
607 Skyline::print_smob (SCM s, SCM port, scm_print_state *)
609 Skyline *r = (Skyline *) SCM_CELL_WORD_1 (s);
612 scm_puts ("#<Skyline>", port);
618 Skyline_pair::mark_smob (SCM)
624 Skyline_pair::print_smob (SCM s, SCM port, scm_print_state *)
626 Skyline_pair *r = (Skyline_pair *) SCM_CELL_WORD_1 (s);
629 scm_puts ("#<Skyline-pair>", port);