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 if (fabs(slope_) > 1e6)
 129     // too steep to be stored in slope-intercept form, given round-off error
 130     {
 131       slope_ = 0.0;
 132       y_intercept_ = max(start_height, end_height);
 133     }
 134   else
 135     y_intercept_ = start_height - slope_ * start;
 136 }
 137
 138 inline Real
 139 Building::height (Real x) const
 140 {
 141   return isinf (x) ? y_intercept_ : slope_ * x + y_intercept_;
 142 }
 143
 144 void
 145 Building::print () const
 146 {
 147   printf ("%f x + %f from %f to %f\n", slope_, y_intercept_, start_, end_);
 148 }
 149
 150 inline Real
 151 Building::intersection_x (Building const &other) const
 152 {
 153   Real ret = (y_intercept_ - other.y_intercept_) / (other.slope_ - slope_);
 154   return isnan (ret) ? -infinity_f : ret;
 155 }
 156
 157 void
 158 Building::leading_part (Real chop)
 159 {
 160   assert (chop <= end_);
 161   end_ = chop;
 162 }
 163
 164 // Returns a shift s such that (x + s, y) intersects the roof of
 165 // this building.  If no such shift exists, returns infinity_f.
 166 Real
 167 Building::shift_to_intersect (Real x, Real y) const
 168 {
 169   // Solve for s: y = (x + s)*m + b
 170   Real ret = (y - y_intercept_ - slope_ * x) / slope_;
 171
 172   if (ret >= start_ && ret <= end_ && !isinf (ret))
 173     return ret;
 174   return infinity_f;
 175 }
 176
 177 static Real
 178 first_intersection (Building const &b, list<Building> *const s, Real start_x)
 179 {
 180   while (!s->empty () && start_x < b.end_)
 181     {
 182       Building c = s->front ();
 183
 184       // conceals and intersection_x involve multiplication and
 185       // division. Avoid that, if we can.
 186       if (c.y_intercept_ == -infinity_f)
 187         {
 188           if (c.end_ > b.end_)
 189             return b.end_;
 190           start_x = c.end_;
 191           s->pop_front ();
 192           continue;
 193         }
 194
 195       if (c.conceals (b, start_x))
 196         return start_x;
 197
 198       Real i = b.intersection_x (c);
 199       if (i > start_x && i <= b.end_ && i <= c.end_)
 200         return i;
 201
 202       start_x = c.end_;
 203       if (b.end_ > c.end_)
 204         s->pop_front ();
 205     }
 206   return b.end_;
 207 }
 208
 209 bool
 210 Building::conceals (Building const &other, Real x) const
 211 {
 212   if (slope_ == other.slope_)
 213     return y_intercept_ > other.y_intercept_;
 214
 215   /* their slopes were not equal, so there is an intersection point */
 216   Real i = intersection_x (other);
 217   return (i <= x && slope_ > other.slope_)
 218          || (i > x && slope_ < other.slope_);
 219 }
 220
 221 // Remove redundant empty buildings from the skyline.
 222 // If there are two adjacent empty buildings, they can be
 223 // turned into one.
 224 void
 225 Skyline::normalize ()
 226 {
 227   bool last_empty = false;
 228   list<Building>::iterator i;
 229
 230   for (i = buildings_.begin (); i != buildings_.end (); i++)
 231     {
 232       if (last_empty && i->y_intercept_ == -infinity_f)
 233         {
 234           list<Building>::iterator last = i;
 235           last--;
 236           last->end_ = i->end_;
 237           buildings_.erase (i);
 238           i = last;
 239         }
 240       last_empty = (i->y_intercept_ == -infinity_f);
 241     }
 242
 243   assert (buildings_.front ().start_ == -infinity_f);
 244   assert (buildings_.back ().end_ == infinity_f);
 245 }
 246
 247 void
 248 Skyline::deholify ()
 249 {
 250   // Since a skyline should always be normalized, we can
 251   // assume that there are never two adjacent empty buildings.
 252   // That is, if center is empty then left and right are not.
 253   list<Building>::iterator left = buildings_.begin ();
 254   list<Building>::iterator center = buildings_.begin ();
 255   list<Building>::iterator right;
 256
 257   for (right = buildings_.begin (); right != buildings_.end (); right++)
 258     {
 259       if (center != buildings_.begin () && center->y_intercept_ == -infinity_f)
 260         {
 261           Real p1 = left->height (left->end_);
 262           Real p2 = right->height (right->start_);
 263           *center = Building (center->start_, p1, p2, center->end_);
 264
 265           left = center;
 266           center = right;
 267         }
 268     }
 269 }
 270
 271 void
 272 Skyline::internal_merge_skyline (list<Building> *s1, list<Building> *s2,
 273                                  list<Building> *const result) const
 274 {
 275   if (s1->empty () || s2->empty ())
 276     {
 277       programming_error ("tried to merge an empty skyline");
 278       return;
 279     }
 280
 281   Real x = -infinity_f;
 282   Real last_end = -infinity_f;
 283   while (!s1->empty ())
 284     {
 285       if (s2->front ().conceals (s1->front (), x))
 286         swap (s1, s2);
 287
 288       Building b = s1->front ();
 289       Building c = s2->front ();
 290
 291       // Optimization: if the other skyline is empty at this point,
 292       // we can avoid testing some intersections. Just grab as many
 293       // buildings from s1 as we can, and shove them onto the output.
 294       if (c.y_intercept_ == -infinity_f
 295           && c.end_ >= b.end_)
 296         {
 297           list<Building>::iterator i = s1->begin ();
 298           i++;
 299           while (i != s1->end () && i->end_ <= c.end_)
 300             i++;
 301
 302           s1->front ().start_ = x;
 303           result->splice (result->end (), *s1, s1->begin (), i);
 304           x = result->back ().end_;
 305           last_end = x;
 306           continue;
 307         }
 308
 309       Real end = first_intersection (b, s2, x);
 310       if (s2->empty ())
 311         {
 312           b.start_ = last_end;
 313           result->push_back (b);
 314           break;
 315         }
 316
 317       if (end >= x)
 318         {
 319           b.leading_part (end);
 320           b.start_ = last_end;
 321           last_end = b.end_;
 322           result->push_back (b);
 323         }
 324
 325       if (end >= s1->front ().end_)
 326         s1->pop_front ();
 327
 328       x = end;
 329     }
 330 }
 331
 332 static void
 333 empty_skyline (list<Building> *const ret)
 334 {
 335   ret->push_front (Building (-infinity_f, -infinity_f, -infinity_f, infinity_f));
 336 }
 337
 338 /*
 339   Given Building 'b', build a skyline containing only that building.
 340 */
 341 static void
 342 single_skyline (Building b, list<Building> *const ret)
 343 {
 344   assert (b.end_ >= b.start_);
 345
 346   if (b.start_ != -infinity_f)
 347     ret->push_back (Building (-infinity_f, -infinity_f,
 348                               -infinity_f, b.start_));
 349   ret->push_back (b);
 350   if (b.end_ != infinity_f)
 351     ret->push_back (Building (b.end_, -infinity_f,
 352                               -infinity_f, infinity_f));
 353 }
 354
 355 /* remove a non-overlapping set of boxes from BOXES and build a skyline
 356    out of them */
 357 static list<Building>
 358 non_overlapping_skyline (list<Building> *const buildings)
 359 {
 360   list<Building> result;
 361   Real last_end = -infinity_f;
 362   Building last_building (-infinity_f, -infinity_f, -infinity_f, infinity_f);
 363   list<Building>::iterator i = buildings->begin ();
 364   while (i != buildings->end ())
 365     {
 366       Real x1 = i->start_;
 367       Real y1 = i->height (i->start_);
 368       Real x2 = i->end_;
 369       Real y2 = i->height (i->end_);
 370
 371       // Drop buildings that will obviously have no effect.
 372       if (last_building.height (x1) >= y1
 373           && last_building.end_ >= x2
 374           && last_building.height (x2) >= y2)
 375         {
 376           list<Building>::iterator j = i++;
 377           buildings->erase (j);
 378           continue;
 379         }
 380
 381       if (x1 < last_end)
 382         {
 383           i++;
 384           continue;
 385         }
 386
 387       // Insert empty Buildings into any gaps. (TODO: is this needed? -KOH)
 388       if (x1 > last_end)
 389         result.push_back (Building (last_end, -infinity_f, -infinity_f, x1));
 390
 391       result.push_back (*i);
 392       last_building = *i;
 393       last_end = i->end_;
 394
 395       list<Building>::iterator j = i++;
 396       buildings->erase (j);
 397     }
 398
 399   if (last_end < infinity_f)
 400     result.push_back (Building (last_end, -infinity_f, -infinity_f, infinity_f));
 401   return result;
 402 }
 403
 404 class LessThanBuilding
 405 {
 406 public:
 407   bool operator () (Building const &b1, Building const &b2)
 408   {
 409     return b1.start_ < b2.start_
 410            || (b1.start_ == b2.start_ && b1.height (b1.start_) > b2.height (b1.start_));
 411   }
 412 };
 413
 414 /**
 415    BUILDINGS is a list of buildings, but they could be overlapping
 416    and in any order.  The returned list of buildings is ordered and non-overlapping.
 417 */
 418 list<Building>
 419 Skyline::internal_build_skyline (list<Building> *buildings) const
 420 {
 421   vsize size = buildings->size ();
 422
 423   if (size == 0)
 424     {
 425       list<Building> result;
 426       empty_skyline (&result);
 427       return result;
 428     }
 429   else if (size == 1)
 430     {
 431       list<Building> result;
 432       single_skyline (buildings->front (), &result);
 433       return result;
 434     }
 435
 436   deque<list<Building> > partials;
 437   buildings->sort (LessThanBuilding ());
 438   while (!buildings->empty ())
 439     partials.push_back (non_overlapping_skyline (buildings));
 440
 441   /* we'd like to say while (partials->size () > 1) but that's O (n).
 442      Instead, we exit in the middle of the loop */
 443   while (!partials.empty ())
 444     {
 445       list<Building> merged;
 446       list<Building> one = partials.front ();
 447       partials.pop_front ();
 448       if (partials.empty ())
 449         return one;
 450
 451       list<Building> two = partials.front ();
 452       partials.pop_front ();
 453       internal_merge_skyline (&one, &two, &merged);
 454       partials.push_back (merged);
 455     }
 456   assert (0);
 457   return list<Building> ();
 458 }
 459
 460 Skyline::Skyline ()
 461 {
 462   sky_ = UP;
 463   empty_skyline (&buildings_);
 464 }
 465
 466 Skyline::Skyline (Direction sky)
 467 {
 468   sky_ = sky;
 469   empty_skyline (&buildings_);
 470 }
 471
 472 /*
 473   Build skyline from a set of boxes.
 474
 475   Boxes should be non-empty on both axes.  Otherwise, they will be ignored
 476  */
 477 Skyline::Skyline (vector<Box> const &boxes, Axis horizon_axis, Direction sky)
 478 {
 479   list<Building> buildings;
 480   sky_ = sky;
 481
 482   for (vsize i = 0; i < boxes.size (); i++)
 483     if (!boxes[i].is_empty (X_AXIS)
 484         && !boxes[i].is_empty (Y_AXIS))
 485       buildings.push_front (Building (boxes[i], horizon_axis, sky));
 486
 487   buildings_ = internal_build_skyline (&buildings);
 488   normalize ();
 489 }
 490
 491 /*
 492   build skyline from a set of line segments.
 493
 494   Segments can be articulated from left to right or right to left.
 495   In the case of the latter, they will be stored internally as left to right.
 496  */
 497 Skyline::Skyline (vector<Drul_array<Offset> > const &segments, Axis horizon_axis, Direction sky)
 498 {
 499   list<Building> buildings;
 500   sky_ = sky;
 501
 502   for (vsize i = 0; i < segments.size (); i++)
 503     {
 504       Drul_array<Offset> const &seg = segments[i];
 505       Offset left = seg[LEFT];
 506       Offset right = seg[RIGHT];
 507       if (left[horizon_axis] > right[horizon_axis])
 508         swap (left, right);
 509
 510       Real x1 = left[horizon_axis];
 511       Real x2 = right[horizon_axis];
 512       Real y1 = left[other_axis (horizon_axis)] * sky;
 513       Real y2 = right[other_axis (horizon_axis)] * sky;
 514
 515       if (x1 <= x2)
 516         buildings.push_back (Building (x1, y1, y2, x2));
 517     }
 518
 519   buildings_ = internal_build_skyline (&buildings);
 520   normalize ();
 521 }
 522
 523 Skyline::Skyline (vector<Skyline_pair> const &skypairs, Direction sky)
 524 {
 525   sky_ = sky;
 526
 527   deque<Skyline> partials;
 528   for (vsize i = 0; i < skypairs.size (); i++)
 529     partials.push_back (Skyline ((skypairs[i])[sky]));
 530
 531   while (partials.size () > 1)
 532     {
 533       Skyline one = partials.front ();
 534       partials.pop_front ();
 535       Skyline two = partials.front ();
 536       partials.pop_front ();
 537
 538       one.merge (two);
 539       partials.push_back (one);
 540     }
 541
 542   if (partials.size ())
 543     buildings_.swap (partials.front ().buildings_);
 544   else
 545     buildings_.clear ();
 546 }
 547
 548 Skyline::Skyline (Box const &b, Axis horizon_axis, Direction sky)
 549 {
 550   sky_ = sky;
 551   if (!b.is_empty (X_AXIS) && !b.is_empty (Y_AXIS))
 552     {
 553       Building front (b, horizon_axis, sky);
 554       single_skyline (front, &buildings_);
 555       normalize ();
 556     }
 557 }
 558
 559 void
 560 Skyline::merge (Skyline const &other)
 561 {
 562   assert (sky_ == other.sky_);
 563
 564   if (other.is_empty ())
 565     return;
 566
 567   if (is_empty ())
 568     {
 569       buildings_ = other.buildings_;
 570       return;
 571     }
 572
 573   list<Building> other_bld (other.buildings_);
 574   list<Building> my_bld;
 575   my_bld.splice (my_bld.begin (), buildings_);
 576   internal_merge_skyline (&other_bld, &my_bld, &buildings_);
 577   normalize ();
 578 }
 579
 580 void
 581 Skyline::insert (Box const &b, Axis a)
 582 {
 583   list<Building> other_bld;
 584   list<Building> my_bld;
 585
 586   if (isnan (b[other_axis (a)][LEFT])
 587       || isnan (b[other_axis (a)][RIGHT]))
 588     {
 589       programming_error ("insane box for skyline");
 590       return;
 591     }
 592
 593   /* do the same filtering as in Skyline (vector<Box> const&, etc.) */
 594   if (b.is_empty (X_AXIS) || b.is_empty (Y_AXIS))
 595     return;
 596
 597   my_bld.splice (my_bld.begin (), buildings_);
 598   single_skyline (Building (b, a, sky_), &other_bld);
 599   internal_merge_skyline (&other_bld, &my_bld, &buildings_);
 600   normalize ();
 601 }
 602
 603 void
 604 Skyline::raise (Real r)
 605 {
 606   list<Building>::iterator end = buildings_.end ();
 607   for (list<Building>::iterator i = buildings_.begin (); i != end; i++)
 608     i->y_intercept_ += sky_ * r;
 609 }
 610
 611 void
 612 Skyline::shift (Real s)
 613 {
 614   list<Building>::iterator end = buildings_.end ();
 615   for (list<Building>::iterator i = buildings_.begin (); i != end; i++)
 616     {
 617       i->start_ += s;
 618       i->end_ += s;
 619       i->y_intercept_ -= s * i->slope_;
 620     }
 621 }
 622
 623 Real
 624 Skyline::distance (Skyline const &other, Real horizon_padding) const
 625 {
 626   Real dummy;
 627   return internal_distance (other, horizon_padding, &dummy);
 628 }
 629
 630 Real
 631 Skyline::touching_point (Skyline const &other, Real horizon_padding) const
 632 {
 633   Real touch;
 634   internal_distance (other, horizon_padding, &touch);
 635   return touch;
 636 }
 637
 638 Real
 639 Skyline::internal_distance (Skyline const &other, Real horizon_padding, Real *touch_point) const
 640 {
 641   if (horizon_padding == 0.0)
 642     return internal_distance (other, touch_point);
 643
 644   // Note that it is not necessary to build a padded version of other,
 645   // because the same effect can be achieved just by doubling horizon_padding.
 646   Skyline padded_this = padded (horizon_padding);
 647   return padded_this.internal_distance (other, touch_point);
 648 }
 649
 650 Skyline
 651 Skyline::padded (Real horizon_padding) const
 652 {
 653   if (horizon_padding < 0.0)
 654     warning ("Cannot have negative horizon padding.  Junking.");
 655
 656   if (horizon_padding <= 0.0)
 657     return *this;
 658
 659   list<Building> pad_buildings;
 660   for (list<Building>::const_iterator i = buildings_.begin (); i != buildings_.end (); ++i)
 661     {
 662       if (i->start_ > -infinity_f)
 663         {
 664           Real height = i->height (i->start_);
 665           if (height > -infinity_f)
 666             {
 667               // Add the sloped building that pads the left side of the current building.
 668               Real start = i->start_ - 2 * horizon_padding;
 669               Real end = i->start_ - horizon_padding;
 670               pad_buildings.push_back (Building (start, height - horizon_padding, height, end));
 671
 672               // Add the flat building that pads the left side of the current building.
 673               start = i->start_ - horizon_padding;
 674               end = i->start_;
 675               pad_buildings.push_back (Building (start, height, height, end));
 676             }
 677         }
 678
 679       if (i->end_ < infinity_f)
 680         {
 681           Real height = i->height (i->end_);
 682           if (height > -infinity_f)
 683             {
 684               // Add the flat building that pads the right side of the current building.
 685               Real start = i->end_;
 686               Real end = start + horizon_padding;
 687               pad_buildings.push_back (Building (start, height, height, end));
 688
 689               // Add the sloped building that pads the right side of the current building.
 690               start = end;
 691               end += horizon_padding;
 692               pad_buildings.push_back (Building (start, height, height - horizon_padding, end));
 693             }
 694         }
 695     }
 696
 697   // The buildings may be overlapping, so resolve that.
 698   list<Building> pad_skyline = internal_build_skyline (&pad_buildings);
 699
 700   // Merge the padding with the original, to make a new skyline.
 701   Skyline padded (sky_);
 702   list<Building> my_buildings = buildings_;
 703   padded.buildings_.clear ();
 704   internal_merge_skyline (&pad_skyline, &my_buildings, &padded.buildings_);
 705   padded.normalize ();
 706
 707   return padded;
 708 }
 709
 710 Real
 711 Skyline::internal_distance (Skyline const &other, Real *touch_point) const
 712 {
 713   assert (sky_ == -other.sky_);
 714
 715   list<Building>::const_iterator i = buildings_.begin ();
 716   list<Building>::const_iterator j = other.buildings_.begin ();
 717
 718   Real dist = -infinity_f;
 719   Real start = -infinity_f;
 720   Real touch = -infinity_f;
 721   while (i != buildings_.end () && j != other.buildings_.end ())
 722     {
 723       Real end = min (i->end_, j->end_);
 724       Real start_dist = i->height (start) + j->height (start);
 725       Real end_dist = i->height (end) + j->height (end);
 726       dist = max (dist, max (start_dist, end_dist));
 727
 728       if (end_dist == dist)
 729         touch = end;
 730       else if (start_dist == dist)
 731         touch = start;
 732
 733       if (i->end_ <= j->end_)
 734         i++;
 735       else
 736         j++;
 737       start = end;
 738     }
 739
 740   *touch_point = touch;
 741   return dist;
 742 }
 743
 744 Real
 745 Skyline::height (Real airplane) const
 746 {
 747   assert (!isinf (airplane));
 748
 749   list<Building>::const_iterator i;
 750   for (i = buildings_.begin (); i != buildings_.end (); i++)
 751     {
 752       if (i->end_ >= airplane)
 753         return sky_ * i->height (airplane);
 754     }
 755
 756   assert (0);
 757   return 0;
 758 }
 759
 760 Real
 761 Skyline::max_height () const
 762 {
 763   Real ret = -infinity_f;
 764
 765   list<Building>::const_iterator i;
 766   for (i = buildings_.begin (); i != buildings_.end (); ++i)
 767     {
 768       ret = max (ret, i->height (i->start_));
 769       ret = max (ret, i->height (i->end_));
 770     }
 771
 772   return sky_ * ret;
 773 }
 774
 775 Direction
 776 Skyline::direction () const
 777 {
 778   return sky_;
 779 }
 780
 781 Real
 782 Skyline::left () const
 783 {
 784   for (list<Building>::const_iterator i (buildings_.begin ());
 785        i != buildings_.end (); i++)
 786     if (i->y_intercept_ > -infinity_f)
 787       return i->start_;
 788
 789   return infinity_f;
 790 }
 791
 792 Real
 793 Skyline::right () const
 794 {
 795   for (list<Building>::const_reverse_iterator i (buildings_.rbegin ());
 796        i != buildings_.rend (); ++i)
 797     if (i->y_intercept_ > -infinity_f)
 798       return i->end_;
 799
 800   return -infinity_f;
 801 }
 802
 803 Real
 804 Skyline::max_height_position () const
 805 {
 806   Skyline s (-sky_);
 807   s.set_minimum_height (0);
 808   return touching_point (s);
 809 }
 810
 811 void
 812 Skyline::set_minimum_height (Real h)
 813 {
 814   Skyline s (sky_);
 815   s.buildings_.front ().y_intercept_ = h * sky_;
 816   merge (s);
 817 }
 818
 819 vector<Offset>
 820 Skyline::to_points (Axis horizon_axis) const
 821 {
 822   vector<Offset> out;
 823
 824   Real start = -infinity_f;
 825   for (list<Building>::const_iterator i (buildings_.begin ());
 826        i != buildings_.end (); i++)
 827     {
 828       out.push_back (Offset (start, sky_ * i->height (start)));
 829       out.push_back (Offset (i->end_, sky_ * i->height (i->end_)));
 830       start = i->end_;
 831     }
 832
 833   if (horizon_axis == Y_AXIS)
 834     for (vsize i = 0; i < out.size (); i++)
 835       out[i] = out[i].swapped ();
 836
 837   return out;
 838 }
 839
 840 bool
 841 Skyline::is_empty () const
 842 {
 843   if (!buildings_.size ())
 844     return true;
 845   Building b = buildings_.front ();
 846   return b.end_ == infinity_f && b.y_intercept_ == -infinity_f;
 847 }
 848
 849 void
 850 Skyline::clear ()
 851 {
 852   buildings_.clear ();
 853   empty_skyline (&buildings_);
 854 }
 855
 856 /****************************************************************/
 857
 858 IMPLEMENT_SIMPLE_SMOBS (Skyline);
 859 IMPLEMENT_TYPE_P (Skyline, "ly:skyline?");
 860 IMPLEMENT_DEFAULT_EQUAL_P (Skyline);
 861
 862 SCM
 863 Skyline::mark_smob (SCM s)
 864 {
 865   ASSERT_LIVE_IS_ALLOWED (s);
 866   return SCM_EOL;
 867 }
 868
 869 int
 870 Skyline::print_smob (SCM s, SCM port, scm_print_state *)
 871 {
 872   Skyline *r = (Skyline *) SCM_CELL_WORD_1 (s);
 873   (void) r;
 874
 875   scm_puts ("#<Skyline>", port);
 876
 877   return 1;
 878 }
 879
 880 MAKE_SCHEME_CALLBACK_WITH_OPTARGS (Skyline, get_touching_point, 3, 1, "")
 881 SCM
 882 Skyline::get_touching_point (SCM skyline_scm, SCM other_skyline_scm, SCM horizon_padding_scm)
 883 {
 884   LY_ASSERT_SMOB (Skyline, other_skyline_scm, 1);
 885
 886   Real horizon_padding = 0;
 887   if (horizon_padding_scm != SCM_UNDEFINED)
 888     {
 889       LY_ASSERT_TYPE (scm_is_number, horizon_padding_scm, 3);
 890       horizon_padding = scm_to_double (horizon_padding_scm);
 891     }
 892
 893   Skyline *skyline = Skyline::unsmob (skyline_scm);
 894   Skyline *other_skyline = Skyline::unsmob (other_skyline_scm);
 895   return scm_from_double (skyline->touching_point (*other_skyline, horizon_padding));
 896 }
 897
 898 MAKE_SCHEME_CALLBACK_WITH_OPTARGS (Skyline, get_distance, 3, 1, "")
 899 SCM
 900 Skyline::get_distance (SCM skyline_scm, SCM other_skyline_scm, SCM horizon_padding_scm)
 901 {
 902   LY_ASSERT_SMOB (Skyline, other_skyline_scm, 1);
 903
 904   Real horizon_padding = 0;
 905   if (horizon_padding_scm != SCM_UNDEFINED)
 906     {
 907       LY_ASSERT_TYPE (scm_is_number, horizon_padding_scm, 3);
 908       horizon_padding = scm_to_double (horizon_padding_scm);
 909     }
 910
 911   Skyline *skyline = Skyline::unsmob (skyline_scm);
 912   Skyline *other_skyline = Skyline::unsmob (other_skyline_scm);
 913   return scm_from_double (skyline->distance (*other_skyline, horizon_padding));
 914 }
 915
 916 MAKE_SCHEME_CALLBACK (Skyline, get_max_height, 1)
 917 SCM
 918 Skyline::get_max_height (SCM skyline_scm)
 919 {
 920   return scm_from_double (Skyline::unsmob (skyline_scm)->max_height ());
 921 }
 922
 923 MAKE_SCHEME_CALLBACK (Skyline, get_max_height_position, 1)
 924 SCM
 925 Skyline::get_max_height_position (SCM skyline_scm)
 926 {
 927   return scm_from_double (Skyline::unsmob (skyline_scm)->max_height_position ());
 928 }
 929
 930 MAKE_SCHEME_CALLBACK (Skyline, get_height, 2)
 931 SCM
 932 Skyline::get_height (SCM skyline_scm, SCM x_scm)
 933 {
 934   Real x = robust_scm2double (x_scm, 0.0);
 935   return scm_from_double (Skyline::unsmob (skyline_scm)->height (x));
 936 }
 937
 938 LY_DEFINE (ly_skyline_empty_p, "ly:skyline-empty?",
 939            1, 0, 0, (SCM sky),
 940            "Return whether @var{sky} is empty.")
 941 {
 942   Skyline *s = Skyline::unsmob (sky);
 943   LY_ASSERT_SMOB (Skyline, sky, 1);
 944   return scm_from_bool (s->is_empty ());
 945 }