2 This file is part of LilyPond, the GNU music typesetter.
4 Copyright (C) 2006--2011 Joe Neeman <joeneeman@gmail.com>
6 LilyPond is free software: you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation, either version 3 of the License, or
9 (at your option) any later version.
11 LilyPond is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
16 You should have received a copy of the GNU General Public License
17 along with LilyPond. If not, see <http://www.gnu.org/licenses/>.
24 #include "ly-smobs.icc"
26 /* A skyline is a sequence of non-overlapping buildings: something like
36 Each building has a starting position, and ending position, a starting
37 height and an ending height.
39 The following invariants are observed:
40 - the start of the first building is at -infinity
41 - the end of the last building is at infinity
42 - if a building has infinite length (ie. the first and last buildings),
43 then its starting height and ending height are equal
44 - the end of one building is the same as the beginning of the next
47 We also allow skylines to point down (the structure is exactly the same,
48 but we think of the part above the line as being filled with mass and the
49 part below as being empty). ::distance finds the minimum distance between
50 an UP skyline and a DOWN skyline.
52 Note that we store DOWN skylines upside-down. That is, in order to compare
53 a DOWN skyline with an UP skyline, we need to flip the DOWN skyline first.
54 This means that the merging routine doesn't need to be aware of direction,
55 but the distance routine does.
58 /* If we start including very thin buildings, numerical accuracy errors can
59 arise. Therefore, we ignore all buildings that are less than epsilon wide. */
63 print_buildings (list<Building> const &b)
65 for (list<Building>::const_iterator i = b.begin (); i != b.end (); i++)
70 Skyline::print () const
72 print_buildings (buildings_);
76 Skyline::print_points () const
78 vector<Offset> ps (to_points (X_AXIS));
80 for (vsize i = 0; i < ps.size (); i++)
81 printf ("(%f,%f)%s", ps[i][X_AXIS], ps[i][Y_AXIS],
82 (i % 2) == 1 ? "\n" : " ");
85 Building::Building (Real start, Real start_height, Real end_height, Real end)
87 if (isinf (start) || isinf (end))
88 assert (start_height == end_height);
91 precompute (start, start_height, end_height, end);
94 Building::Building (Box const &b, Real horizon_padding, Axis horizon_axis, Direction sky)
96 Real start = b[horizon_axis][LEFT] - horizon_padding;
97 Real end = b[horizon_axis][RIGHT] + horizon_padding;
98 Real height = sky * b[other_axis (horizon_axis)][sky];
101 precompute (start, height, height, end);
105 Building::precompute (Real start, Real start_height, Real end_height, Real end)
107 slope_ = (end_height - start_height) / (end - start);
108 if (start_height == end_height) /* if they were both infinite, we would get nan, not 0, from the prev line */
111 assert (!isinf (slope_) && !isnan (slope_));
115 assert (start_height == end_height);
116 y_intercept_ = start_height;
119 y_intercept_ = start_height - slope_ * start;
123 Building::height (Real x) const
125 return isinf (x) ? y_intercept_ : slope_ * x + y_intercept_;
129 Building::print () const
131 printf ("%f x + %f ends at %f\n", slope_, y_intercept_, end_);
135 Building::intersection_x (Building const &other) const
137 Real ret = (y_intercept_ - other.y_intercept_) / (other.slope_ - slope_);
138 return isnan (ret) ? -infinity_f : ret;
142 Building::leading_part (Real chop)
144 assert (chop <= end_);
149 Building::sloped_neighbour (Real start, Real horizon_padding, Direction d) const
151 Real x = (d == LEFT) ? start : end_;
153 Real right = x + d * horizon_padding;
154 Real left_height = height (x);
155 Real right_height = left_height - horizon_padding;
159 swap (left_height, right_height);
161 return Building (left, left_height, right_height, right);
165 first_intersection (Building const &b, list<Building> *const s, Real start_x)
167 while (!s->empty () && start_x < b.end_)
169 Building c = s->front ();
170 if (c.conceals (b, start_x))
173 Real i = b.intersection_x (c);
174 if (i > start_x && i <= b.end_ && i <= c.end_)
185 Building::conceals (Building const &other, Real x) const
187 if (slope_ == other.slope_)
188 return y_intercept_ > other.y_intercept_;
190 /* their slopes were not equal, so there is an intersection point */
191 Real i = intersection_x (other);
192 return (i <= x && slope_ > other.slope_)
193 || (i > x && slope_ < other.slope_);
197 Skyline::internal_merge_skyline (list<Building> *s1, list<Building> *s2,
198 list<Building> *const result)
200 if (s1->empty () || s2->empty ())
202 programming_error ("tried to merge an empty skyline");
206 Real x = -infinity_f;
207 while (!s1->empty ())
209 if (s2->front ().conceals (s1->front (), x))
212 Building b = s1->front ();
213 Real end = first_intersection (b, s2, x);
217 result->push_front (b);
221 /* only include buildings wider than epsilon */
224 b.leading_part (end);
225 result->push_front (b);
228 if (end >= s1->front ().end_)
237 empty_skyline (list<Building> *const ret)
239 ret->push_front (Building (-infinity_f, -infinity_f, -infinity_f, infinity_f));
243 Given Building 'b' with starting wall location 'start', extend each side
244 with a sloped roofline of width 'horizon_padding'; put the skyline in 'ret'
247 single_skyline (Building b, Real start, Real horizon_padding, list<Building> *const ret)
249 bool sloped_neighbours = horizon_padding > 0 && !isinf (start) && !isinf (b.end_);
251 ret->push_front (Building (b.end_ + horizon_padding, -infinity_f,
252 -infinity_f, infinity_f));
253 if (sloped_neighbours)
254 ret->push_front (b.sloped_neighbour (start, horizon_padding, RIGHT));
256 if (b.end_ > start + EPS)
259 if (sloped_neighbours)
260 ret->push_front (b.sloped_neighbour (start, horizon_padding, LEFT));
263 ret->push_front (Building (-infinity_f, -infinity_f,
264 -infinity_f, start - horizon_padding));
267 /* remove a non-overlapping set of boxes from BOXES and build a skyline
269 static list<Building>
270 non_overlapping_skyline (list<Box> *const boxes, Real horizon_padding, Axis horizon_axis, Direction sky)
272 list<Building> result;
273 Real last_end = -infinity_f;
274 list<Box>::iterator i = boxes->begin ();
275 while (i != boxes->end ())
277 Interval iv = (*i)[horizon_axis];
279 if (iv[LEFT] - horizon_padding < last_end)
285 if (iv[LEFT] - horizon_padding > last_end + EPS)
286 result.push_front (Building (last_end, -infinity_f, -infinity_f, iv[LEFT] - 2 * horizon_padding));
288 Building b (*i, horizon_padding, horizon_axis, sky);
289 bool sloped_neighbours = horizon_padding > 0 && !isinf (iv.length ());
290 if (sloped_neighbours)
291 result.push_front (b.sloped_neighbour (iv[LEFT] - horizon_padding, horizon_padding, LEFT));
292 result.push_front (b);
293 if (sloped_neighbours)
294 result.push_front (b.sloped_neighbour (iv[LEFT] - horizon_padding, horizon_padding, RIGHT));
296 list<Box>::iterator j = i++;
298 last_end = result.front ().end_;
300 if (last_end < infinity_f)
301 result.push_front (Building (last_end, -infinity_f, -infinity_f, infinity_f));
316 bool operator () (Box const &b1, Box const &b2)
318 return b1[a_][LEFT] < b2[a_][LEFT];
323 Skyline::internal_build_skyline (list<Box> *boxes, Real horizon_padding, Axis horizon_axis, Direction sky)
325 vsize size = boxes->size ();
329 list<Building> result;
330 empty_skyline (&result);
335 list<Building> result;
336 single_skyline (Building (boxes->front (), horizon_padding, horizon_axis, sky),
337 boxes->front ()[horizon_axis][LEFT] - horizon_padding,
338 horizon_padding, &result);
342 deque<list<Building> > partials;
343 boxes->sort (LessThanBox (horizon_axis));
344 while (!boxes->empty ())
345 partials.push_back (non_overlapping_skyline (boxes, horizon_padding, horizon_axis, sky));
347 /* we'd like to say while (partials->size () > 1) but that's O (n).
348 Instead, we exit in the middle of the loop */
349 while (!partials.empty ())
351 list<Building> merged;
352 list<Building> one = partials.front ();
353 partials.pop_front ();
354 if (partials.empty ())
357 list<Building> two = partials.front ();
358 partials.pop_front ();
359 internal_merge_skyline (&one, &two, &merged);
360 partials.push_back (merged);
363 return list<Building> ();
369 empty_skyline (&buildings_);
372 Skyline::Skyline (Skyline const &src)
376 /* doesn't a list's copy constructor do this? -- jneem */
377 for (list<Building>::const_iterator i = src.buildings_.begin ();
378 i != src.buildings_.end (); i++)
380 buildings_.push_back (Building ((*i)));
384 Skyline::Skyline (Direction sky)
387 empty_skyline (&buildings_);
391 build padded skyline from an existing skyline with padding
395 Skyline::Skyline (Skyline const &src, Real horizon_padding, Axis /*a*/)
398 We extract boxes from the skyline, then build a new skyline from
400 A box is created for every horizontal portion of the skyline
401 Because skylines are defined positive, and then inverted if they
402 are to be down-facing, we create the new skyline in the UP
403 direction, then give it the down direction if needed.
405 Real start = -infinity_f;
408 // establish a baseline box
409 // FIXME: This has hardcoded logic, assuming a == X_AXIS!
410 boxes.push_back (Box (Interval (-infinity_f, infinity_f),
412 list<Building>::const_iterator end = src.buildings_.end ();
413 for (list<Building>::const_iterator i = src.buildings_.begin (); i != end; start = i->end_, i++)
414 if ((i->slope_ == 0) && !isinf (i->y_intercept_))
415 boxes.push_back (Box (Interval (start, i->end_),
416 Interval (-infinity_f, i->y_intercept_)));
417 buildings_ = internal_build_skyline (&boxes, horizon_padding, X_AXIS, UP);
422 build skyline from a set of boxes. If horizon_padding > 0, expand all the boxes
423 by that amount and add 45-degree sloped boxes to the edges of each box (of
424 width horizon_padding). That is, the total amount of horizontal expansion is
425 horizon_padding*4, half of which is sloped and half of which is flat.
427 Boxes should have fatness in the horizon_axis (after they are expanded by
428 horizon_padding), otherwise they are ignored.
430 Skyline::Skyline (vector<Box> const &boxes, Real horizon_padding, Axis horizon_axis, Direction sky)
432 list<Box> filtered_boxes;
435 Axis vert_axis = other_axis (horizon_axis);
436 for (vsize i = 0; i < boxes.size (); i++)
438 Interval iv = boxes[i][horizon_axis];
439 iv.widen (horizon_padding);
440 if (iv.length () > EPS && !boxes[i][vert_axis].is_empty ())
441 filtered_boxes.push_front (boxes[i]);
444 buildings_ = internal_build_skyline (&filtered_boxes, horizon_padding, horizon_axis, sky);
447 Skyline::Skyline (Box const &b, Real horizon_padding, Axis horizon_axis, Direction sky)
450 Building front (b, horizon_padding, horizon_axis, sky);
451 single_skyline (front, b[horizon_axis][LEFT] - horizon_padding,
452 horizon_padding, &buildings_);
456 Skyline::merge (Skyline const &other)
458 assert (sky_ == other.sky_);
460 list<Building> other_bld (other.buildings_);
461 list<Building> my_bld;
462 my_bld.splice (my_bld.begin (), buildings_);
463 internal_merge_skyline (&other_bld, &my_bld, &buildings_);
467 Skyline::insert (Box const &b, Real horizon_padding, Axis a)
469 list<Building> other_bld;
470 list<Building> my_bld;
472 if (isnan (b[other_axis (a)][LEFT])
473 || isnan (b[other_axis (a)][RIGHT]))
475 programming_error ("insane box for skyline");
479 /* do the same filtering as in Skyline (vector<Box> const&, etc.) */
481 iv.widen (horizon_padding);
482 if (iv.length () <= EPS || b[other_axis (a)].is_empty ())
485 my_bld.splice (my_bld.begin (), buildings_);
486 single_skyline (Building (b, horizon_padding, a, sky_), b[a][LEFT] - horizon_padding,
487 horizon_padding, &other_bld);
488 internal_merge_skyline (&other_bld, &my_bld, &buildings_);
492 Skyline::raise (Real r)
494 list<Building>::iterator end = buildings_.end ();
495 for (list<Building>::iterator i = buildings_.begin (); i != end; i++)
496 i->y_intercept_ += sky_ * r;
500 Skyline::shift (Real s)
502 list<Building>::iterator end = buildings_.end ();
503 for (list<Building>::iterator i = buildings_.begin (); i != end; i++)
506 i->y_intercept_ -= s * i->slope_;
511 Skyline::distance (Skyline const &other, Real horizon_padding) const
513 assert (sky_ == -other.sky_);
515 Skyline const *padded_this = this;
516 Skyline const *padded_other = &other;
517 bool created_tmp_skylines = false;
520 For systems, padding is not added at creation time. Padding is
521 added to AxisGroup objects when outside-staff objects are added.
522 Thus, when we want to place systems with horizontal padding,
523 we do it at distance calculation time.
525 if (horizon_padding != 0.0)
527 padded_this = new Skyline (*padded_this, horizon_padding, X_AXIS);
528 padded_other = new Skyline (*padded_other, horizon_padding, X_AXIS);
529 created_tmp_skylines = true;
532 list<Building>::const_iterator i = padded_this->buildings_.begin ();
533 list<Building>::const_iterator j = padded_other->buildings_.begin ();
535 Real dist = -infinity_f;
536 Real start = -infinity_f;
537 while (i != padded_this->buildings_.end () && j != padded_other->buildings_.end ())
539 Real end = min (i->end_, j->end_);
540 Real start_dist = i->height (start) + j->height (start);
541 Real end_dist = i->height (end) + j->height (end);
542 dist = max (dist, max (start_dist, end_dist));
543 if (i->end_ <= j->end_)
550 if (created_tmp_skylines)
560 Skyline::height (Real airplane) const
562 assert (!isinf (airplane));
564 list<Building>::const_iterator i;
565 for (i = buildings_.begin (); i != buildings_.end (); i++)
567 if (i->end_ >= airplane)
568 return sky_ * i->height (airplane);
576 Skyline::max_height () const
579 s.set_minimum_height (0);
580 return sky_ * distance (s);
584 Skyline::set_minimum_height (Real h)
587 s.buildings_.front ().y_intercept_ = h * sky_;
592 Skyline::to_points (Axis horizon_axis) const
596 Real start = -infinity_f;
597 for (list<Building>::const_iterator i (buildings_.begin ());
598 i != buildings_.end (); i++)
600 out.push_back (Offset (start, sky_ * i->height (start)));
601 out.push_back (Offset (i->end_, sky_ * i->height (i->end_)));
605 if (horizon_axis == Y_AXIS)
606 for (vsize i = 0; i < out.size (); i++)
607 out[i] = out[i].swapped ();
613 Skyline::is_empty () const
615 Building b = buildings_.front ();
616 return b.end_ == infinity_f && b.y_intercept_ == -infinity_f;
623 empty_skyline (&buildings_);
626 /****************************************************************/
628 IMPLEMENT_SIMPLE_SMOBS (Skyline);
629 IMPLEMENT_TYPE_P (Skyline, "ly:skyline?");
630 IMPLEMENT_DEFAULT_EQUAL_P (Skyline);
633 Skyline::mark_smob (SCM)
635 ASSERT_LIVE_IS_ALLOWED ();
640 Skyline::print_smob (SCM s, SCM port, scm_print_state *)
642 Skyline *r = (Skyline *) SCM_CELL_WORD_1 (s);
645 scm_puts ("#<Skyline>", port);