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 "line-interface.hh"
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::is_legal_skyline () const
55 list<Building>::const_iterator i;
56 Real last_x = -infinity_f;
57 Real last_h = -infinity_f;
58 for (i = buildings_.begin (); i != buildings_.end (); i++)
60 if (i->iv_[LEFT] != last_x)
62 if (i != buildings_.begin () && !equal (i->start_height_, last_h))
64 last_x = i->iv_[RIGHT];
65 last_h = i->end_height_;
67 return last_x == infinity_f;
70 Building::Building (Real start, Real start_height, Real end_height, Real end, Real max_slope)
73 start_height_ = start_height;
74 end_height_ = end_height;
77 assert (isinf (start_height) || start_height == end_height);
79 assert (isinf (end_height) || start_height == end_height);
81 m_ = (end_height - start_height) / (end - start);
82 if (start_height == end_height)
84 if (isinf (m_) || isnan (m_))
85 m_ = max_slope * (start_height < end_height ? 1 : -1);
86 assert (abs (m_) <= max_slope);
93 b_ = end_height - m_*end;
96 b_ = start_height - m_*start;
100 Building::height (Real x) const
103 return (x > 0) ? end_height_ : start_height_;
108 Building::intersection (Building const &other) const
110 return (b_ - other.b_) / (other.m_ - m_);
114 Building::leading_part (Real chop, Real h)
116 assert (chop > iv_[LEFT] && chop <= iv_[RIGHT] && !equal (chop, iv_[LEFT]));
117 assert (equal (h, height (chop)));
123 skyline_trailing_part (list<Building> *sky, Real x)
125 if (equal (x, sky->front ().iv_[RIGHT]))
128 assert (x < sky->front ().iv_[RIGHT]);
132 sky->front ().iv_[LEFT] = x;
133 sky->front ().start_height_ = sky->front ().height (x);
138 Building::obstructs (Building const &other) const
140 if (equal (intersection (other), iv_[LEFT]) || equal (start_height_, other.start_height_))
141 return m_ > other.m_ || (m_ == other.m_ && b_ > other.b_);
142 return start_height_ > other.start_height_;
146 Skyline::internal_merge_skyline (list<Building> *s1, list<Building> *s2,
147 list<Building> *const result)
149 while (!s1->empty ())
151 if (s2->front ().obstructs (s1->front ()))
154 Building b = s1->front ();
155 while (s2->front ().iv_[RIGHT] < b.iv_[RIGHT]
156 && s2->front ().end_height_ <= b.height (s2->front ().iv_[RIGHT]))
159 /* the front of s2 either intersects with b or it ends after b */
160 Real end = infinity_f;
161 if (s2->front ().end_height_ > b.height (s2->front ().iv_[RIGHT]))
162 end = b.intersection (s2->front ());
163 end = min (end, b.iv_[RIGHT]);
164 Real height = b.height (end);
166 b.leading_part (end, height);
167 result->push_front (b);
169 skyline_trailing_part (s1, end);
171 s1->front ().start_height_ = height;
172 skyline_trailing_part (s2, end);
178 empty_skyline (list<Building> *const ret)
180 ret->push_front (Building (-infinity_f, -infinity_f, -infinity_f, infinity_f, 0));
184 single_skyline (Building const &b, list<Building> *const ret, Real max_slope)
186 if (!isinf (b.iv_[RIGHT]))
187 ret->push_front (Building (b.iv_[RIGHT], b.end_height_, -infinity_f, infinity_f, max_slope));
189 if (!isinf (b.iv_[LEFT]))
190 ret->push_front (Building (-infinity_f, -infinity_f, b.start_height_, b.iv_[LEFT], max_slope));
194 Skyline::internal_build_skyline (list<Building> *buildings, list<Building> *const result)
196 vsize size = buildings->size ();
200 empty_skyline (result);
205 single_skyline (buildings->front (), result, max_slope_);
209 list<Building> right_half;
210 list<Building>::iterator i = buildings->begin ();
212 for (vsize s = 0; s < size/2; s++)
214 right_half.splice (right_half.end (), *buildings, i, buildings->end ());
216 list<Building> right;
218 internal_build_skyline (&right_half, &right);
219 internal_build_skyline (buildings, &left);
220 internal_merge_skyline (&right, &left, result);
227 empty_skyline (&buildings_);
230 Skyline::Skyline (Direction sky)
234 empty_skyline (&buildings_);
237 Skyline::Skyline (vector<Box> const &boxes, Axis a, Direction sky)
239 list<Building> bldgs;
243 for (vsize i = 0; i < boxes.size (); i++)
245 Interval iv = boxes[i][a];
246 Real height = sky * boxes[i][other_axis (a)][sky];
247 if (!iv.is_empty () && !isinf (height) && !equal (iv[LEFT], iv[RIGHT]))
248 bldgs.push_front (Building (iv[LEFT], height, height, iv[RIGHT], max_slope_));
250 internal_build_skyline (&bldgs, &buildings_);
251 assert (is_legal_skyline ());
255 Skyline::merge (Skyline const &other)
257 assert (sky_ == other.sky_);
259 list<Building> other_bld (other.buildings_);
260 list<Building> my_bld;
261 my_bld.splice (my_bld.begin (), buildings_);
262 internal_merge_skyline (&other_bld, &my_bld, &buildings_);
263 assert (is_legal_skyline ());
267 Skyline::insert (Box const &b, Axis a)
269 list<Building> other_bld;
270 list<Building> my_bld (buildings_);
272 Real height = sky_ * b[other_axis (a)][sky_];
274 single_skyline (Building (iv[LEFT], height, height, iv[RIGHT], max_slope_), &other_bld, max_slope_);
275 internal_merge_skyline (&other_bld, &my_bld, &buildings_);
276 assert (is_legal_skyline ());
280 Skyline::raise (Real r)
282 list<Building>::iterator end = buildings_.end ();
283 for (list<Building>::iterator i = buildings_.begin (); i != end; i++)
285 i->start_height_ += sky_ * r;
286 i->end_height_ += sky_ * r;
289 assert (is_legal_skyline ());
293 Skyline::distance (Skyline const &other) const
295 assert (sky_ == -other.sky_);
296 list<Building>::const_iterator i = buildings_.begin ();
297 list<Building>::const_iterator j = other.buildings_.begin ();
299 Real dist = -infinity_f;
300 for (; i != buildings_.end () && j != other.buildings_.end (); i++)
302 while (j->iv_[RIGHT] < i->iv_[LEFT])
305 Interval iv = intersection (i->iv_, j->iv_);
306 dist = max (dist, max (i->height (iv[LEFT]) + j->height (iv[LEFT]),
307 i->height (iv[RIGHT]) + j->height (iv[RIGHT])));
313 Skyline::height (Real airplane) const
315 assert (!isinf (airplane));
317 list<Building>::const_iterator i;
318 for (i = buildings_.begin (); i != buildings_.end (); i++)
320 if (i->iv_[RIGHT] >= airplane)
321 return sky_ * i->height (airplane);
328 Skyline::max_height () const
331 s.set_minimum_height (0);
332 return sky_ * distance (s);
336 Skyline::set_minimum_height (Real h)
339 s.buildings_.front ().start_height_ = h*sky_;
340 s.buildings_.front ().end_height_ = h*sky_;
341 s.buildings_.front ().b_ = h*sky_;
349 for (list<Building>::iterator i = buildings_.begin (); i != buildings_.end (); i++)
351 if (!isinf (i->iv_.length ()))
353 Stencil line = Line_interface::make_line (0.1,
354 Offset (i->iv_[LEFT], sky_*i->start_height_),
355 Offset (i->iv_[RIGHT], sky_*i->end_height_));
356 ret.add_stencil (line);