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 skyline_trailing_part (list<Building> *sky, Real x)
165 if (approx_equal (x, sky->front ().iv_[RIGHT]))
168 assert (x < sky->front ().iv_[RIGHT]);
172 sky->front ().iv_[LEFT] = x;
173 sky->front ().height_[LEFT] = sky->front ().height (x);
178 Building::conceals_beginning (Building const &other) const
180 if (approx_equal (intersection (other), iv_[LEFT]) || approx_equal (height_[LEFT], other.height_[LEFT]))
181 return slope_ > other.slope_;
182 return height_[LEFT] > other.height_[LEFT];
186 Building::conceals (Building const &other) const
188 assert (iv_[LEFT] <= other.iv_[LEFT]);
189 return (iv_[RIGHT] >= other.iv_[RIGHT])
190 && approx_greater_equal (height (other.iv_[LEFT]), other.height_[LEFT])
191 && approx_greater_equal (height (other.iv_[RIGHT]), other.height_[RIGHT]);
195 Skyline::internal_merge_skyline (list<Building> *s1, list<Building> *s2,
196 list<Building> *const result)
198 while (!s1->empty ())
200 if (s2->front ().conceals_beginning (s1->front ()))
203 Building b = s1->front ();
204 while (!s2->empty () && b.conceals (s2->front ()))
208 result->push_front (b);
212 /* s2 either intersects with b or it ends after b */
213 Real end = infinity_f;
214 Real s2_start_height = s2->front ().height_[LEFT];
215 Real s2_end_height = s2->front ().height_[RIGHT];
216 Real s1_start_height = b.height (s2->front ().iv_[LEFT]);
217 Real s1_end_height = b.height (s2->front ().iv_[RIGHT]);
218 if (approx_greater_than (s2_start_height, s1_start_height))
219 end = s2->front ().iv_[LEFT];
220 else if (approx_greater_than (s2_end_height, s1_end_height))
221 end = b.intersection (s2->front ());
222 end = min (end, b.iv_[RIGHT]);
224 b.leading_part (end);
225 result->push_front (b);
227 skyline_trailing_part (s1, end);
228 skyline_trailing_part (s2, end);
234 empty_skyline (list<Building> *const ret)
236 ret->push_front (Building (-infinity_f, -infinity_f, -infinity_f, infinity_f));
240 single_skyline (Building const &b, list<Building> *const ret)
242 if (!isinf (b.iv_[RIGHT]))
243 ret->push_front (Building (b.iv_[RIGHT], -infinity_f,
244 -infinity_f, infinity_f));
245 if (b.iv_[RIGHT] > b.iv_[LEFT])
247 if (!isinf (b.iv_[LEFT]))
248 ret->push_front (Building (-infinity_f, -infinity_f,
249 -infinity_f, b.iv_[LEFT]));
253 Skyline::internal_build_skyline (list<Building> *buildings, list<Building> *const result)
255 vsize size = buildings->size ();
259 empty_skyline (result);
264 single_skyline (buildings->front (), result);
268 list<Building> right_half;
269 list<Building>::iterator i = buildings->begin ();
271 for (vsize s = 0; s < size/2; s++)
273 right_half.splice (right_half.end (), *buildings, i, buildings->end ());
275 list<Building> right;
277 internal_build_skyline (&right_half, &right);
278 internal_build_skyline (buildings, &left);
279 internal_merge_skyline (&right, &left, result);
285 empty_skyline (&buildings_);
288 Skyline::Skyline (Skyline const &src)
292 for (list<Building>::const_iterator i = src.buildings_.begin ();
293 i != src.buildings_.end (); i++)
295 buildings_.push_back (Building ((*i)));
299 Skyline::Skyline (Direction sky)
302 empty_skyline (&buildings_);
306 build skyline from a set of boxes.
308 Boxes should have fatness in the horizon_axis, otherwise they are ignored.
310 Skyline::Skyline (vector<Box> const &boxes, Axis horizon_axis, Direction sky)
312 list<Building> bldgs;
315 for (vsize i = 0; i < boxes.size (); i++)
317 Interval iv = boxes[i][horizon_axis];
318 Real height = sky * boxes[i][other_axis (horizon_axis)][sky];
319 if (!iv.is_empty () && !isinf (height) && !approx_equal (iv[LEFT], iv[RIGHT]))
322 bldgs.push_front (Building (iv[LEFT], height, height, iv[RIGHT]));
326 internal_build_skyline (&bldgs, &buildings_);
327 assert (is_legal_skyline ());
330 Skyline::Skyline (vector<Offset> const &points, Direction sky)
334 for (vsize i = 1; i < points.size (); i++)
336 buildings_.push_back (Building (points[i-1][X_AXIS],
337 sky * points[i-1][Y_AXIS],
338 sky * points[i][Y_AXIS],
343 assert (is_legal_skyline ());
347 Skyline::merge (Skyline const &other)
349 assert (sky_ == other.sky_);
351 list<Building> other_bld (other.buildings_);
352 list<Building> my_bld;
353 my_bld.splice (my_bld.begin (), buildings_);
354 internal_merge_skyline (&other_bld, &my_bld, &buildings_);
355 assert (is_legal_skyline ());
359 Skyline::insert (Box const &b, Axis a)
361 list<Building> other_bld;
362 list<Building> my_bld;
364 Real height = sky_ * b[other_axis (a)][sky_];
366 assert (!iv.is_empty ());
369 my_bld.splice (my_bld.begin (), buildings_);
370 single_skyline (Building (iv[LEFT], height, height, iv[RIGHT]), &other_bld);
371 internal_merge_skyline (&other_bld, &my_bld, &buildings_);
372 assert (is_legal_skyline ());
376 Skyline::raise (Real r)
378 list<Building>::iterator end = buildings_.end ();
379 for (list<Building>::iterator i = buildings_.begin (); i != end; i++)
381 i->height_[LEFT] += sky_ * r;
382 i->height_[RIGHT] += sky_ * r;
383 i->y_intercept_ += sky_ * r;
385 assert (is_legal_skyline ());
389 Skyline::distance (Skyline const &other) const
391 assert (sky_ == -other.sky_);
392 list<Building>::const_iterator i = buildings_.begin ();
393 list<Building>::const_iterator j = other.buildings_.begin ();
395 Real dist = -infinity_f;
396 while (i != buildings_.end () && j != other.buildings_.end ())
398 Interval iv = intersection (i->iv_, j->iv_);
399 dist = max (dist, max (i->height (iv[LEFT]) + j->height (iv[LEFT]),
400 i->height (iv[RIGHT]) + j->height (iv[RIGHT])));
401 if (i->iv_[RIGHT] <= j->iv_[RIGHT])
410 Skyline::height (Real airplane) const
412 assert (!isinf (airplane));
414 list<Building>::const_iterator i;
415 for (i = buildings_.begin (); i != buildings_.end (); i++)
417 if (i->iv_[RIGHT] >= airplane)
418 return sky_ * i->height (airplane);
426 Skyline::max_height () const
429 s.set_minimum_height (0);
430 return sky_ * distance (s);
434 Skyline::set_minimum_height (Real h)
437 s.buildings_.front ().height_[LEFT] = h * sky_;
438 s.buildings_.front ().height_[RIGHT] = h * sky_;
439 s.buildings_.front ().y_intercept_ = h * sky_;
445 Skyline::to_points () const
450 for (list<Building>::const_iterator i (buildings_.begin ());
451 i != buildings_.end (); i++)
454 out.push_back (Offset ((*i).iv_[LEFT], sky_ * (*i).height_[LEFT]));
457 out.push_back (Offset ((*i).iv_[RIGHT], sky_ * (*i).height_[RIGHT]));
463 /****************************************************************/
466 IMPLEMENT_SIMPLE_SMOBS (Skyline);
467 IMPLEMENT_TYPE_P (Skyline, "ly:skyline?");
468 IMPLEMENT_DEFAULT_EQUAL_P (Skyline);
471 Skyline::mark_smob (SCM)
477 Skyline::print_smob (SCM s, SCM port, scm_print_state *)
479 Skyline *r = (Skyline *) SCM_CELL_WORD_1 (s);
482 scm_puts ("#<Skyline>", port);