lily/skyline.cc

   1 /*
   2   This file is part of LilyPond, the GNU music typesetter.
   3
   4   Copyright (C) 2006--2012 Joe Neeman <joeneeman@gmail.com>
   5
   6   LilyPond is free software: you can redistribute it and/or modify
   7   it under the terms of the GNU General Public License as published by
   8   the Free Software Foundation, either version 3 of the License, or
   9   (at your option) any later version.
  10
  11   LilyPond is distributed in the hope that it will be useful,
  12   but WITHOUT ANY WARRANTY; without even the implied warranty of
  13   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14   GNU General Public License for more details.
  15
  16   You should have received a copy of the GNU General Public License
  17   along with LilyPond.  If not, see <http://www.gnu.org/licenses/>.
  18 */
  19
  20 #include "skyline.hh"
  21 #include "skyline-pair.hh"
  22 #include <deque>
  23 #include <cstdio>
  24
  25 #include "ly-smobs.icc"
  26
  27 /* A skyline is a sequence of non-overlapping buildings: something like
  28    this:
  29                    _______
  30                   |       \                                 ________
  31                   |        \                       ________/        \
  32         /\        |          \                    /                  \
  33        /  --------             \                 /                    \
  34       /                          \              /                      \
  35      /                             ------------/                        ----
  36    --
  37    Each building has a starting position, and ending position, a starting
  38    height and an ending height.
  39
  40    The following invariants are observed:
  41     - the start of the first building is at -infinity
  42     - the end of the last building is at infinity
  43     - if a building has infinite length (ie. the first and last buildings),
  44       then its starting height and ending height are equal
  45     - the end of one building is the same as the beginning of the next
  46       building
  47
  48    We also allow skylines to point down (the structure is exactly the same,
  49    but we think of the part above the line as being filled with mass and the
  50    part below as being empty). ::distance finds the minimum distance between
  51    an UP skyline and a DOWN skyline.
  52
  53    Note that we store DOWN skylines upside-down. That is, in order to compare
  54    a DOWN skyline with an UP skyline, we need to flip the DOWN skyline first.
  55    This means that the merging routine doesn't need to be aware of direction,
  56    but the distance routine does.
  57
  58    From 2007 through 2012, buildings of width less than EPS were discarded,
  59    citing numerical accuracy concerns.  We remember that floating point
  60    comparisons of nearly-equal values can be affected by rounding error.
  61    Also, some target machines use the x87 floating point unit, which provides
  62    extended precision for intermediate results held in registers. On this type
  63    of hardware comparisons such as
  64      double c = 1.0/3.0; boolean compare = (c == 1.0/3.0)
  65    could go either way because the 1.0/3.0 is allowed to be kept
  66    higher precision than the variable 'c'.
  67    Alert to these considerations, we now accept buildings of zero-width.
  68 */
  69
  70 static void
  71 print_buildings (list<Building> const &b)
  72 {
  73   for (list<Building>::const_iterator i = b.begin (); i != b.end (); i++)
  74     i->print ();
  75 }
  76
  77 void
  78 Skyline::print () const
  79 {
  80   print_buildings (buildings_);
  81 }
  82
  83 void
  84 Skyline::print_points () const
  85 {
  86   vector<Offset> ps (to_points (X_AXIS));
  87
  88   for (vsize i = 0; i < ps.size (); i++)
  89     printf ("(%f,%f)%s", ps[i][X_AXIS], ps[i][Y_AXIS],
  90             (i % 2) == 1 ? "\n" : " ");
  91 }
  92
  93 Building::Building (Real start, Real start_height, Real end_height, Real end)
  94 {
  95   if (isinf (start) || isinf (end))
  96     assert (start_height == end_height);
  97
  98   start_ = start;
  99   end_ = end;
 100   precompute (start, start_height, end_height, end);
 101 }
 102
 103 Building::Building (Box const &b, Axis horizon_axis, Direction sky)
 104 {
 105   Real start = b[horizon_axis][LEFT];
 106   Real end = b[horizon_axis][RIGHT];
 107   Real height = sky * b[other_axis (horizon_axis)][sky];
 108
 109   start_ = start;
 110   end_ = end;
 111   precompute (start, height, height, end);
 112 }
 113
 114 void
 115 Building::precompute (Real start, Real start_height, Real end_height, Real end)
 116 {
 117   slope_ = 0.0; /* if they were both infinite, we would get nan, not 0, from the prev line */
 118   if (start_height != end_height)
 119     slope_ = (end_height - start_height) / (end - start);
 120
 121   assert (!isinf (slope_) && !isnan (slope_));
 122
 123   if (isinf (start))
 124     {
 125       assert (start_height == end_height);
 126       y_intercept_ = start_height;
 127     }
 128   else
 129     y_intercept_ = start_height - slope_ * start;
 130 }
 131
 132 inline Real
 133 Building::height (Real x) const
 134 {
 135   return isinf (x) ? y_intercept_ : slope_ * x + y_intercept_;
 136 }
 137
 138 void
 139 Building::print () const
 140 {
 141   printf ("%f x + %f from %f to %f\n", slope_, y_intercept_, start_, end_);
 142 }
 143
 144 inline Real
 145 Building::intersection_x (Building const &other) const
 146 {
 147   Real ret = (y_intercept_ - other.y_intercept_) / (other.slope_ - slope_);
 148   return isnan (ret) ? -infinity_f : ret;
 149 }
 150
 151 void
 152 Building::leading_part (Real chop)
 153 {
 154   assert (chop <= end_);
 155   end_ = chop;
 156 }
 157
 158 // Returns a shift s such that (x + s, y) intersects the roof of
 159 // this building.  If no such shift exists, returns infinity_f.
 160 Real
 161 Building::shift_to_intersect (Real x, Real y) const
 162 {
 163   // Solve for s: y = (x + s)*m + b
 164   Real ret = (y - y_intercept_ - slope_ * x) / slope_;
 165
 166   if (ret >= start_ && ret <= end_ && !isinf (ret))
 167     return ret;
 168   return infinity_f;
 169 }
 170
 171 static Real
 172 first_intersection (Building const &b, list<Building> *const s, Real start_x)
 173 {
 174   while (!s->empty () && start_x < b.end_)
 175     {
 176       Building c = s->front ();
 177
 178       // conceals and intersection_x involve multiplication and
 179       // division. Avoid that, if we can.
 180       if (c.y_intercept_ == -infinity_f)
 181         {
 182           if (c.end_ > b.end_)
 183             return b.end_;
 184           start_x = c.end_;
 185           s->pop_front ();
 186           continue;
 187         }
 188
 189       if (c.conceals (b, start_x))
 190         return start_x;
 191
 192       Real i = b.intersection_x (c);
 193       if (i > start_x && i <= b.end_ && i <= c.end_)
 194         return i;
 195
 196       start_x = c.end_;
 197       if (b.end_ > c.end_)
 198         s->pop_front ();
 199     }
 200   return b.end_;
 201 }
 202
 203 bool
 204 Building::conceals (Building const &other, Real x) const
 205 {
 206   if (slope_ == other.slope_)
 207     return y_intercept_ > other.y_intercept_;
 208
 209   /* their slopes were not equal, so there is an intersection point */
 210   Real i = intersection_x (other);
 211   return (i <= x && slope_ > other.slope_)
 212          || (i > x && slope_ < other.slope_);
 213 }
 214
 215 // Remove redundant empty buildings from the skyline.
 216 // If there are two adjacent empty buildings, they can be
 217 // turned into one.
 218 void
 219 Skyline::normalize ()
 220 {
 221   bool last_empty = false;
 222   list<Building>::iterator i;
 223
 224   for (i = buildings_.begin (); i != buildings_.end (); i++)
 225     {
 226       if (last_empty && i->y_intercept_ == -infinity_f)
 227         {
 228           list<Building>::iterator last = i;
 229           last--;
 230           last->end_ = i->end_;
 231           buildings_.erase (i);
 232           i = last;
 233         }
 234       last_empty = (i->y_intercept_ == -infinity_f);
 235     }
 236
 237   assert (buildings_.front ().start_ == -infinity_f);
 238   assert (buildings_.back ().end_ == infinity_f);
 239 }
 240
 241 void
 242 Skyline::deholify ()
 243 {
 244   // Since a skyline should always be normalized, we can
 245   // assume that there are never two adjacent empty buildings.
 246   // That is, if center is empty then left and right are not.
 247   list<Building>::iterator left = buildings_.begin ();
 248   list<Building>::iterator center = buildings_.begin ();
 249   list<Building>::iterator right;
 250
 251   for (right = buildings_.begin (); right != buildings_.end (); right++)
 252     {
 253       if (center != buildings_.begin () && center->y_intercept_ == -infinity_f)
 254         {
 255           Real p1 = left->height (left->end_);
 256           Real p2 = right->height (right->start_);
 257           *center = Building (center->start_, p1, p2, center->end_);
 258
 259           left = center;
 260           center = right;
 261         }
 262     }
 263 }
 264
 265 void
 266 Skyline::internal_merge_skyline (list<Building> *s1, list<Building> *s2,
 267                                  list<Building> *const result) const
 268 {
 269   if (s1->empty () || s2->empty ())
 270     {
 271       programming_error ("tried to merge an empty skyline");
 272       return;
 273     }
 274
 275   Real x = -infinity_f;
 276   Real last_end = -infinity_f;
 277   while (!s1->empty ())
 278     {
 279       if (s2->front ().conceals (s1->front (), x))
 280         swap (s1, s2);
 281
 282       Building b = s1->front ();
 283       Building c = s2->front ();
 284
 285       // Optimization: if the other skyline is empty at this point,
 286       // we can avoid testing some intersections. Just grab as many
 287       // buildings from s1 as we can, and shove them onto the output.
 288       if (c.y_intercept_ == -infinity_f
 289           && c.end_ >= b.end_)
 290         {
 291           list<Building>::iterator i = s1->begin ();
 292           i++;
 293           while (i != s1->end () && i->end_ <= c.end_)
 294             i++;
 295
 296           s1->front ().start_ = x;
 297           result->splice (result->end (), *s1, s1->begin (), i);
 298           x = result->back ().end_;
 299           last_end = x;
 300           continue;
 301         }
 302
 303       Real end = first_intersection (b, s2, x);
 304       if (s2->empty ())
 305         {
 306           b.start_ = last_end;
 307           result->push_back (b);
 308           break;
 309         }
 310
 311       if (end >= x)
 312         {
 313           b.leading_part (end);
 314           b.start_ = last_end;
 315           last_end = b.end_;
 316           result->push_back (b);
 317         }
 318
 319       if (end >= s1->front ().end_)
 320         s1->pop_front ();
 321
 322       x = end;
 323     }
 324 }
 325
 326 static void
 327 empty_skyline (list<Building> *const ret)
 328 {
 329   ret->push_front (Building (-infinity_f, -infinity_f, -infinity_f, infinity_f));
 330 }
 331
 332 /*
 333   Given Building 'b', build a skyline containing only that building.
 334 */
 335 static void
 336 single_skyline (Building b, list<Building> *const ret)
 337 {
 338   assert (b.end_ >= b.start_);
 339
 340   if (b.start_ != -infinity_f)
 341     ret->push_back (Building (-infinity_f, -infinity_f,
 342                               -infinity_f, b.start_));
 343   ret->push_back (b);
 344   if (b.end_ != infinity_f)
 345     ret->push_back (Building (b.end_, -infinity_f,
 346                               -infinity_f, infinity_f));
 347 }
 348
 349 /* remove a non-overlapping set of boxes from BOXES and build a skyline
 350    out of them */
 351 static list<Building>
 352 non_overlapping_skyline (list<Building> *const buildings)
 353 {
 354   list<Building> result;
 355   Real last_end = -infinity_f;
 356   Building last_building (-infinity_f, -infinity_f, -infinity_f, infinity_f);
 357   list<Building>::iterator i = buildings->begin ();
 358   while (i != buildings->end ())
 359     {
 360       Real x1 = i->start_;
 361       Real y1 = i->height (i->start_);
 362       Real x2 = i->end_;
 363       Real y2 = i->height (i->end_);
 364
 365       // Drop buildings that will obviously have no effect.
 366       if (last_building.height (x1) >= y1
 367           && last_building.end_ >= x2
 368           && last_building.height (x2) >= y2)
 369         {
 370           list<Building>::iterator j = i++;
 371           buildings->erase (j);
 372           continue;
 373         }
 374
 375       if (x1 < last_end)
 376         {
 377           i++;
 378           continue;
 379         }
 380
 381       // Insert empty Buildings into any gaps. (TODO: is this needed? -KOH)
 382       if (x1 > last_end)
 383         result.push_back (Building (last_end, -infinity_f, -infinity_f, x1));
 384
 385       result.push_back (*i);
 386       last_building = *i;
 387       last_end = i->end_;
 388
 389       list<Building>::iterator j = i++;
 390       buildings->erase (j);
 391     }
 392
 393   if (last_end < infinity_f)
 394     result.push_back (Building (last_end, -infinity_f, -infinity_f, infinity_f));
 395   return result;
 396 }
 397
 398 class LessThanBuilding
 399 {
 400 public:
 401   bool operator () (Building const &b1, Building const &b2)
 402   {
 403     return b1.start_ < b2.start_
 404            || (b1.start_ == b2.start_ && b1.height (b1.start_) > b2.height (b1.start_));
 405   }
 406 };
 407
 408 /**
 409    BUILDINGS is a list of buildings, but they could be overlapping
 410    and in any order.  The returned list of buildings is ordered and non-overlapping.
 411 */
 412 list<Building>
 413 Skyline::internal_build_skyline (list<Building> *buildings) const
 414 {
 415   vsize size = buildings->size ();
 416
 417   if (size == 0)
 418     {
 419       list<Building> result;
 420       empty_skyline (&result);
 421       return result;
 422     }
 423   else if (size == 1)
 424     {
 425       list<Building> result;
 426       single_skyline (buildings->front (), &result);
 427       return result;
 428     }
 429
 430   deque<list<Building> > partials;
 431   buildings->sort (LessThanBuilding ());
 432   while (!buildings->empty ())
 433     partials.push_back (non_overlapping_skyline (buildings));
 434
 435   /* we'd like to say while (partials->size () > 1) but that's O (n).
 436      Instead, we exit in the middle of the loop */
 437   while (!partials.empty ())
 438     {
 439       list<Building> merged;
 440       list<Building> one = partials.front ();
 441       partials.pop_front ();
 442       if (partials.empty ())
 443         return one;
 444
 445       list<Building> two = partials.front ();
 446       partials.pop_front ();
 447       internal_merge_skyline (&one, &two, &merged);
 448       partials.push_back (merged);
 449     }
 450   assert (0);
 451   return list<Building> ();
 452 }
 453
 454 Skyline::Skyline ()
 455 {
 456   sky_ = UP;
 457   empty_skyline (&buildings_);
 458 }
 459
 460 Skyline::Skyline (Skyline const &src)
 461 {
 462   sky_ = src.sky_;
 463
 464   /* doesn't a list's copy constructor do this? -- jneem */
 465   for (list<Building>::const_iterator i = src.buildings_.begin ();
 466        i != src.buildings_.end (); i++)
 467     {
 468       buildings_.push_back (Building ((*i)));
 469     }
 470 }
 471
 472 Skyline::Skyline (Direction sky)
 473 {
 474   sky_ = sky;
 475   empty_skyline (&buildings_);
 476 }
 477
 478 /*
 479   Build skyline from a set of boxes.
 480
 481   Boxes should be non-empty on both axes.  Otherwise, they will be ignored
 482  */
 483 Skyline::Skyline (vector<Box> const &boxes, Axis horizon_axis, Direction sky)
 484 {
 485   list<Building> buildings;
 486   sky_ = sky;
 487
 488   for (vsize i = 0; i < boxes.size (); i++)
 489     if (!boxes[i].is_empty (X_AXIS)
 490         && !boxes[i].is_empty (Y_AXIS))
 491       buildings.push_front (Building (boxes[i], horizon_axis, sky));
 492
 493   buildings_ = internal_build_skyline (&buildings);
 494   normalize ();
 495 }
 496
 497 /*
 498   build skyline from a set of line segments.
 499
 500   Segments can be articulated from left to right or right to left.
 501   In the case of the latter, they will be stored internally as left to right.
 502  */
 503 Skyline::Skyline (vector<Drul_array<Offset> > const &segments, Axis horizon_axis, Direction sky)
 504 {
 505   list<Building> buildings;
 506   sky_ = sky;
 507
 508   for (vsize i = 0; i < segments.size (); i++)
 509     {
 510       Drul_array<Offset> const &seg = segments[i];
 511       Offset left = seg[LEFT];
 512       Offset right = seg[RIGHT];
 513       if (left[horizon_axis] > right[horizon_axis])
 514         swap (left, right);
 515
 516       Real x1 = left[horizon_axis];
 517       Real x2 = right[horizon_axis];
 518       Real y1 = left[other_axis (horizon_axis)] * sky;
 519       Real y2 = right[other_axis (horizon_axis)] * sky;
 520
 521       if (x1 <= x2)
 522         buildings.push_back (Building (x1, y1, y2, x2));
 523     }
 524
 525   buildings_ = internal_build_skyline (&buildings);
 526   normalize ();
 527 }
 528
 529 Skyline::Skyline (vector<Skyline_pair> const &skypairs, Direction sky)
 530 {
 531   sky_ = sky;
 532
 533   deque<Skyline> partials;
 534   for (vsize i = 0; i < skypairs.size (); i++)
 535     partials.push_back (Skyline ((skypairs[i])[sky]));
 536
 537   while (partials.size () > 1)
 538     {
 539       Skyline one = partials.front ();
 540       partials.pop_front ();
 541       Skyline two = partials.front ();
 542       partials.pop_front ();
 543
 544       one.merge (two);
 545       partials.push_back (one);
 546     }
 547
 548   if (partials.size ())
 549     buildings_.swap (partials.front ().buildings_);
 550   else
 551     buildings_.clear ();
 552 }
 553
 554 Skyline::Skyline (Box const &b, Axis horizon_axis, Direction sky)
 555 {
 556   sky_ = sky;
 557   if (!b.is_empty (X_AXIS) && !b.is_empty (Y_AXIS))
 558     {
 559       Building front (b, horizon_axis, sky);
 560       single_skyline (front, &buildings_);
 561       normalize ();
 562     }
 563 }
 564
 565 void
 566 Skyline::merge (Skyline const &other)
 567 {
 568   assert (sky_ == other.sky_);
 569
 570   if (other.is_empty ())
 571     return;
 572
 573   if (is_empty ())
 574     {
 575       buildings_ = other.buildings_;
 576       return;
 577     }
 578
 579   list<Building> other_bld (other.buildings_);
 580   list<Building> my_bld;
 581   my_bld.splice (my_bld.begin (), buildings_);
 582   internal_merge_skyline (&other_bld, &my_bld, &buildings_);
 583   normalize ();
 584 }
 585
 586 void
 587 Skyline::insert (Box const &b, Axis a)
 588 {
 589   list<Building> other_bld;
 590   list<Building> my_bld;
 591
 592   if (isnan (b[other_axis (a)][LEFT])
 593       || isnan (b[other_axis (a)][RIGHT]))
 594     {
 595       programming_error ("insane box for skyline");
 596       return;
 597     }
 598
 599   /* do the same filtering as in Skyline (vector<Box> const&, etc.) */
 600   if (b.is_empty (X_AXIS) || b.is_empty (Y_AXIS))
 601     return;
 602
 603   my_bld.splice (my_bld.begin (), buildings_);
 604   single_skyline (Building (b, a, sky_), &other_bld);
 605   internal_merge_skyline (&other_bld, &my_bld, &buildings_);
 606   normalize ();
 607 }
 608
 609 void
 610 Skyline::raise (Real r)
 611 {
 612   list<Building>::iterator end = buildings_.end ();
 613   for (list<Building>::iterator i = buildings_.begin (); i != end; i++)
 614     i->y_intercept_ += sky_ * r;
 615 }
 616
 617 void
 618 Skyline::shift (Real s)
 619 {
 620   list<Building>::iterator end = buildings_.end ();
 621   for (list<Building>::iterator i = buildings_.begin (); i != end; i++)
 622     {
 623       i->start_ += s;
 624       i->end_ += s;
 625       i->y_intercept_ -= s * i->slope_;
 626     }
 627 }
 628
 629 Real
 630 Skyline::distance (Skyline const &other, Real horizon_padding) const
 631 {
 632   Real dummy;
 633   return internal_distance (other, horizon_padding, &dummy);
 634 }
 635
 636 Real
 637 Skyline::touching_point (Skyline const &other, Real horizon_padding) const
 638 {
 639   Real touch;
 640   internal_distance (other, horizon_padding, &touch);
 641   return touch;
 642 }
 643
 644 Real
 645 Skyline::internal_distance (Skyline const &other, Real horizon_padding, Real *touch_point) const
 646 {
 647   if (horizon_padding == 0.0)
 648     return internal_distance (other, touch_point);
 649
 650   // Note that it is not necessary to build a padded version of other,
 651   // because the same effect can be achieved just by doubling horizon_padding.
 652   Skyline padded_this = padded (horizon_padding);
 653   return padded_this.internal_distance (other, touch_point);
 654 }
 655
 656 Skyline
 657 Skyline::padded (Real horizon_padding) const
 658 {
 659   if (horizon_padding < 0.0)
 660     warning ("Cannot have negative horizon padding.  Junking.");
 661
 662   if (horizon_padding <= 0.0)
 663     return *this;
 664
 665   list<Building> pad_buildings;
 666   for (list<Building>::const_iterator i = buildings_.begin (); i != buildings_.end (); ++i)
 667     {
 668       if (i->start_ > -infinity_f)
 669         {
 670           Real height = i->height (i->start_);
 671           if (height > -infinity_f)
 672             {
 673               // Add the sloped building that pads the left side of the current building.
 674               Real start = i->start_ - 2 * horizon_padding;
 675               Real end = i->start_ - horizon_padding;
 676               pad_buildings.push_back (Building (start, height - horizon_padding, height, end));
 677
 678               // Add the flat building that pads the left side of the current building.
 679               start = i->start_ - horizon_padding;
 680               end = i->start_;
 681               pad_buildings.push_back (Building (start, height, height, end));
 682             }
 683         }
 684
 685       if (i->end_ < infinity_f)
 686         {
 687           Real height = i->height (i->end_);
 688           if (height > -infinity_f)
 689             {
 690               // Add the flat building that pads the right side of the current building.
 691               Real start = i->end_;
 692               Real end = start + horizon_padding;
 693               pad_buildings.push_back (Building (start, height, height, end));
 694
 695               // Add the sloped building that pads the right side of the current building.
 696               start = end;
 697               end += horizon_padding;
 698               pad_buildings.push_back (Building (start, height, height - horizon_padding, end));
 699             }
 700         }
 701     }
 702
 703   // The buildings may be overlapping, so resolve that.
 704   list<Building> pad_skyline = internal_build_skyline (&pad_buildings);
 705
 706   // Merge the padding with the original, to make a new skyline.
 707   Skyline padded (sky_);
 708   list<Building> my_buildings = buildings_;
 709   padded.buildings_.clear ();
 710   internal_merge_skyline (&pad_skyline, &my_buildings, &padded.buildings_);
 711   padded.normalize ();
 712
 713   return padded;
 714 }
 715
 716 Real
 717 Skyline::internal_distance (Skyline const &other, Real *touch_point) const
 718 {
 719   assert (sky_ == -other.sky_);
 720
 721   list<Building>::const_iterator i = buildings_.begin ();
 722   list<Building>::const_iterator j = other.buildings_.begin ();
 723
 724   Real dist = -infinity_f;
 725   Real start = -infinity_f;
 726   Real touch = -infinity_f;
 727   while (i != buildings_.end () && j != other.buildings_.end ())
 728     {
 729       Real end = min (i->end_, j->end_);
 730       Real start_dist = i->height (start) + j->height (start);
 731       Real end_dist = i->height (end) + j->height (end);
 732       dist = max (dist, max (start_dist, end_dist));
 733
 734       if (end_dist == dist)
 735         touch = end;
 736       else if (start_dist == dist)
 737         touch = start;
 738
 739       if (i->end_ <= j->end_)
 740         i++;
 741       else
 742         j++;
 743       start = end;
 744     }
 745
 746   *touch_point = touch;
 747   return dist;
 748 }
 749
 750 Real
 751 Skyline::height (Real airplane) const
 752 {
 753   assert (!isinf (airplane));
 754
 755   list<Building>::const_iterator i;
 756   for (i = buildings_.begin (); i != buildings_.end (); i++)
 757     {
 758       if (i->end_ >= airplane)
 759         return sky_ * i->height (airplane);
 760     }
 761
 762   assert (0);
 763   return 0;
 764 }
 765
 766 Real
 767 Skyline::max_height () const
 768 {
 769   Real ret = -infinity_f;
 770
 771   list<Building>::const_iterator i;
 772   for (i = buildings_.begin (); i != buildings_.end (); ++i)
 773     {
 774       ret = max (ret, i->height (i->start_));
 775       ret = max (ret, i->height (i->end_));
 776     }
 777
 778   return sky_ * ret;
 779 }
 780
 781 Direction
 782 Skyline::direction () const
 783 {
 784   return sky_;
 785 }
 786
 787 Real
 788 Skyline::left () const
 789 {
 790   for (list<Building>::const_iterator i (buildings_.begin ());
 791        i != buildings_.end (); i++)
 792     if (i->y_intercept_ > -infinity_f)
 793       return i->start_;
 794
 795   return infinity_f;
 796 }
 797
 798 Real
 799 Skyline::right () const
 800 {
 801   for (list<Building>::const_reverse_iterator i (buildings_.rbegin ());
 802        i != buildings_.rend (); ++i)
 803     if (i->y_intercept_ > -infinity_f)
 804       return i->end_;
 805
 806   return -infinity_f;
 807 }
 808
 809 Real
 810 Skyline::max_height_position () const
 811 {
 812   Skyline s (-sky_);
 813   s.set_minimum_height (0);
 814   return touching_point (s);
 815 }
 816
 817 void
 818 Skyline::set_minimum_height (Real h)
 819 {
 820   Skyline s (sky_);
 821   s.buildings_.front ().y_intercept_ = h * sky_;
 822   merge (s);
 823 }
 824
 825 vector<Offset>
 826 Skyline::to_points (Axis horizon_axis) const
 827 {
 828   vector<Offset> out;
 829
 830   Real start = -infinity_f;
 831   for (list<Building>::const_iterator i (buildings_.begin ());
 832        i != buildings_.end (); i++)
 833     {
 834       out.push_back (Offset (start, sky_ * i->height (start)));
 835       out.push_back (Offset (i->end_, sky_ * i->height (i->end_)));
 836       start = i->end_;
 837     }
 838
 839   if (horizon_axis == Y_AXIS)
 840     for (vsize i = 0; i < out.size (); i++)
 841       out[i] = out[i].swapped ();
 842
 843   return out;
 844 }
 845
 846 bool
 847 Skyline::is_empty () const
 848 {
 849   if (!buildings_.size ())
 850     return true;
 851   Building b = buildings_.front ();
 852   return b.end_ == infinity_f && b.y_intercept_ == -infinity_f;
 853 }
 854
 855 void
 856 Skyline::clear ()
 857 {
 858   buildings_.clear ();
 859   empty_skyline (&buildings_);
 860 }
 861
 862 /****************************************************************/
 863
 864 IMPLEMENT_SIMPLE_SMOBS (Skyline);
 865 IMPLEMENT_TYPE_P (Skyline, "ly:skyline?");
 866 IMPLEMENT_DEFAULT_EQUAL_P (Skyline);
 867
 868 SCM
 869 Skyline::mark_smob (SCM s)
 870 {
 871   ASSERT_LIVE_IS_ALLOWED (s);
 872   return SCM_EOL;
 873 }
 874
 875 int
 876 Skyline::print_smob (SCM s, SCM port, scm_print_state *)
 877 {
 878   Skyline *r = (Skyline *) SCM_CELL_WORD_1 (s);
 879   (void) r;
 880
 881   scm_puts ("#<Skyline>", port);
 882
 883   return 1;
 884 }
 885
 886 MAKE_SCHEME_CALLBACK_WITH_OPTARGS (Skyline, get_touching_point, 3, 1, "")
 887 SCM
 888 Skyline::get_touching_point (SCM skyline_scm, SCM other_skyline_scm, SCM horizon_padding_scm)
 889 {
 890   LY_ASSERT_SMOB (Skyline, other_skyline_scm, 1);
 891
 892   Real horizon_padding = 0;
 893   if (horizon_padding_scm != SCM_UNDEFINED)
 894     {
 895       LY_ASSERT_TYPE (scm_is_number, horizon_padding_scm, 3);
 896       horizon_padding = scm_to_double (horizon_padding_scm);
 897     }
 898
 899   Skyline *skyline = Skyline::unsmob (skyline_scm);
 900   Skyline *other_skyline = Skyline::unsmob (other_skyline_scm);
 901   return scm_from_double (skyline->touching_point (*other_skyline, horizon_padding));
 902 }
 903
 904 MAKE_SCHEME_CALLBACK_WITH_OPTARGS (Skyline, get_distance, 3, 1, "")
 905 SCM
 906 Skyline::get_distance (SCM skyline_scm, SCM other_skyline_scm, SCM horizon_padding_scm)
 907 {
 908   LY_ASSERT_SMOB (Skyline, other_skyline_scm, 1);
 909
 910   Real horizon_padding = 0;
 911   if (horizon_padding_scm != SCM_UNDEFINED)
 912     {
 913       LY_ASSERT_TYPE (scm_is_number, horizon_padding_scm, 3);
 914       horizon_padding = scm_to_double (horizon_padding_scm);
 915     }
 916
 917   Skyline *skyline = Skyline::unsmob (skyline_scm);
 918   Skyline *other_skyline = Skyline::unsmob (other_skyline_scm);
 919   return scm_from_double (skyline->distance (*other_skyline, horizon_padding));
 920 }
 921
 922 MAKE_SCHEME_CALLBACK (Skyline, get_max_height, 1)
 923 SCM
 924 Skyline::get_max_height (SCM skyline_scm)
 925 {
 926   return scm_from_double (Skyline::unsmob (skyline_scm)->max_height ());
 927 }
 928
 929 MAKE_SCHEME_CALLBACK (Skyline, get_max_height_position, 1)
 930 SCM
 931 Skyline::get_max_height_position (SCM skyline_scm)
 932 {
 933   return scm_from_double (Skyline::unsmob (skyline_scm)->max_height_position ());
 934 }
 935
 936 MAKE_SCHEME_CALLBACK (Skyline, get_height, 2)
 937 SCM
 938 Skyline::get_height (SCM skyline_scm, SCM x_scm)
 939 {
 940   Real x = robust_scm2double (x_scm, 0.0);
 941   return scm_from_double (Skyline::unsmob (skyline_scm)->height (x));
 942 }
 943
 944 LY_DEFINE (ly_skyline_empty_p, "ly:skyline-empty?",
 945            1, 0, 0, (SCM sky),
 946            "Return whether @var{sky} is empty.")
 947 {
 948   Skyline *s = Skyline::unsmob (sky);
 949   LY_ASSERT_SMOB (Skyline, sky, 1);
 950   return scm_from_bool (s->is_empty ());
 951 }