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]) + EPS)
159 /* the front of s2 either intersects with b or it ends after b */
160 Real end = infinity_f;
161 Real s2_end_height = s2->front ().end_height_;
162 Real s1_end_height = b.height (s2->front ().iv_[RIGHT]);
163 if (s2_end_height > s1_end_height + EPS)
164 end = b.intersection (s2->front ());
165 end = min (end, b.iv_[RIGHT]);
166 Real height = b.height (end);
168 b.leading_part (end, height);
169 result->push_front (b);
171 skyline_trailing_part (s1, end);
173 s1->front ().start_height_ = height;
174 skyline_trailing_part (s2, end);
180 empty_skyline (list<Building> *const ret)
182 ret->push_front (Building (-infinity_f, -infinity_f, -infinity_f, infinity_f, 0));
186 single_skyline (Building const &b, list<Building> *const ret, Real max_slope)
188 if (!isinf (b.iv_[RIGHT]))
189 ret->push_front (Building (b.iv_[RIGHT], b.end_height_, -infinity_f, infinity_f, max_slope));
191 if (!isinf (b.iv_[LEFT]))
192 ret->push_front (Building (-infinity_f, -infinity_f, b.start_height_, b.iv_[LEFT], max_slope));
196 Skyline::internal_build_skyline (list<Building> *buildings, list<Building> *const result)
198 vsize size = buildings->size ();
202 empty_skyline (result);
207 single_skyline (buildings->front (), result, max_slope_);
211 list<Building> right_half;
212 list<Building>::iterator i = buildings->begin ();
214 for (vsize s = 0; s < size/2; s++)
216 right_half.splice (right_half.end (), *buildings, i, buildings->end ());
218 list<Building> right;
220 internal_build_skyline (&right_half, &right);
221 internal_build_skyline (buildings, &left);
222 internal_merge_skyline (&right, &left, result);
229 empty_skyline (&buildings_);
232 Skyline::Skyline (Direction sky)
236 empty_skyline (&buildings_);
239 Skyline::Skyline (vector<Box> const &boxes, Axis a, Direction sky)
241 list<Building> bldgs;
245 for (vsize i = 0; i < boxes.size (); i++)
247 Interval iv = boxes[i][a];
248 Real height = sky * boxes[i][other_axis (a)][sky];
249 if (!iv.is_empty () && !isinf (height) && !equal (iv[LEFT], iv[RIGHT]))
250 bldgs.push_front (Building (iv[LEFT], height, height, iv[RIGHT], max_slope_));
252 internal_build_skyline (&bldgs, &buildings_);
253 assert (is_legal_skyline ());
257 Skyline::merge (Skyline const &other)
259 assert (sky_ == other.sky_);
261 list<Building> other_bld (other.buildings_);
262 list<Building> my_bld;
263 my_bld.splice (my_bld.begin (), buildings_);
264 internal_merge_skyline (&other_bld, &my_bld, &buildings_);
265 assert (is_legal_skyline ());
269 Skyline::insert (Box const &b, Axis a)
271 list<Building> other_bld;
272 list<Building> my_bld;
274 Real height = sky_ * b[other_axis (a)][sky_];
276 my_bld.splice (my_bld.begin (), buildings_);
277 single_skyline (Building (iv[LEFT], height, height, iv[RIGHT], max_slope_), &other_bld, max_slope_);
278 internal_merge_skyline (&other_bld, &my_bld, &buildings_);
279 assert (is_legal_skyline ());
283 Skyline::raise (Real r)
285 list<Building>::iterator end = buildings_.end ();
286 for (list<Building>::iterator i = buildings_.begin (); i != end; i++)
288 i->start_height_ += sky_ * r;
289 i->end_height_ += sky_ * r;
292 assert (is_legal_skyline ());
296 Skyline::distance (Skyline const &other) const
298 assert (sky_ == -other.sky_);
299 list<Building>::const_iterator i = buildings_.begin ();
300 list<Building>::const_iterator j = other.buildings_.begin ();
302 Real dist = -infinity_f;
303 for (; i != buildings_.end () && j != other.buildings_.end (); i++)
305 while (j->iv_[RIGHT] < i->iv_[LEFT])
308 Interval iv = intersection (i->iv_, j->iv_);
309 dist = max (dist, max (i->height (iv[LEFT]) + j->height (iv[LEFT]),
310 i->height (iv[RIGHT]) + j->height (iv[RIGHT])));
316 Skyline::height (Real airplane) const
318 assert (!isinf (airplane));
320 list<Building>::const_iterator i;
321 for (i = buildings_.begin (); i != buildings_.end (); i++)
323 if (i->iv_[RIGHT] >= airplane)
324 return sky_ * i->height (airplane);
331 Skyline::max_height () const
334 s.set_minimum_height (0);
335 return sky_ * distance (s);
339 Skyline::set_minimum_height (Real h)
342 s.buildings_.front ().start_height_ = h*sky_;
343 s.buildings_.front ().end_height_ = h*sky_;
344 s.buildings_.front ().b_ = h*sky_;
352 for (list<Building>::iterator i = buildings_.begin (); i != buildings_.end (); i++)
354 if (!isinf (i->iv_.length ()))
356 Stencil line = Line_interface::make_line (0.1,
357 Offset (i->iv_[LEFT], sky_*i->start_height_),
358 Offset (i->iv_[RIGHT], sky_*i->end_height_));
359 ret.add_stencil (line);