lily/skyline.cc

   1 /* skyline.cc -- implement the Skyline class
   2
   3    source file of the GNU LilyPond music typesetter
   4
   5    (c) 2006 Joe Neeman <joeneeman@gmail.com>
   6 */
   7
   8 #include "skyline.hh"
   9
  10 #include "line-interface.hh"
  11
  12 /* A skyline is a sequence of non-overlapping buildings: something like
  13    this:
  14                    _______
  15                   /       \                                ________
  16                  /         \                      ________/        \
  17         /\      /           \                    /                  \
  18        /  -----/              \                 /                    \
  19       /                         \              /                      \
  20      /                            ------------/                        ----
  21    --
  22    Each building has a starting position, and ending position, a starting
  23    height and an ending height.
  24
  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
  31       building
  32
  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.
  37
  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.
  42 */
  43
  44 #define EPS 1e-10
  45
  46 static inline bool
  47 equal (Real x, Real y)
  48 {
  49   return abs (x - y) < EPS || (isinf (x) && isinf (y) && ((x > 0) == (y > 0)));
  50 }
  51
  52 bool
  53 Skyline::is_legal_skyline () const
  54 {
  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++)
  59     {
  60       if (i->iv_[LEFT] != last_x)
  61         return false;
  62       if (i != buildings_.begin () && !equal (i->start_height_, last_h))
  63         return false;
  64       last_x = i->iv_[RIGHT];
  65       last_h = i->end_height_;
  66     }
  67   return last_x == infinity_f;
  68 }
  69
  70 Building::Building (Real start, Real start_height, Real end_height, Real end, Real max_slope)
  71   : iv_ (start, end)
  72 {
  73   start_height_ = start_height;
  74   end_height_ = end_height;
  75
  76   if (isinf (start))
  77     assert (isinf (start_height) || start_height == end_height);
  78   if (isinf (end))
  79     assert (isinf (end_height) || start_height == end_height);
  80
  81   m_ = (end_height - start_height) / (end - start);
  82   if (start_height == end_height)
  83     m_ = 0;
  84   if (isinf (m_) || isnan (m_))
  85     m_ = max_slope * (start_height < end_height ? 1 : -1);
  86   assert (abs (m_) <= max_slope);
  87
  88   if (isinf (start))
  89     {
  90       if (isinf (end))
  91         b_ = start_height;
  92       else
  93         b_ = end_height - m_*end;
  94     }
  95   else
  96     b_ = start_height - m_*start;
  97 }
  98
  99 Real
 100 Building::height (Real x) const
 101 {
 102   if (isinf (x))
 103     return (x > 0) ? end_height_ : start_height_;
 104   return m_*x + b_;
 105 }
 106
 107 Real
 108 Building::intersection (Building const &other) const
 109 {
 110   return (b_ - other.b_) / (other.m_ - m_);
 111 }
 112
 113 void
 114 Building::leading_part (Real chop, Real h)
 115 {
 116   assert (chop > iv_[LEFT] && chop <= iv_[RIGHT] && !equal (chop, iv_[LEFT]));
 117   assert (equal (h, height (chop)));
 118   iv_[RIGHT] = chop;
 119   end_height_ = h;
 120 }
 121
 122 static void
 123 skyline_trailing_part (list<Building> *sky, Real x)
 124 {
 125   if (equal (x, sky->front ().iv_[RIGHT]))
 126     sky->pop_front ();
 127   else
 128     assert (x < sky->front ().iv_[RIGHT]);
 129
 130   if (!sky->empty ())
 131     {
 132       sky->front ().iv_[LEFT] = x;
 133       sky->front ().start_height_ = sky->front ().height (x);
 134     }
 135 }
 136
 137 bool
 138 Building::obstructs (Building const &other) const
 139 {
 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_;
 143 }
 144
 145 void
 146 Skyline::internal_merge_skyline (list<Building> *s1, list<Building> *s2,
 147                                  list<Building> *const result)
 148 {
 149   while (!s1->empty ())
 150     {
 151       if (s2->front ().obstructs (s1->front ()))
 152         swap (s1, s2);
 153
 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)
 157         s2->pop_front ();
 158
 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);
 167
 168       b.leading_part (end, height);
 169       result->push_front (b);
 170
 171       skyline_trailing_part (s1, end);
 172       if (!s1->empty ())
 173         s1->front ().start_height_ = height;
 174       skyline_trailing_part (s2, end);
 175     }
 176   result->reverse ();
 177 }
 178
 179 static void
 180 empty_skyline (list<Building> *const ret)
 181 {
 182   ret->push_front (Building (-infinity_f, -infinity_f, -infinity_f, infinity_f, 0));
 183 }
 184
 185 static void
 186 single_skyline (Building const &b, list<Building> *const ret, Real max_slope)
 187 {
 188   if (!isinf (b.iv_[RIGHT]))
 189     ret->push_front (Building (b.iv_[RIGHT], b.end_height_, -infinity_f, infinity_f, max_slope));
 190   ret->push_front (b);
 191   if (!isinf (b.iv_[LEFT]))
 192     ret->push_front (Building (-infinity_f, -infinity_f, b.start_height_, b.iv_[LEFT], max_slope));
 193 }
 194
 195 void
 196 Skyline::internal_build_skyline (list<Building> *buildings, list<Building> *const result)
 197 {
 198   vsize size = buildings->size ();
 199
 200   if (size == 0)
 201     {
 202       empty_skyline (result);
 203       return;
 204     }
 205   else if (size == 1)
 206     {
 207       single_skyline (buildings->front (), result, max_slope_);
 208       return;
 209     }
 210
 211   list<Building> right_half;
 212   list<Building>::iterator i = buildings->begin ();
 213
 214   for (vsize s = 0; s < size/2; s++)
 215     i++;
 216   right_half.splice (right_half.end (), *buildings, i, buildings->end ());
 217
 218   list<Building> right;
 219   list<Building> left;
 220   internal_build_skyline (&right_half, &right);
 221   internal_build_skyline (buildings, &left);
 222   internal_merge_skyline (&right, &left, result);
 223 }
 224
 225 Skyline::Skyline ()
 226 {
 227   max_slope_ = 2;
 228   sky_ = UP;
 229   empty_skyline (&buildings_);
 230 }
 231
 232 Skyline::Skyline (Direction sky)
 233 {
 234   max_slope_ = 2;
 235   sky_ = sky;
 236   empty_skyline (&buildings_);
 237 }
 238
 239 Skyline::Skyline (vector<Box> const &boxes, Axis a, Direction sky)
 240 {
 241   list<Building> bldgs;
 242   sky_ = sky;
 243   max_slope_ = 2;
 244
 245   for (vsize i = 0; i < boxes.size (); i++)
 246     {
 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_));
 251     }
 252   internal_build_skyline (&bldgs, &buildings_);
 253   assert (is_legal_skyline ());
 254 }
 255
 256 void
 257 Skyline::merge (Skyline const &other)
 258 {
 259   assert (sky_ == other.sky_);
 260
 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 ());
 266 }
 267
 268 void
 269 Skyline::insert (Box const &b, Axis a)
 270 {
 271   list<Building> other_bld;
 272   list<Building> my_bld;
 273   Interval iv = b[a];
 274   Real height = sky_ * b[other_axis (a)][sky_];
 275
 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 ());
 280 }
 281
 282 void
 283 Skyline::raise (Real r)
 284 {
 285   list<Building>::iterator end = buildings_.end ();
 286   for (list<Building>::iterator i = buildings_.begin (); i != end; i++)
 287     {
 288       i->start_height_ += sky_ * r;
 289       i->end_height_ += sky_ * r;
 290       i->b_ += sky_ * r;
 291     }
 292   assert (is_legal_skyline ());
 293 }
 294
 295 Real
 296 Skyline::distance (Skyline const &other) const
 297 {
 298   assert (sky_ == -other.sky_);
 299   list<Building>::const_iterator i = buildings_.begin ();
 300   list<Building>::const_iterator j = other.buildings_.begin ();
 301
 302   Real dist = -infinity_f;
 303   while (i != buildings_.end () && j != other.buildings_.end ())
 304     {
 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])));
 308       if (i->iv_[RIGHT] <= j->iv_[RIGHT])
 309         i++;
 310       else
 311         j++;
 312     }
 313   return dist;
 314 }
 315
 316 Real
 317 Skyline::height (Real airplane) const
 318 {
 319   assert (!isinf (airplane));
 320
 321   list<Building>::const_iterator i;
 322   for (i = buildings_.begin (); i != buildings_.end (); i++)
 323     {
 324       if (i->iv_[RIGHT] >= airplane)
 325         return sky_ * i->height (airplane);
 326     }
 327   assert (0);
 328   return 0;
 329 }
 330
 331 Real
 332 Skyline::max_height () const
 333 {
 334   Skyline s (-sky_);
 335   s.set_minimum_height (0);
 336   return sky_ * distance (s);
 337 }
 338
 339 void
 340 Skyline::set_minimum_height (Real h)
 341 {
 342   Skyline s (sky_);
 343   s.buildings_.front ().start_height_ = h*sky_;
 344   s.buildings_.front ().end_height_ = h*sky_;
 345   s.buildings_.front ().b_ = h*sky_;
 346   merge (s);
 347 }
 348
 349 Stencil
 350 Skyline::stencil ()
 351 {
 352   Stencil ret;
 353   for (list<Building>::iterator i = buildings_.begin (); i != buildings_.end (); i++)
 354     {
 355       if (!isinf (i->iv_.length ()))
 356         {
 357           Stencil line = Line_interface::make_line (0.1,
 358                                                     Offset (i->iv_[LEFT], sky_*i->start_height_),
 359                                                     Offset (i->iv_[RIGHT], sky_*i->end_height_));
 360           ret.add_stencil (line);
 361         }
 362     }
 363   return ret;
 364 }