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 equal (Real x, Real y)
49 return abs (x - y) < EPS || (isinf (x) && isinf (y) && ((x > 0) == (y > 0)));
53 Skyline::print () const
55 for (list<Building>::const_iterator i = buildings_.begin ();
56 i != buildings_.end (); i++)
63 Skyline::is_legal_skyline () const
65 list<Building>::const_iterator i;
66 Real last_x = -infinity_f;
67 Real last_h = -infinity_f;
68 for (i = buildings_.begin (); i != buildings_.end (); i++)
70 if (i->iv_[LEFT] != last_x)
72 if (i != buildings_.begin () && !equal (i->start_height_, last_h))
74 last_x = i->iv_[RIGHT];
75 last_h = i->end_height_;
77 return last_x == infinity_f;
80 Building::Building (Real start, Real start_height, Real end_height,
81 Real end, Real max_slope)
84 start_height_ = start_height;
85 end_height_ = end_height;
88 assert (isinf (start_height) || start_height == end_height);
90 assert (isinf (end_height) || start_height == end_height);
92 precompute (max_slope);
96 Building::precompute (Real max_slope)
98 slope_ = (end_height_ - start_height_) / (iv_.length());
99 if (start_height_ == end_height_)
101 if (isinf (slope_) || isnan (slope_))
102 slope_ = max_slope * (start_height_ < end_height_ ? 1 : -1);
106 this check is sensitive to roundoff errors when converting to/from
109 assert (abs (slope_) <= max_slope + EPS);
112 if (isinf (iv_[START]))
114 if (isinf (iv_[STOP]))
115 zero_height_ = start_height_;
117 zero_height_ = end_height_ - slope_ * iv_[STOP];
120 zero_height_ = start_height_ - slope_ * iv_[START];
124 Building::height (Real x) const
127 return (x > 0) ? end_height_ : start_height_;
128 return slope_*x + zero_height_;
132 Building::print () const
134 printf ("X[%f,%f] -> Y[%f,%f]\n",
135 iv_[LEFT], iv_[RIGHT],
136 start_height_, end_height_);
140 Building::intersection (Building const &other) const
142 return (zero_height_ - other.zero_height_) / (other.slope_ - slope_);
146 Building::leading_part (Real chop, Real h)
148 assert (chop > iv_[LEFT] && chop <= iv_[RIGHT] && !equal (chop, iv_[LEFT]));
149 assert (equal (h, height (chop)));
155 skyline_trailing_part (list<Building> *sky, Real x)
157 if (equal (x, sky->front ().iv_[RIGHT]))
160 assert (x < sky->front ().iv_[RIGHT]);
164 sky->front ().iv_[LEFT] = x;
165 sky->front ().start_height_ = sky->front ().height (x);
170 Building::obstructs (Building const &other) const
172 if (equal (intersection (other), iv_[LEFT]) || equal (start_height_, other.start_height_))
173 return slope_ > other.slope_ || (slope_ == other.slope_ && zero_height_ > other.zero_height_);
174 return start_height_ > other.start_height_;
178 Skyline::internal_merge_skyline (list<Building> *s1, list<Building> *s2,
179 list<Building> *const result)
181 while (!s1->empty ())
183 if (s2->front ().obstructs (s1->front ()))
186 Building b = s1->front ();
187 while (s2->front ().iv_[RIGHT] < b.iv_[RIGHT]
188 && s2->front ().end_height_ <= b.height (s2->front ().iv_[RIGHT]) + EPS)
191 /* the front of s2 either intersects with b or it ends after b */
192 Real end = infinity_f;
193 Real s2_end_height = s2->front ().end_height_;
194 Real s1_end_height = b.height (s2->front ().iv_[RIGHT]);
195 if (s2_end_height > s1_end_height + EPS)
196 end = b.intersection (s2->front ());
197 end = min (end, b.iv_[RIGHT]);
198 Real height = b.height (end);
200 b.leading_part (end, height);
201 result->push_front (b);
203 skyline_trailing_part (s1, end);
205 s1->front ().start_height_ = height;
206 skyline_trailing_part (s2, end);
212 empty_skyline (list<Building> *const ret)
214 ret->push_front (Building (-infinity_f, -infinity_f, -infinity_f, infinity_f, 0));
218 single_skyline (Building const &b, list<Building> *const ret, Real max_slope)
220 if (!isinf (b.iv_[RIGHT]))
221 ret->push_front (Building (b.iv_[RIGHT], b.end_height_,
222 -infinity_f, infinity_f, max_slope));
224 if (!isinf (b.iv_[LEFT]))
225 ret->push_front (Building (-infinity_f, -infinity_f,
226 b.start_height_, b.iv_[LEFT], max_slope));
230 Skyline::internal_build_skyline (list<Building> *buildings, list<Building> *const result)
232 vsize size = buildings->size ();
236 empty_skyline (result);
241 single_skyline (buildings->front (), result, max_slope_);
245 list<Building> right_half;
246 list<Building>::iterator i = buildings->begin ();
248 for (vsize s = 0; s < size/2; s++)
250 right_half.splice (right_half.end (), *buildings, i, buildings->end ());
252 list<Building> right;
254 internal_build_skyline (&right_half, &right);
255 internal_build_skyline (buildings, &left);
256 internal_merge_skyline (&right, &left, result);
263 empty_skyline (&buildings_);
268 Skyline::Skyline (Skyline const &src)
270 max_slope_ = src.max_slope_;
273 for (list<Building>::const_iterator i = src.buildings_.begin ();
274 i != src.buildings_.end (); i++)
276 buildings_.push_back (Building ((*i)));
280 Skyline::Skyline (Direction sky)
284 empty_skyline (&buildings_);
288 build skyline from a set of boxes.
290 Boxes should have fatness in the horizon_axis, otherwise they are ignored.
292 Skyline::Skyline (vector<Box> const &boxes, Axis horizon_axis, Direction sky)
294 list<Building> bldgs;
298 for (vsize i = 0; i < boxes.size (); i++)
300 Interval iv = boxes[i][horizon_axis];
301 Real height = sky * boxes[i][other_axis (horizon_axis)][sky];
302 if (!iv.is_empty () && !isinf (height) && !equal (iv[LEFT], iv[RIGHT]))
303 bldgs.push_front (Building (iv[LEFT], height, height, iv[RIGHT],
307 internal_build_skyline (&bldgs, &buildings_);
308 assert (is_legal_skyline ());
311 Skyline::Skyline (vector<Offset> const &points, Real max_slope, Direction sky)
314 max_slope_ = max_slope;
316 for (vsize i = 1; i < points.size (); i++)
318 buildings_.push_back (Building (points[i-1][X_AXIS], sky * points[i-1][Y_AXIS],
319 sky * points[i][Y_AXIS],
326 assert (is_legal_skyline ());
330 Skyline::merge (Skyline const &other)
332 assert (sky_ == other.sky_);
334 list<Building> other_bld (other.buildings_);
335 list<Building> my_bld;
336 my_bld.splice (my_bld.begin (), buildings_);
337 internal_merge_skyline (&other_bld, &my_bld, &buildings_);
338 assert (is_legal_skyline ());
342 Skyline::insert (Box const &b, Axis a)
344 list<Building> other_bld;
345 list<Building> my_bld;
347 Real height = sky_ * b[other_axis (a)][sky_];
349 my_bld.splice (my_bld.begin (), buildings_);
350 single_skyline (Building (iv[LEFT], height, height, iv[RIGHT], max_slope_), &other_bld, max_slope_);
351 internal_merge_skyline (&other_bld, &my_bld, &buildings_);
352 assert (is_legal_skyline ());
356 Skyline::raise (Real r)
358 list<Building>::iterator end = buildings_.end ();
359 for (list<Building>::iterator i = buildings_.begin (); i != end; i++)
361 i->start_height_ += sky_ * r;
362 i->end_height_ += sky_ * r;
363 i->zero_height_ += sky_ * r;
365 assert (is_legal_skyline ());
369 Skyline::distance (Skyline const &other) const
371 assert (sky_ == -other.sky_);
372 list<Building>::const_iterator i = buildings_.begin ();
373 list<Building>::const_iterator j = other.buildings_.begin ();
375 Real dist = -infinity_f;
376 while (i != buildings_.end () && j != other.buildings_.end ())
378 Interval iv = intersection (i->iv_, j->iv_);
379 dist = max (dist, max (i->height (iv[LEFT]) + j->height (iv[LEFT]),
380 i->height (iv[RIGHT]) + j->height (iv[RIGHT])));
381 if (i->iv_[RIGHT] <= j->iv_[RIGHT])
390 Skyline::height (Real airplane) const
392 assert (!isinf (airplane));
394 list<Building>::const_iterator i;
395 for (i = buildings_.begin (); i != buildings_.end (); i++)
397 if (i->iv_[RIGHT] >= airplane)
398 return sky_ * i->height (airplane);
406 Skyline::max_height () const
409 s.set_minimum_height (0);
410 return sky_ * distance (s);
414 Skyline::set_minimum_height (Real h)
417 s.buildings_.front ().start_height_ = h * sky_;
418 s.buildings_.front ().end_height_ = h * sky_;
419 s.buildings_.front ().zero_height_ = h * sky_;
425 Skyline::to_points () const
430 for (list<Building>::const_iterator i (buildings_.begin ());
431 i != buildings_.end (); i++)
434 out.push_back (Offset ((*i).iv_[LEFT], sky_ * (*i).start_height_));
437 out.push_back (Offset ((*i).iv_[RIGHT], sky_ * (*i).end_height_));
443 /****************************************************************/
446 IMPLEMENT_SIMPLE_SMOBS (Skyline);
447 IMPLEMENT_TYPE_P (Skyline, "ly:skyline?");
448 IMPLEMENT_DEFAULT_EQUAL_P (Skyline);
451 Skyline::mark_smob (SCM)
457 Skyline::print_smob (SCM s, SCM port, scm_print_state *)
459 Skyline *r = (Skyline *) SCM_CELL_WORD_1 (s);
462 scm_puts ("#<Skyline>", port);