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.
47 approx_equal (Real x, Real y)
49 return abs (x - y) < EPS || (isinf (x) && isinf (y) && ((x > 0) == (y > 0)));
53 approx_greater_than (Real x, Real y)
59 approx_less_than (Real x, Real y)
65 approx_less_equal (Real x, Real y)
71 approx_greater_equal (Real x, Real y)
77 Skyline::print () const
79 for (list<Building>::const_iterator i = buildings_.begin ();
80 i != buildings_.end (); i++)
87 Skyline::is_legal_skyline () const
89 list<Building>::const_iterator i;
90 Real last_x = -infinity_f;
91 for (i = buildings_.begin (); i != buildings_.end (); i++)
93 if (i->iv_[LEFT] != last_x)
95 last_x = i->iv_[RIGHT];
96 if (isinf (i->iv_.length ()) && i->height_[LEFT] != i->height_[RIGHT])
99 return last_x == infinity_f;
102 Building::Building (Real start, Real start_height, Real end_height, Real end)
105 height_[LEFT] = start_height;
106 height_[RIGHT] = end_height;
108 if (isinf (start) || isinf (end))
109 assert (start_height == end_height);
115 Building::precompute ()
117 slope_ = (height_[RIGHT] - height_[LEFT]) / (iv_.length());
118 if (height_[LEFT] == height_[RIGHT]) /* in case they're both infinity */
121 assert (!isinf (slope_) && !isnan (slope_));
123 if (isinf (iv_[START]))
125 assert (slope_ == 0);
126 y_intercept_ = height_[LEFT];
129 y_intercept_ = height_[LEFT] - slope_ * iv_[START];
133 Building::height (Real x) const
136 return (x > 0) ? height_[RIGHT] : height_[LEFT];
137 return slope_*x + y_intercept_;
141 Building::print () const
143 printf ("X[%f,%f] -> Y[%f,%f]\n",
144 iv_[LEFT], iv_[RIGHT],
145 height_[LEFT], height_[RIGHT]);
149 Building::intersection (Building const &other) const
151 return (y_intercept_ - other.y_intercept_) / (other.slope_ - slope_);
155 Building::leading_part (Real chop)
157 assert (chop > iv_[LEFT] && chop <= iv_[RIGHT] && !approx_equal (chop, iv_[LEFT]));
159 height_[RIGHT] = height (chop);
163 Building::sloped_neighbour (Real horizon_padding, Direction d) const
166 Real right = iv_[d] + d * horizon_padding;
167 Real left_height = height_[d];
168 Real right_height = height_[d] - horizon_padding;
172 swap (left_height, right_height);
174 return Building (left, left_height, right_height, right);
178 skyline_trailing_part (list<Building> *sky, Real x)
180 if (approx_equal (x, sky->front ().iv_[RIGHT]))
183 assert (x < sky->front ().iv_[RIGHT]);
187 sky->front ().iv_[LEFT] = x;
188 sky->front ().height_[LEFT] = sky->front ().height (x);
193 Building::conceals_beginning (Building const &other) const
195 if (approx_equal (intersection (other), iv_[LEFT]) || approx_equal (height_[LEFT], other.height_[LEFT]))
196 return slope_ > other.slope_;
197 return height_[LEFT] > other.height_[LEFT];
201 Building::conceals (Building const &other) const
203 assert (iv_[LEFT] <= other.iv_[LEFT]);
204 return (iv_[RIGHT] >= other.iv_[RIGHT])
205 && approx_greater_equal (height (other.iv_[LEFT]), other.height_[LEFT])
206 && approx_greater_equal (height (other.iv_[RIGHT]), other.height_[RIGHT]);
210 Skyline::internal_merge_skyline (list<Building> *s1, list<Building> *s2,
211 list<Building> *const result)
213 while (!s1->empty ())
215 if (s2->front ().conceals_beginning (s1->front ()))
218 Building b = s1->front ();
219 while (!s2->empty () && b.conceals (s2->front ()))
223 result->push_front (b);
227 /* s2 either intersects with b or it ends after b */
228 Real end = infinity_f;
229 Real s2_start_height = s2->front ().height_[LEFT];
230 Real s2_end_height = s2->front ().height_[RIGHT];
231 Real s1_start_height = b.height (s2->front ().iv_[LEFT]);
232 Real s1_end_height = b.height (s2->front ().iv_[RIGHT]);
233 if (approx_greater_than (s2_start_height, s1_start_height))
234 end = s2->front ().iv_[LEFT];
235 else if (approx_greater_than (s2_end_height, s1_end_height))
236 end = b.intersection (s2->front ());
237 end = min (end, b.iv_[RIGHT]);
239 b.leading_part (end);
240 result->push_front (b);
242 skyline_trailing_part (s1, end);
243 skyline_trailing_part (s2, end);
249 empty_skyline (list<Building> *const ret)
251 ret->push_front (Building (-infinity_f, -infinity_f, -infinity_f, infinity_f));
255 single_skyline (Building b, Real horizon_padding, list<Building> *const ret)
257 b.iv_.widen (horizon_padding);
259 if (!isinf (b.iv_[RIGHT]))
260 ret->push_front (Building (b.iv_[RIGHT], -infinity_f,
261 -infinity_f, infinity_f));
262 if (horizon_padding > 0 && !isinf (b.iv_.length ()))
263 ret->push_front (b.sloped_neighbour (horizon_padding, RIGHT));
265 if (b.iv_[RIGHT] > b.iv_[LEFT])
268 if (horizon_padding > 0 && !isinf (b.iv_.length ()))
269 ret->push_front (b.sloped_neighbour (horizon_padding, LEFT));
270 if (!isinf (b.iv_[LEFT]))
271 ret->push_front (Building (-infinity_f, -infinity_f,
272 -infinity_f, b.iv_[LEFT]));
276 Skyline::internal_build_skyline (list<Building> *buildings, list<Building> *const result)
278 vsize size = buildings->size ();
282 empty_skyline (result);
287 single_skyline (buildings->front (), 0, result);
291 list<Building> right_half;
292 list<Building>::iterator i = buildings->begin ();
294 for (vsize s = 0; s < size/2; s++)
296 right_half.splice (right_half.end (), *buildings, i, buildings->end ());
298 list<Building> right;
300 internal_build_skyline (&right_half, &right);
301 internal_build_skyline (buildings, &left);
302 internal_merge_skyline (&right, &left, result);
308 empty_skyline (&buildings_);
311 Skyline::Skyline (Skyline const &src)
315 for (list<Building>::const_iterator i = src.buildings_.begin ();
316 i != src.buildings_.end (); i++)
318 buildings_.push_back (Building ((*i)));
322 Skyline::Skyline (Direction sky)
325 empty_skyline (&buildings_);
329 build skyline from a set of boxes. If horizon_padding > 0, expand all the boxes
330 by that amount and add 45-degree sloped boxes to the edges of each box (of
331 width horizon_padding). That is, the total amount of horizontal expansion is
332 horizon_padding*4, half of which is sloped and half of which is flat.
334 Boxes should have fatness in the horizon_axis (after they are expanded by
335 horizon_padding), otherwise they are ignored.
337 Skyline::Skyline (vector<Box> const &boxes, Real horizon_padding, Axis horizon_axis, Direction sky)
339 list<Building> bldgs;
342 for (vsize i = 0; i < boxes.size (); i++)
344 Interval iv = boxes[i][horizon_axis];
345 Real height = sky * boxes[i][other_axis (horizon_axis)][sky];
347 iv.widen (horizon_padding);
348 if (!iv.is_empty () && !isinf (height) && !approx_equal (iv[LEFT], iv[RIGHT]))
351 Building front = Building (iv[LEFT], height, height, iv[RIGHT]);
352 bldgs.push_front (front);
353 if (horizon_padding > 0 && !isinf (front.iv_.length ()))
355 bldgs.push_front (front.sloped_neighbour (horizon_padding, LEFT));
356 bldgs.push_front (front.sloped_neighbour (horizon_padding, RIGHT));
361 internal_build_skyline (&bldgs, &buildings_);
362 assert (is_legal_skyline ());
366 Skyline::merge (Skyline const &other)
368 assert (sky_ == other.sky_);
370 list<Building> other_bld (other.buildings_);
371 list<Building> my_bld;
372 my_bld.splice (my_bld.begin (), buildings_);
373 internal_merge_skyline (&other_bld, &my_bld, &buildings_);
374 assert (is_legal_skyline ());
378 Skyline::insert (Box const &b, Real horizon_padding, Axis a)
380 list<Building> other_bld;
381 list<Building> my_bld;
383 Real height = sky_ * b[other_axis (a)][sky_];
385 assert (!iv.is_empty ());
388 my_bld.splice (my_bld.begin (), buildings_);
389 single_skyline (Building (iv[LEFT], height, height, iv[RIGHT]), horizon_padding, &other_bld);
390 internal_merge_skyline (&other_bld, &my_bld, &buildings_);
391 assert (is_legal_skyline ());
395 Skyline::raise (Real r)
397 list<Building>::iterator end = buildings_.end ();
398 for (list<Building>::iterator i = buildings_.begin (); i != end; i++)
400 i->height_[LEFT] += sky_ * r;
401 i->height_[RIGHT] += sky_ * r;
402 i->y_intercept_ += sky_ * r;
404 assert (is_legal_skyline ());
408 Skyline::distance (Skyline const &other) const
410 assert (sky_ == -other.sky_);
411 list<Building>::const_iterator i = buildings_.begin ();
412 list<Building>::const_iterator j = other.buildings_.begin ();
414 Real dist = -infinity_f;
415 while (i != buildings_.end () && j != other.buildings_.end ())
417 Interval iv = intersection (i->iv_, j->iv_);
418 dist = max (dist, max (i->height (iv[LEFT]) + j->height (iv[LEFT]),
419 i->height (iv[RIGHT]) + j->height (iv[RIGHT])));
420 if (i->iv_[RIGHT] <= j->iv_[RIGHT])
429 Skyline::height (Real airplane) const
431 assert (!isinf (airplane));
433 list<Building>::const_iterator i;
434 for (i = buildings_.begin (); i != buildings_.end (); i++)
436 if (i->iv_[RIGHT] >= airplane)
437 return sky_ * i->height (airplane);
445 Skyline::max_height () const
448 s.set_minimum_height (0);
449 return sky_ * distance (s);
453 Skyline::set_minimum_height (Real h)
456 s.buildings_.front ().height_[LEFT] = h * sky_;
457 s.buildings_.front ().height_[RIGHT] = h * sky_;
458 s.buildings_.front ().y_intercept_ = h * sky_;
464 Skyline::to_points () const
468 for (list<Building>::const_iterator i (buildings_.begin ());
469 i != buildings_.end (); i++)
471 if (!isinf (i->iv_[LEFT]) && !isinf (i->height_[LEFT]))
472 out.push_back (Offset (i->iv_[LEFT], sky_ * i->height_[LEFT]));
473 if (!isinf (i->iv_[RIGHT]) && !isinf (i->height_[RIGHT]))
474 out.push_back (Offset (i->iv_[RIGHT], sky_ * i->height_[RIGHT]));
479 /****************************************************************/
482 IMPLEMENT_SIMPLE_SMOBS (Skyline);
483 IMPLEMENT_TYPE_P (Skyline, "ly:skyline?");
484 IMPLEMENT_DEFAULT_EQUAL_P (Skyline);
487 Skyline::mark_smob (SCM)
493 Skyline::print_smob (SCM s, SCM port, scm_print_state *)
495 Skyline *r = (Skyline *) SCM_CELL_WORD_1 (s);
498 scm_puts ("#<Skyline>", port);