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 /* A skyline is a sequence of non-overlapping buildings: something like
18 / --------------- -------
20 Each building has a starting position, and ending position, a starting
21 height and an ending height.
23 The following invariants are observed:
24 - the start of the first building is at -infinity
25 - the end of the last building is at infinity
26 - if a building has infinite length (ie. the first and last buildings),
27 then its starting height and ending height are equal
28 - the end of one building is the same as the beginning of the next
31 We also allow skylines to point down (the structure is exactly the same,
32 but we think of the part above the line as being filled with mass and the
33 part below as being empty). ::distance finds the minimum distance between
34 an UP skyline and a DOWN skyline.
36 Note that we store DOWN skylines upside-down. That is, in order to compare
37 a DOWN skyline with an UP skyline, we need to flip the DOWN skyline first.
38 This means that the merging routine doesn't need to be aware of direction,
39 but the distance routine does.
45 equal (Real x, Real y)
47 return abs (x - y) < EPS || (isinf (x) && isinf (y) && ((x > 0) == (y > 0)));
51 Skyline::is_legal_skyline () const
53 list<Building>::const_iterator i;
54 Real last_x = -infinity_f;
55 for (i = buildings_.begin (); i != buildings_.end (); i++)
57 if (isinf (i->start_height_) != isinf (i->end_height_))
59 if (i->iv_[LEFT] != last_x)
61 if (isinf (i->iv_.length ()) && i->start_height_ != i->end_height_)
63 last_x = i->iv_[RIGHT];
65 return last_x == infinity_f;
68 Building::Building (Real start, Real start_height, Real end_height, Real end)
71 start_height_ = start_height;
72 end_height_ = end_height;
74 if (isinf (start_height) || isinf (start) || isinf (end))
75 end_height_ = start_height;
76 else if (isinf (end_height))
77 start_height_ = end_height;
79 m_ = (end_height - start_height) / (end - start);
80 b_ = start_height - m_*start;
82 if (isinf (start_height) || isinf (start) || isinf (end))
90 Building::height (Real x) const
98 Building::intersection (Building const &other) const
100 return (b_ - other.b_) / (other.m_ - m_);
104 Building::leading_part (Real chop)
106 assert (chop > iv_[LEFT] && chop <= iv_[RIGHT] && !equal (chop, iv_[LEFT]));
108 end_height_ = height (chop);
112 skyline_trailing_part (list<Building> *sky, Real x)
114 if (equal (x, sky->front ().iv_[RIGHT]))
117 assert (x < sky->front ().iv_[RIGHT]);
121 sky->front ().iv_[LEFT] = x;
122 sky->front ().start_height_ = sky->front ().height (x);
127 Building::obstructs (Building const &other) const
129 if (equal (intersection (other), iv_[LEFT]) || equal (start_height_, other.start_height_))
130 return m_ > other.m_;
131 return start_height_ > other.start_height_;
135 /* precondition: the building should be visible above the first
136 building in skyline. The building and the skyline should
137 start at the same point.
139 return the point at which the building b is no longer visible,
140 either because it has ended or because the skyline has risen
141 above it. Truncate the skyline at that point.
144 Skyline::last_visible_point (Building const &b, list<Building> *const skyline)
146 assert (!skyline->front ().obstructs (b));
149 Building other = skyline->front ();
151 /* there are 3 interesting cases:
152 1) the roofs intersect within the spans of the buildings */
153 Real intersect = b.intersection (other);
154 if (intersection (b.iv_, other.iv_).contains (intersect))
156 if (equal (intersect, b.iv_[LEFT]))
158 /* if the buildings have almost the same starting height, we can find
159 that their intersection "equals" the start point. In this case, we
160 just skip the intersection.
162 assert (b.m_ >= other.m_);
166 skyline_trailing_part (skyline, intersect);
171 /* 2) the first building ends. This is guaranteed to happen before
172 the skyline becomes empty because it has to end at infinity */
173 if (skyline->empty () && !other.iv_.contains (b.iv_[RIGHT]))
175 if (other.iv_.contains (b.iv_[RIGHT]))
177 skyline_trailing_part (skyline, b.iv_[RIGHT]);
181 assert (!skyline->empty ());
182 skyline->pop_front ();
183 other = skyline->front ();
185 /* 3) the next building in the skyline starts above b */
186 if (other.start_height_ > b.height (other.iv_[LEFT]))
187 return other.iv_[LEFT];
192 Skyline::internal_merge_skyline (list<Building> *s1, list<Building> *s2,
193 list<Building> *const result)
195 while (!s1->empty ())
197 if (s2->front ().obstructs (s1->front ()))
200 Building b = s1->front ();
201 Real end = last_visible_point (b, s2);
203 b.leading_part (end);
204 result->push_front (b);
206 skyline_trailing_part (s1, end);
212 empty_skyline (list<Building> *const ret)
214 ret->push_front (Building (-infinity_f, -infinity_f, -infinity_f, infinity_f));
218 single_skyline (Building const &b, list<Building> *const ret)
220 if (!isinf (b.iv_[RIGHT]))
221 ret->push_front (Building (b.iv_[RIGHT], -infinity_f, -infinity_f, infinity_f));
223 if (!isinf (b.iv_[LEFT]))
224 ret->push_front (Building (-infinity_f, -infinity_f, -infinity_f, b.iv_[LEFT]));
228 Skyline::internal_build_skyline (list<Building> *buildings, list<Building> *const result)
230 vsize size = buildings->size ();
234 empty_skyline (result);
239 single_skyline (buildings->front (), result);
243 list<Building> right_half;
244 list<Building>::iterator i = buildings->begin ();
246 for (vsize s = 0; s < size/2; s++)
248 right_half.splice (right_half.end (), *buildings, i, buildings->end ());
250 list<Building> right;
252 internal_build_skyline (&right_half, &right);
253 internal_build_skyline (buildings, &left);
254 internal_merge_skyline (&right, &left, result);
260 empty_skyline (&buildings_);
263 Skyline::Skyline (Direction sky)
266 empty_skyline (&buildings_);
269 Skyline::Skyline (vector<Box> const &boxes, Axis a, Direction sky)
271 list<Building> bldgs;
274 for (vsize i = 0; i < boxes.size (); i++)
276 Interval iv = boxes[i][a];
277 Real height = sky * boxes[i][other_axis (a)][sky];
278 if (!iv.is_empty () && !isinf (height) && !equal (iv[LEFT], iv[RIGHT]))
279 bldgs.push_front (Building (iv[LEFT], height, height, iv[RIGHT]));
281 internal_build_skyline (&bldgs, &buildings_);
282 assert (is_legal_skyline ());
286 Skyline::merge (Skyline const &other)
288 assert (sky_ == other.sky_);
290 list<Building> other_bld (other.buildings_);
291 list<Building> my_bld;
292 my_bld.splice (my_bld.begin (), buildings_);
293 internal_merge_skyline (&other_bld, &my_bld, &buildings_);
294 assert (is_legal_skyline ());
298 Skyline::insert (Box const &b, Axis a)
300 list<Building> other_bld;
301 list<Building> my_bld (buildings_);
303 Real height = sky_ * b[other_axis (a)][sky_];
305 single_skyline (Building (iv[LEFT], height, height, iv[RIGHT]), &other_bld);
306 internal_merge_skyline (&other_bld, &my_bld, &buildings_);
307 assert (is_legal_skyline ());
311 Skyline::raise (Real r)
313 list<Building>::iterator end = buildings_.end ();
314 for (list<Building>::iterator i = buildings_.begin (); i != end; i++)
316 i->start_height_ += sky_ * r;
317 i->end_height_ += sky_ * r;
320 assert (is_legal_skyline ());
324 Skyline::distance (Skyline const &other) const
326 assert (sky_ == -other.sky_);
327 list<Building>::const_iterator i = buildings_.begin ();
328 list<Building>::const_iterator j = other.buildings_.begin ();
330 Real dist = -infinity_f;
331 for (; i != buildings_.end () && j != other.buildings_.end (); i++)
333 while (j->iv_[RIGHT] < i->iv_[LEFT])
336 list<Building>::const_iterator k;
337 for (k = j; k->iv_[LEFT] <= i->iv_[RIGHT] && k != other.buildings_.end (); k++)
339 Interval iv = intersection (i->iv_, k->iv_);
340 dist = max (dist, max (i->height (iv[LEFT]) + k->height (iv[LEFT]),
341 i->height (iv[RIGHT]) + k->height (iv[RIGHT])));
348 Skyline::height (Real airplane) const
350 assert (!isinf (airplane));
352 list<Building>::const_iterator i;
353 for (i = buildings_.begin (); i != buildings_.end (); i++)
355 if (i->iv_[RIGHT] > airplane)
356 return sky_ * i->height (airplane);
357 if (i->iv_[RIGHT] == airplane)
359 assert (i != buildings_.end ());
360 list<Building>::const_iterator j = i;
362 return sky_ * (max (i->end_height_, j->start_height_));
370 Skyline::max_height () const
373 s.set_minimum_height (0);
374 return sky_ * distance (s);
378 Skyline::set_minimum_height (Real h)
381 s.buildings_.front ().start_height_ = h*sky_;
382 s.buildings_.front ().end_height_ = h*sky_;
383 s.buildings_.front ().b_ = h*sky_;