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 Real x = -infinity_f;
178 while (!s1->empty ())
180 if (s2->front ().conceals (s1->front (), x))
183 Building b = s1->front ();
184 Real end = first_intersection (b, s2, x);
188 result->push_front (b);
192 /* only include buildings wider than epsilon */
195 b.leading_part (end);
196 result->push_front (b);
199 if (end >= s1->front ().end_)
208 empty_skyline (list<Building> *const ret)
210 ret->push_front (Building (-infinity_f, -infinity_f, -infinity_f, infinity_f));
214 single_skyline (Building b, Real start, Real horizon_padding, list<Building> *const ret)
216 bool sloped_neighbours = horizon_padding > 0 && !isinf (start) && !isinf (b.end_);
218 ret->push_front (Building (b.end_ + horizon_padding, -infinity_f,
219 -infinity_f, infinity_f));
220 if (sloped_neighbours)
221 ret->push_front (b.sloped_neighbour (start, horizon_padding, RIGHT));
223 if (b.end_ > start + EPS)
226 if (sloped_neighbours)
227 ret->push_front (b.sloped_neighbour (start, horizon_padding, LEFT));
230 ret->push_front (Building (-infinity_f, -infinity_f,
231 -infinity_f, start - horizon_padding));
234 /* remove a non-overlapping set of boxes from BOXES and build a skyline
236 static list<Building>
237 non_overlapping_skyline (list<Box> *const boxes, Real horizon_padding, Axis horizon_axis, Direction sky)
239 list<Building> result;
240 Real last_end = -infinity_f;
241 list<Box>::iterator i = boxes->begin ();
242 while (i != boxes->end ())
244 Interval iv = (*i)[horizon_axis];
246 if (iv[LEFT] - horizon_padding < last_end)
252 if (iv[LEFT] - horizon_padding > last_end + EPS)
253 result.push_front (Building (last_end, -infinity_f, -infinity_f, iv[LEFT] - horizon_padding));
255 Building b (*i, horizon_padding, horizon_axis, sky);
256 bool sloped_neighbours = horizon_padding > 0 && !isinf (iv.length ());
257 if (sloped_neighbours)
258 result.push_front (b.sloped_neighbour (iv[LEFT] - horizon_padding, horizon_padding, LEFT));
259 result.push_front (b);
260 if (sloped_neighbours)
261 result.push_front (b.sloped_neighbour (iv[LEFT] - horizon_padding, horizon_padding, RIGHT));
263 list<Box>::iterator j = i++;
265 last_end = result.front ().end_;
267 if (last_end < infinity_f)
268 result.push_front (Building (last_end, -infinity_f, -infinity_f, infinity_f));
283 bool operator() (Box const &b1, Box const &b2)
285 return b1[a_][LEFT] < b2[a_][LEFT];
290 Skyline::internal_build_skyline (list<Box> *boxes, Real horizon_padding, Axis horizon_axis, Direction sky)
292 vsize size = boxes->size ();
296 list<Building> result;
297 empty_skyline (&result);
302 list<Building> result;
303 single_skyline (Building (boxes->front (), horizon_padding, horizon_axis, sky),
304 boxes->front ()[horizon_axis][LEFT], horizon_axis, &result);
308 deque<list<Building> > partials;
309 boxes->sort (LessThanBox (horizon_axis));
310 while (!boxes->empty ())
311 partials.push_back (non_overlapping_skyline (boxes, horizon_padding, horizon_axis, sky));
313 /* we'd like to say while (partials->size () > 1) but that's O (n).
314 Instead, we exit in the middle of the loop */
315 while (!partials.empty ())
317 list<Building> merged;
318 list<Building> one = partials.front ();
319 partials.pop_front ();
320 if (partials.empty ())
323 list<Building> two = partials.front ();
324 partials.pop_front ();
325 internal_merge_skyline (&one, &two, &merged);
326 partials.push_back (merged);
329 return list<Building> ();
335 empty_skyline (&buildings_);
338 Skyline::Skyline (Skyline const &src)
342 /* doesn't a list's copy constructor do this? -- jneem */
343 for (list<Building>::const_iterator i = src.buildings_.begin ();
344 i != src.buildings_.end (); i++)
346 buildings_.push_back (Building ((*i)));
350 Skyline::Skyline (Direction sky)
353 empty_skyline (&buildings_);
357 build skyline from a set of boxes. If horizon_padding > 0, expand all the boxes
358 by that amount and add 45-degree sloped boxes to the edges of each box (of
359 width horizon_padding). That is, the total amount of horizontal expansion is
360 horizon_padding*4, half of which is sloped and half of which is flat.
362 Boxes should have fatness in the horizon_axis (after they are expanded by
363 horizon_padding), otherwise they are ignored.
365 Skyline::Skyline (vector<Box> const &boxes, Real horizon_padding, Axis horizon_axis, Direction sky)
367 list<Box> filtered_boxes;
370 Axis vert_axis = other_axis (horizon_axis);
371 for (vsize i = 0; i < boxes.size (); i++)
373 Interval iv = boxes[i][horizon_axis];
374 iv.widen (horizon_padding);
375 if (iv.length () > EPS && !boxes[i][vert_axis].is_empty ())
376 filtered_boxes.push_front (boxes[i]);
379 buildings_ = internal_build_skyline (&filtered_boxes, horizon_padding, horizon_axis, sky);
382 Skyline::Skyline (Box const &b, Real horizon_padding, Axis horizon_axis, Direction sky)
385 Building front (b, horizon_padding, horizon_axis, sky);
386 single_skyline (front, b[horizon_axis][LEFT], horizon_padding, &buildings_);
390 Skyline::merge (Skyline const &other)
392 assert (sky_ == other.sky_);
394 list<Building> other_bld (other.buildings_);
395 list<Building> my_bld;
396 my_bld.splice (my_bld.begin (), buildings_);
397 internal_merge_skyline (&other_bld, &my_bld, &buildings_);
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, horizon_padding, a, sky_), b[a][LEFT], horizon_padding, &other_bld);
408 internal_merge_skyline (&other_bld, &my_bld, &buildings_);
412 Skyline::raise (Real r)
414 list<Building>::iterator end = buildings_.end ();
415 for (list<Building>::iterator i = buildings_.begin (); i != end; i++)
416 i->y_intercept_ += sky_ * r;
420 Skyline::shift (Real s)
422 list<Building>::iterator end = buildings_.end ();
423 for (list<Building>::iterator i = buildings_.begin (); i != end; i++)
426 i->y_intercept_ -= s * i->slope_;
431 Skyline::distance (Skyline const &other) const
433 assert (sky_ == -other.sky_);
434 list<Building>::const_iterator i = buildings_.begin ();
435 list<Building>::const_iterator j = other.buildings_.begin ();
437 Real dist = -infinity_f;
438 Real start = -infinity_f;
439 while (i != buildings_.end () && j != other.buildings_.end ())
441 Real end = min (i->end_, j->end_);
442 Real start_dist = i->height (start) + j->height (start);
443 Real end_dist = i->height (end) + j->height (end);
444 dist = max (dist, max (start_dist, end_dist));
445 if (i->end_ <= j->end_)
455 Skyline::height (Real airplane) const
457 assert (!isinf (airplane));
459 list<Building>::const_iterator i;
460 for (i = buildings_.begin (); i != buildings_.end (); i++)
462 if (i->end_ >= airplane)
463 return sky_ * i->height (airplane);
471 Skyline::max_height () const
474 s.set_minimum_height (0);
475 return sky_ * distance (s);
479 Skyline::set_minimum_height (Real h)
482 s.buildings_.front ().y_intercept_ = h * sky_;
488 Skyline::to_points (Axis a) const
492 Real start = -infinity_f;
493 for (list<Building>::const_iterator i (buildings_.begin ());
494 i != buildings_.end (); i++)
496 out.push_back (Offset (start, sky_ * i->height (start)));
497 out.push_back (Offset (i->end_, sky_ * i->height (i->end_)));
502 for (vsize i = 0; i < out.size (); i++)
503 out[i] = Offset (out[i][Y_AXIS], out[i][X_AXIS]);
509 Skyline::is_empty () const
511 return buildings_.empty ();
514 Skyline_pair::Skyline_pair ()
515 : skylines_ (Skyline (DOWN), Skyline (UP))
519 Skyline_pair::Skyline_pair (vector<Box> const &boxes, Real padding, Axis a)
520 : skylines_ (Skyline (boxes, padding, a, DOWN), Skyline (boxes, padding, a, UP))
524 Skyline_pair::Skyline_pair (Box const &b, Real padding, Axis a)
525 : skylines_ (Skyline (b, padding, a, DOWN), Skyline (b, padding, a, UP))
530 Skyline_pair::raise (Real r)
532 skylines_[UP].raise (r);
533 skylines_[DOWN].raise (r);
537 Skyline_pair::shift (Real r)
539 skylines_[UP].shift (r);
540 skylines_[DOWN].shift (r);
544 Skyline_pair::insert (Box const &b, Real padding, Axis a)
546 skylines_[UP].insert (b, padding, a);
547 skylines_[DOWN].insert (b, padding, a);
551 Skyline_pair::merge (Skyline_pair const &other)
553 skylines_[UP].merge (other[UP]);
554 skylines_[DOWN].merge (other[DOWN]);
558 Skyline_pair::is_empty () const
560 return skylines_[UP].is_empty ()
561 && skylines_[DOWN].is_empty ();
565 Skyline_pair::operator [] (Direction d)
571 Skyline_pair::operator [] (Direction d) const
576 /****************************************************************/
579 IMPLEMENT_SIMPLE_SMOBS (Skyline);
580 IMPLEMENT_TYPE_P (Skyline, "ly:skyline?");
581 IMPLEMENT_DEFAULT_EQUAL_P (Skyline);
583 IMPLEMENT_SIMPLE_SMOBS (Skyline_pair);
584 IMPLEMENT_TYPE_P (Skyline_pair, "ly:skyline-pair?");
585 IMPLEMENT_DEFAULT_EQUAL_P (Skyline_pair);
588 Skyline::mark_smob (SCM)
590 ASSERT_LIVE_IS_ALLOWED ();
595 Skyline::print_smob (SCM s, SCM port, scm_print_state *)
597 Skyline *r = (Skyline *) SCM_CELL_WORD_1 (s);
600 scm_puts ("#<Skyline>", port);
606 Skyline_pair::mark_smob (SCM)
612 Skyline_pair::print_smob (SCM s, SCM port, scm_print_state *)
614 Skyline_pair *r = (Skyline_pair *) SCM_CELL_WORD_1 (s);
617 scm_puts ("#<Skyline-pair>", port);