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;
519 For systems, padding is not added at creation time. Padding is
520 added to AxisGroup objects when outside-staff objects are added.
521 Thus, when we want to place systems with horizontal padding,
522 we do it at distance calculation time.
524 if (horizon_padding != 0.0)
526 padded_this = new Skyline (*padded_this, horizon_padding, X_AXIS);
527 padded_other = new Skyline (*padded_other, horizon_padding, X_AXIS);
530 list<Building>::const_iterator i = padded_this->buildings_.begin ();
531 list<Building>::const_iterator j = padded_other->buildings_.begin ();
533 Real dist = -infinity_f;
534 Real start = -infinity_f;
535 while (i != padded_this->buildings_.end () && j != padded_other->buildings_.end ())
537 Real end = min (i->end_, j->end_);
538 Real start_dist = i->height (start) + j->height (start);
539 Real end_dist = i->height (end) + j->height (end);
540 dist = max (dist, max (start_dist, end_dist));
541 if (i->end_ <= j->end_)
551 Skyline::height (Real airplane) const
553 assert (!isinf (airplane));
555 list<Building>::const_iterator i;
556 for (i = buildings_.begin (); i != buildings_.end (); i++)
558 if (i->end_ >= airplane)
559 return sky_ * i->height (airplane);
567 Skyline::max_height () const
570 s.set_minimum_height (0);
571 return sky_ * distance (s);
575 Skyline::set_minimum_height (Real h)
578 s.buildings_.front ().y_intercept_ = h * sky_;
583 Skyline::to_points (Axis horizon_axis) const
587 Real start = -infinity_f;
588 for (list<Building>::const_iterator i (buildings_.begin ());
589 i != buildings_.end (); i++)
591 out.push_back (Offset (start, sky_ * i->height (start)));
592 out.push_back (Offset (i->end_, sky_ * i->height (i->end_)));
596 if (horizon_axis == Y_AXIS)
597 for (vsize i = 0; i < out.size (); i++)
598 out[i] = out[i].swapped ();
604 Skyline::is_empty () const
606 Building b = buildings_.front ();
607 return b.end_ == infinity_f && b.y_intercept_ == -infinity_f;
614 empty_skyline (&buildings_);
617 /****************************************************************/
619 IMPLEMENT_SIMPLE_SMOBS (Skyline);
620 IMPLEMENT_TYPE_P (Skyline, "ly:skyline?");
621 IMPLEMENT_DEFAULT_EQUAL_P (Skyline);
624 Skyline::mark_smob (SCM)
626 ASSERT_LIVE_IS_ALLOWED ();
631 Skyline::print_smob (SCM s, SCM port, scm_print_state *)
633 Skyline *r = (Skyline *) SCM_CELL_WORD_1 (s);
636 scm_puts ("#<Skyline>", port);