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->height_[LEFT], last_h))
74 last_x = i->iv_[RIGHT];
75 last_h = i->height_[RIGHT];
77 return last_x == infinity_f;
80 Building::Building (Real start, Real start_height, Real end_height,
81 Real end, Real max_slope)
84 height_[LEFT] = start_height;
85 height_[RIGHT] = 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_ = (height_[RIGHT] - height_[LEFT]) / (iv_.length());
99 if (height_[LEFT] == height_[RIGHT])
101 if (isinf (slope_) || isnan (slope_))
102 slope_ = max_slope * (height_[LEFT] < height_[RIGHT] ? 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_ = height_[LEFT];
117 zero_height_ = height_[RIGHT] - slope_ * iv_[STOP];
120 zero_height_ = height_[LEFT] - slope_ * iv_[START];
124 Building::height (Real x) const
127 return (x > 0) ? height_[RIGHT] : height_[LEFT];
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 height_[LEFT], height_[RIGHT]);
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 ().height_[LEFT] = sky->front ().height (x);
170 Building::obstructs (Building const &other) const
172 if (equal (intersection (other), iv_[LEFT]) || equal (height_[LEFT], other.height_[LEFT]))
173 return slope_ > other.slope_ || (slope_ == other.slope_ && zero_height_ > other.zero_height_);
174 return height_[LEFT] > other.height_[LEFT];
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 ().height_[RIGHT] <= 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 ().height_[RIGHT];
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 ().height_[LEFT] = 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.height_[RIGHT],
222 -infinity_f, infinity_f, max_slope));
223 if (b.iv_[RIGHT] > b.iv_[LEFT])
225 if (!isinf (b.iv_[LEFT]))
226 ret->push_front (Building (-infinity_f, -infinity_f,
227 b.height_[LEFT], b.iv_[LEFT], max_slope));
231 Skyline::internal_build_skyline (list<Building> *buildings, Real max_slope, list<Building> *const result)
233 vsize size = buildings->size ();
237 empty_skyline (result);
242 single_skyline (buildings->front (), result, max_slope);
246 list<Building> right_half;
247 list<Building>::iterator i = buildings->begin ();
249 for (vsize s = 0; s < size/2; s++)
251 right_half.splice (right_half.end (), *buildings, i, buildings->end ());
253 list<Building> right;
255 internal_build_skyline (&right_half, max_slope, &right);
256 internal_build_skyline (buildings, max_slope, &left);
257 internal_merge_skyline (&right, &left, result);
263 empty_skyline (&buildings_);
266 Skyline::Skyline (Skyline const &src)
270 for (list<Building>::const_iterator i = src.buildings_.begin ();
271 i != src.buildings_.end (); i++)
273 buildings_.push_back (Building ((*i)));
277 Skyline::Skyline (Direction sky)
280 empty_skyline (&buildings_);
284 build skyline from a set of boxes.
286 Boxes should have fatness in the horizon_axis, otherwise they are ignored.
288 Skyline::Skyline (vector<Box> const &boxes, Real max_slope, Axis horizon_axis, Direction sky)
290 list<Building> bldgs;
293 for (vsize i = 0; i < boxes.size (); i++)
295 Interval iv = boxes[i][horizon_axis];
296 Real height = sky * boxes[i][other_axis (horizon_axis)][sky];
297 if (!iv.is_empty () && !isinf (height) && !equal (iv[LEFT], iv[RIGHT]))
298 bldgs.push_front (Building (iv[LEFT], height, height, iv[RIGHT],
302 internal_build_skyline (&bldgs, max_slope, &buildings_);
303 assert (is_legal_skyline ());
306 Skyline::Skyline (vector<Offset> const &points, Real max_slope, Direction sky)
310 for (vsize i = 1; i < points.size (); i++)
312 buildings_.push_back (Building (points[i-1][X_AXIS],
313 sky * points[i-1][Y_AXIS],
314 sky * points[i][Y_AXIS],
320 assert (is_legal_skyline ());
324 Skyline::merge (Skyline const &other)
326 assert (sky_ == other.sky_);
328 list<Building> other_bld (other.buildings_);
329 list<Building> my_bld;
330 my_bld.splice (my_bld.begin (), buildings_);
331 internal_merge_skyline (&other_bld, &my_bld, &buildings_);
332 assert (is_legal_skyline ());
336 Skyline::insert (Box const &b, Real max_slope, Axis a)
338 list<Building> other_bld;
339 list<Building> my_bld;
341 Real height = sky_ * b[other_axis (a)][sky_];
343 assert (!iv.is_empty ());
345 my_bld.splice (my_bld.begin (), buildings_);
346 single_skyline (Building (iv[LEFT], height, height, iv[RIGHT], max_slope), &other_bld, max_slope);
347 internal_merge_skyline (&other_bld, &my_bld, &buildings_);
348 assert (is_legal_skyline ());
352 Skyline::raise (Real r)
354 list<Building>::iterator end = buildings_.end ();
355 for (list<Building>::iterator i = buildings_.begin (); i != end; i++)
357 i->height_[LEFT] += sky_ * r;
358 i->height_[RIGHT] += sky_ * r;
359 i->zero_height_ += sky_ * r;
361 assert (is_legal_skyline ());
365 Skyline::distance (Skyline const &other) const
367 assert (sky_ == -other.sky_);
368 list<Building>::const_iterator i = buildings_.begin ();
369 list<Building>::const_iterator j = other.buildings_.begin ();
371 Real dist = -infinity_f;
372 while (i != buildings_.end () && j != other.buildings_.end ())
374 Interval iv = intersection (i->iv_, j->iv_);
375 dist = max (dist, max (i->height (iv[LEFT]) + j->height (iv[LEFT]),
376 i->height (iv[RIGHT]) + j->height (iv[RIGHT])));
377 if (i->iv_[RIGHT] <= j->iv_[RIGHT])
386 Skyline::height (Real airplane) const
388 assert (!isinf (airplane));
390 list<Building>::const_iterator i;
391 for (i = buildings_.begin (); i != buildings_.end (); i++)
393 if (i->iv_[RIGHT] >= airplane)
394 return sky_ * i->height (airplane);
402 Skyline::max_height () const
405 s.set_minimum_height (0);
406 return sky_ * distance (s);
410 Skyline::set_minimum_height (Real h)
413 s.buildings_.front ().height_[LEFT] = h * sky_;
414 s.buildings_.front ().height_[RIGHT] = h * sky_;
415 s.buildings_.front ().zero_height_ = h * sky_;
421 Skyline::to_points () const
426 for (list<Building>::const_iterator i (buildings_.begin ());
427 i != buildings_.end (); i++)
430 out.push_back (Offset ((*i).iv_[LEFT], sky_ * (*i).height_[LEFT]));
433 out.push_back (Offset ((*i).iv_[RIGHT], sky_ * (*i).height_[RIGHT]));
439 /****************************************************************/
442 IMPLEMENT_SIMPLE_SMOBS (Skyline);
443 IMPLEMENT_TYPE_P (Skyline, "ly:skyline?");
444 IMPLEMENT_DEFAULT_EQUAL_P (Skyline);
447 Skyline::mark_smob (SCM)
453 Skyline::print_smob (SCM s, SCM port, scm_print_state *)
455 Skyline *r = (Skyline *) SCM_CELL_WORD_1 (s);
458 scm_puts ("#<Skyline>", port);