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 (Direction sky)
 461 {
 462   sky_ = sky;
 463   empty_skyline (&buildings_);
 464 }
 465
 466 /*
 467   Build skyline from a set of boxes.
 468
 469   Boxes should be non-empty on both axes.  Otherwise, they will be ignored
 470  */
 471 Skyline::Skyline (vector<Box> const &boxes, Axis horizon_axis, Direction sky)
 472 {
 473   list<Building> buildings;
 474   sky_ = sky;
 475
 476   for (vsize i = 0; i < boxes.size (); i++)
 477     if (!boxes[i].is_empty (X_AXIS)
 478         && !boxes[i].is_empty (Y_AXIS))
 479       buildings.push_front (Building (boxes[i], horizon_axis, sky));
 480
 481   buildings_ = internal_build_skyline (&buildings);
 482   normalize ();
 483 }
 484
 485 /*
 486   build skyline from a set of line segments.
 487
 488   Segments can be articulated from left to right or right to left.
 489   In the case of the latter, they will be stored internally as left to right.
 490  */
 491 Skyline::Skyline (vector<Drul_array<Offset> > const &segments, Axis horizon_axis, Direction sky)
 492 {
 493   list<Building> buildings;
 494   sky_ = sky;
 495
 496   for (vsize i = 0; i < segments.size (); i++)
 497     {
 498       Drul_array<Offset> const &seg = segments[i];
 499       Offset left = seg[LEFT];
 500       Offset right = seg[RIGHT];
 501       if (left[horizon_axis] > right[horizon_axis])
 502         swap (left, right);
 503
 504       Real x1 = left[horizon_axis];
 505       Real x2 = right[horizon_axis];
 506       Real y1 = left[other_axis (horizon_axis)] * sky;
 507       Real y2 = right[other_axis (horizon_axis)] * sky;
 508
 509       if (x1 <= x2)
 510         buildings.push_back (Building (x1, y1, y2, x2));
 511     }
 512
 513   buildings_ = internal_build_skyline (&buildings);
 514   normalize ();
 515 }
 516
 517 Skyline::Skyline (vector<Skyline_pair> const &skypairs, Direction sky)
 518 {
 519   sky_ = sky;
 520
 521   deque<Skyline> partials;
 522   for (vsize i = 0; i < skypairs.size (); i++)
 523     partials.push_back (Skyline ((skypairs[i])[sky]));
 524
 525   while (partials.size () > 1)
 526     {
 527       Skyline one = partials.front ();
 528       partials.pop_front ();
 529       Skyline two = partials.front ();
 530       partials.pop_front ();
 531
 532       one.merge (two);
 533       partials.push_back (one);
 534     }
 535
 536   if (partials.size ())
 537     buildings_.swap (partials.front ().buildings_);
 538   else
 539     buildings_.clear ();
 540 }
 541
 542 Skyline::Skyline (Box const &b, Axis horizon_axis, Direction sky)
 543 {
 544   sky_ = sky;
 545   if (!b.is_empty (X_AXIS) && !b.is_empty (Y_AXIS))
 546     {
 547       Building front (b, horizon_axis, sky);
 548       single_skyline (front, &buildings_);
 549       normalize ();
 550     }
 551 }
 552
 553 void
 554 Skyline::merge (Skyline const &other)
 555 {
 556   assert (sky_ == other.sky_);
 557
 558   if (other.is_empty ())
 559     return;
 560
 561   if (is_empty ())
 562     {
 563       buildings_ = other.buildings_;
 564       return;
 565     }
 566
 567   list<Building> other_bld (other.buildings_);
 568   list<Building> my_bld;
 569   my_bld.splice (my_bld.begin (), buildings_);
 570   internal_merge_skyline (&other_bld, &my_bld, &buildings_);
 571   normalize ();
 572 }
 573
 574 void
 575 Skyline::insert (Box const &b, Axis a)
 576 {
 577   list<Building> other_bld;
 578   list<Building> my_bld;
 579
 580   if (isnan (b[other_axis (a)][LEFT])
 581       || isnan (b[other_axis (a)][RIGHT]))
 582     {
 583       programming_error ("insane box for skyline");
 584       return;
 585     }
 586
 587   /* do the same filtering as in Skyline (vector<Box> const&, etc.) */
 588   if (b.is_empty (X_AXIS) || b.is_empty (Y_AXIS))
 589     return;
 590
 591   my_bld.splice (my_bld.begin (), buildings_);
 592   single_skyline (Building (b, a, sky_), &other_bld);
 593   internal_merge_skyline (&other_bld, &my_bld, &buildings_);
 594   normalize ();
 595 }
 596
 597 void
 598 Skyline::raise (Real r)
 599 {
 600   list<Building>::iterator end = buildings_.end ();
 601   for (list<Building>::iterator i = buildings_.begin (); i != end; i++)
 602     i->y_intercept_ += sky_ * r;
 603 }
 604
 605 void
 606 Skyline::shift (Real s)
 607 {
 608   list<Building>::iterator end = buildings_.end ();
 609   for (list<Building>::iterator i = buildings_.begin (); i != end; i++)
 610     {
 611       i->start_ += s;
 612       i->end_ += s;
 613       i->y_intercept_ -= s * i->slope_;
 614     }
 615 }
 616
 617 Real
 618 Skyline::distance (Skyline const &other, Real horizon_padding) const
 619 {
 620   Real dummy;
 621   return internal_distance (other, horizon_padding, &dummy);
 622 }
 623
 624 Real
 625 Skyline::touching_point (Skyline const &other, Real horizon_padding) const
 626 {
 627   Real touch;
 628   internal_distance (other, horizon_padding, &touch);
 629   return touch;
 630 }
 631
 632 Real
 633 Skyline::internal_distance (Skyline const &other, Real horizon_padding, Real *touch_point) const
 634 {
 635   if (horizon_padding == 0.0)
 636     return internal_distance (other, touch_point);
 637
 638   // Note that it is not necessary to build a padded version of other,
 639   // because the same effect can be achieved just by doubling horizon_padding.
 640   Skyline padded_this = padded (horizon_padding);
 641   return padded_this.internal_distance (other, touch_point);
 642 }
 643
 644 Skyline
 645 Skyline::padded (Real horizon_padding) const
 646 {
 647   if (horizon_padding < 0.0)
 648     warning ("Cannot have negative horizon padding.  Junking.");
 649
 650   if (horizon_padding <= 0.0)
 651     return *this;
 652
 653   list<Building> pad_buildings;
 654   for (list<Building>::const_iterator i = buildings_.begin (); i != buildings_.end (); ++i)
 655     {
 656       if (i->start_ > -infinity_f)
 657         {
 658           Real height = i->height (i->start_);
 659           if (height > -infinity_f)
 660             {
 661               // Add the sloped building that pads the left side of the current building.
 662               Real start = i->start_ - 2 * horizon_padding;
 663               Real end = i->start_ - horizon_padding;
 664               pad_buildings.push_back (Building (start, height - horizon_padding, height, end));
 665
 666               // Add the flat building that pads the left side of the current building.
 667               start = i->start_ - horizon_padding;
 668               end = i->start_;
 669               pad_buildings.push_back (Building (start, height, height, end));
 670             }
 671         }
 672
 673       if (i->end_ < infinity_f)
 674         {
 675           Real height = i->height (i->end_);
 676           if (height > -infinity_f)
 677             {
 678               // Add the flat building that pads the right side of the current building.
 679               Real start = i->end_;
 680               Real end = start + horizon_padding;
 681               pad_buildings.push_back (Building (start, height, height, end));
 682
 683               // Add the sloped building that pads the right side of the current building.
 684               start = end;
 685               end += horizon_padding;
 686               pad_buildings.push_back (Building (start, height, height - horizon_padding, end));
 687             }
 688         }
 689     }
 690
 691   // The buildings may be overlapping, so resolve that.
 692   list<Building> pad_skyline = internal_build_skyline (&pad_buildings);
 693
 694   // Merge the padding with the original, to make a new skyline.
 695   Skyline padded (sky_);
 696   list<Building> my_buildings = buildings_;
 697   padded.buildings_.clear ();
 698   internal_merge_skyline (&pad_skyline, &my_buildings, &padded.buildings_);
 699   padded.normalize ();
 700
 701   return padded;
 702 }
 703
 704 Real
 705 Skyline::internal_distance (Skyline const &other, Real *touch_point) const
 706 {
 707   assert (sky_ == -other.sky_);
 708
 709   list<Building>::const_iterator i = buildings_.begin ();
 710   list<Building>::const_iterator j = other.buildings_.begin ();
 711
 712   Real dist = -infinity_f;
 713   Real start = -infinity_f;
 714   Real touch = -infinity_f;
 715   while (i != buildings_.end () && j != other.buildings_.end ())
 716     {
 717       Real end = min (i->end_, j->end_);
 718       Real start_dist = i->height (start) + j->height (start);
 719       Real end_dist = i->height (end) + j->height (end);
 720       dist = max (dist, max (start_dist, end_dist));
 721
 722       if (end_dist == dist)
 723         touch = end;
 724       else if (start_dist == dist)
 725         touch = start;
 726
 727       if (i->end_ <= j->end_)
 728         i++;
 729       else
 730         j++;
 731       start = end;
 732     }
 733
 734   *touch_point = touch;
 735   return dist;
 736 }
 737
 738 Real
 739 Skyline::height (Real airplane) const
 740 {
 741   assert (!isinf (airplane));
 742
 743   list<Building>::const_iterator i;
 744   for (i = buildings_.begin (); i != buildings_.end (); i++)
 745     {
 746       if (i->end_ >= airplane)
 747         return sky_ * i->height (airplane);
 748     }
 749
 750   assert (0);
 751   return 0;
 752 }
 753
 754 Real
 755 Skyline::max_height () const
 756 {
 757   Real ret = -infinity_f;
 758
 759   list<Building>::const_iterator i;
 760   for (i = buildings_.begin (); i != buildings_.end (); ++i)
 761     {
 762       ret = max (ret, i->height (i->start_));
 763       ret = max (ret, i->height (i->end_));
 764     }
 765
 766   return sky_ * ret;
 767 }
 768
 769 Direction
 770 Skyline::direction () const
 771 {
 772   return sky_;
 773 }
 774
 775 Real
 776 Skyline::left () const
 777 {
 778   for (list<Building>::const_iterator i (buildings_.begin ());
 779        i != buildings_.end (); i++)
 780     if (i->y_intercept_ > -infinity_f)
 781       return i->start_;
 782
 783   return infinity_f;
 784 }
 785
 786 Real
 787 Skyline::right () const
 788 {
 789   for (list<Building>::const_reverse_iterator i (buildings_.rbegin ());
 790        i != buildings_.rend (); ++i)
 791     if (i->y_intercept_ > -infinity_f)
 792       return i->end_;
 793
 794   return -infinity_f;
 795 }
 796
 797 Real
 798 Skyline::max_height_position () const
 799 {
 800   Skyline s (-sky_);
 801   s.set_minimum_height (0);
 802   return touching_point (s);
 803 }
 804
 805 void
 806 Skyline::set_minimum_height (Real h)
 807 {
 808   Skyline s (sky_);
 809   s.buildings_.front ().y_intercept_ = h * sky_;
 810   merge (s);
 811 }
 812
 813 vector<Offset>
 814 Skyline::to_points (Axis horizon_axis) const
 815 {
 816   vector<Offset> out;
 817
 818   Real start = -infinity_f;
 819   for (list<Building>::const_iterator i (buildings_.begin ());
 820        i != buildings_.end (); i++)
 821     {
 822       out.push_back (Offset (start, sky_ * i->height (start)));
 823       out.push_back (Offset (i->end_, sky_ * i->height (i->end_)));
 824       start = i->end_;
 825     }
 826
 827   if (horizon_axis == Y_AXIS)
 828     for (vsize i = 0; i < out.size (); i++)
 829       out[i] = out[i].swapped ();
 830
 831   return out;
 832 }
 833
 834 bool
 835 Skyline::is_empty () const
 836 {
 837   if (!buildings_.size ())
 838     return true;
 839   Building b = buildings_.front ();
 840   return b.end_ == infinity_f && b.y_intercept_ == -infinity_f;
 841 }
 842
 843 void
 844 Skyline::clear ()
 845 {
 846   buildings_.clear ();
 847   empty_skyline (&buildings_);
 848 }
 849
 850 /****************************************************************/
 851
 852 IMPLEMENT_SIMPLE_SMOBS (Skyline);
 853 IMPLEMENT_TYPE_P (Skyline, "ly:skyline?");
 854 IMPLEMENT_DEFAULT_EQUAL_P (Skyline);
 855
 856 SCM
 857 Skyline::mark_smob (SCM s)
 858 {
 859   ASSERT_LIVE_IS_ALLOWED (s);
 860   return SCM_EOL;
 861 }
 862
 863 int
 864 Skyline::print_smob (SCM s, SCM port, scm_print_state *)
 865 {
 866   Skyline *r = (Skyline *) SCM_CELL_WORD_1 (s);
 867   (void) r;
 868
 869   scm_puts ("#<Skyline>", port);
 870
 871   return 1;
 872 }
 873
 874 MAKE_SCHEME_CALLBACK_WITH_OPTARGS (Skyline, get_touching_point, 3, 1, "")
 875 SCM
 876 Skyline::get_touching_point (SCM skyline_scm, SCM other_skyline_scm, SCM horizon_padding_scm)
 877 {
 878   LY_ASSERT_SMOB (Skyline, other_skyline_scm, 1);
 879
 880   Real horizon_padding = 0;
 881   if (horizon_padding_scm != SCM_UNDEFINED)
 882     {
 883       LY_ASSERT_TYPE (scm_is_number, horizon_padding_scm, 3);
 884       horizon_padding = scm_to_double (horizon_padding_scm);
 885     }
 886
 887   Skyline *skyline = Skyline::unsmob (skyline_scm);
 888   Skyline *other_skyline = Skyline::unsmob (other_skyline_scm);
 889   return scm_from_double (skyline->touching_point (*other_skyline, horizon_padding));
 890 }
 891
 892 MAKE_SCHEME_CALLBACK_WITH_OPTARGS (Skyline, get_distance, 3, 1, "")
 893 SCM
 894 Skyline::get_distance (SCM skyline_scm, SCM other_skyline_scm, SCM horizon_padding_scm)
 895 {
 896   LY_ASSERT_SMOB (Skyline, other_skyline_scm, 1);
 897
 898   Real horizon_padding = 0;
 899   if (horizon_padding_scm != SCM_UNDEFINED)
 900     {
 901       LY_ASSERT_TYPE (scm_is_number, horizon_padding_scm, 3);
 902       horizon_padding = scm_to_double (horizon_padding_scm);
 903     }
 904
 905   Skyline *skyline = Skyline::unsmob (skyline_scm);
 906   Skyline *other_skyline = Skyline::unsmob (other_skyline_scm);
 907   return scm_from_double (skyline->distance (*other_skyline, horizon_padding));
 908 }
 909
 910 MAKE_SCHEME_CALLBACK (Skyline, get_max_height, 1)
 911 SCM
 912 Skyline::get_max_height (SCM skyline_scm)
 913 {
 914   return scm_from_double (Skyline::unsmob (skyline_scm)->max_height ());
 915 }
 916
 917 MAKE_SCHEME_CALLBACK (Skyline, get_max_height_position, 1)
 918 SCM
 919 Skyline::get_max_height_position (SCM skyline_scm)
 920 {
 921   return scm_from_double (Skyline::unsmob (skyline_scm)->max_height_position ());
 922 }
 923
 924 MAKE_SCHEME_CALLBACK (Skyline, get_height, 2)
 925 SCM
 926 Skyline::get_height (SCM skyline_scm, SCM x_scm)
 927 {
 928   Real x = robust_scm2double (x_scm, 0.0);
 929   return scm_from_double (Skyline::unsmob (skyline_scm)->height (x));
 930 }
 931
 932 LY_DEFINE (ly_skyline_empty_p, "ly:skyline-empty?",
 933            1, 0, 0, (SCM sky),
 934            "Return whether @var{sky} is empty.")
 935 {
 936   Skyline *s = Skyline::unsmob (sky);
 937   LY_ASSERT_SMOB (Skyline, sky, 1);
 938   return scm_from_bool (s->is_empty ());
 939 }