lily/skyline.cc

   1 /*
   2   This file is part of LilyPond, the GNU music typesetter.
   3
   4   Copyright (C) 2006--2015 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 /* A skyline is a sequence of non-overlapping buildings: something like
  26    this:
  27                    _______
  28                   |       \                                 ________
  29                   |        \                       ________/        \
  30         /\        |          \                    /                  \
  31        /  --------             \                 /                    \
  32       /                          \              /                      \
  33      /                             ------------/                        ----
  34    --
  35    Each building has a starting position, and ending position, a starting
  36    height and an ending height.
  37
  38    The following invariants are observed:
  39     - the start of the first building is at -infinity
  40     - the end of the last building is at infinity
  41     - if a building has infinite length (ie. the first and last buildings),
  42       then its starting height and ending height are equal
  43     - the end of one building is the same as the beginning of the next
  44       building
  45
  46    We also allow skylines to point down (the structure is exactly the same,
  47    but we think of the part above the line as being filled with mass and the
  48    part below as being empty). ::distance finds the minimum distance between
  49    an UP skyline and a DOWN skyline.
  50
  51    Note that we store DOWN skylines upside-down. That is, in order to compare
  52    a DOWN skyline with an UP skyline, we need to flip the DOWN skyline first.
  53    This means that the merging routine doesn't need to be aware of direction,
  54    but the distance routine does.
  55
  56    From 2007 through 2012, buildings of width less than EPS were discarded,
  57    citing numerical accuracy concerns.  We remember that floating point
  58    comparisons of nearly-equal values can be affected by rounding error.
  59    Also, some target machines use the x87 floating point unit, which provides
  60    extended precision for intermediate results held in registers. On this type
  61    of hardware comparisons such as
  62      double c = 1.0/3.0; boolean compare = (c == 1.0/3.0)
  63    could go either way because the 1.0/3.0 is allowed to be kept
  64    higher precision than the variable 'c'.
  65    Alert to these considerations, we now accept buildings of zero-width.
  66 */
  67
  68 ADD_SMOB_INIT (Skyline);
  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 // Returns a shift s such that (x + s, y) intersects the roof of
 158 // this building.  If no such shift exists, returns infinity_f.
 159 Real
 160 Building::shift_to_intersect (Real x, Real y) const
 161 {
 162   // Solve for s: y = (x + s)*m + b
 163   Real ret = (y - y_intercept_ - slope_ * x) / slope_;
 164
 165   if (ret >= start_ && ret <= end_ && !isinf (ret))
 166     return ret;
 167   return infinity_f;
 168 }
 169
 170 bool
 171 Building::above (Building const &other, Real x) const
 172 {
 173   return (isinf (y_intercept_) || isinf (other.y_intercept_) || isinf (x))
 174          ? y_intercept_ > other.y_intercept_
 175          : (slope_ - other.slope_) * x + y_intercept_ > other.y_intercept_;
 176 }
 177
 178 // Remove redundant empty buildings from the skyline.
 179 // If there are two adjacent empty buildings, they can be
 180 // turned into one.
 181 void
 182 Skyline::normalize ()
 183 {
 184   bool last_empty = false;
 185   list<Building>::iterator i;
 186
 187   for (i = buildings_.begin (); i != buildings_.end (); i++)
 188     {
 189       if (last_empty && i->y_intercept_ == -infinity_f)
 190         {
 191           list<Building>::iterator last = i;
 192           last--;
 193           last->end_ = i->end_;
 194           buildings_.erase (i);
 195           i = last;
 196         }
 197       last_empty = (i->y_intercept_ == -infinity_f);
 198     }
 199
 200   assert (buildings_.front ().start_ == -infinity_f);
 201   assert (buildings_.back ().end_ == infinity_f);
 202 }
 203
 204 void
 205 Skyline::internal_merge_skyline (list<Building> *sb, list<Building> *sc,
 206                                  list<Building> *const result) const
 207 {
 208   if (sb->empty () || sc->empty ())
 209     {
 210       programming_error ("tried to merge an empty skyline");
 211       return;
 212     }
 213
 214   Building b = sb->front ();
 215   for (; !sc->empty (); sc->pop_front ())
 216     {
 217       /* Building b is continuing from the previous pass through the loop.
 218          Building c is newly-considered, and starts no earlier than b started.
 219          The comments draw b as if its roof had zero slope ----.
 220          with dashes where b lies above c.
 221          The roof of c could rise / or fall \ through the roof of b,
 222          or the vertical sides | of c could intersect the roof of b.  */
 223       Building c = sc->front ();
 224       if (b.end_ < c.end_) /* finish with b */
 225         {
 226           if (b.end_ <= b.start_) /* we are already finished with b */
 227             ;
 228           else if (c.above (b, c.start_)) /* -|   . | */
 229             {
 230               Building m (b);
 231               m.end_ = c.start_;
 232               if (m.end_ > m.start_)
 233                 result->push_back (m);
 234               if (b.above (c, b.end_))    /* -|\--.   */
 235                 {
 236                   Building n (c);
 237                   n.end_ = b.start_ = b.intersection_x (c);
 238                   result->push_back (n);
 239                   result->push_back (b);
 240                 }
 241             }
 242           else
 243             {
 244               if (c.above (b, b.end_))    /* ---/ . | */
 245                 b.end_ = b.intersection_x (c);
 246               else                        /* -----.   */
 247                 c.start_ = b.end_;
 248               result->push_back (b);
 249             }
 250           /* 'c' continues further, so move it into 'b' for the next pass. */
 251           b = c;
 252           swap (sb, sc);
 253         }
 254       else /* b.end_ > c.end_ so finish with c */
 255         {
 256           if (c.above (b, c.start_))    /* -| |---. */
 257             {
 258               Building m (b);
 259               m.end_ = c.start_;
 260               if (m.end_ > m.start_)
 261                 result->push_back (m);
 262               if (b.above (c, c.end_))  /* -| \---. */
 263                 c.end_ = b.intersection_x (c);
 264             }
 265           else if (c.above (b, c.end_)) /* ---/|--. */
 266             {
 267               Building m (b);
 268               c.start_ = m.end_ = b.intersection_x (c);
 269               result->push_back (m);
 270             }
 271           else  /* c is completely hidden by b */
 272             continue;
 273           result->push_back (c);
 274           b.start_ = c.end_;
 275         }
 276     }
 277   if (b.end_ > b.start_)
 278     result->push_back (b);
 279 }
 280
 281 static void
 282 empty_skyline (list<Building> *const ret)
 283 {
 284   ret->push_front (Building (-infinity_f, -infinity_f, -infinity_f, infinity_f));
 285 }
 286
 287 /*
 288   Given Building 'b', build a skyline containing only that building.
 289 */
 290 static void
 291 single_skyline (Building b, list<Building> *const ret)
 292 {
 293   assert (b.end_ >= b.start_);
 294
 295   if (b.start_ != -infinity_f)
 296     ret->push_back (Building (-infinity_f, -infinity_f,
 297                               -infinity_f, b.start_));
 298   ret->push_back (b);
 299   if (b.end_ != infinity_f)
 300     ret->push_back (Building (b.end_, -infinity_f,
 301                               -infinity_f, infinity_f));
 302 }
 303
 304 /* remove a non-overlapping set of boxes from BOXES and build a skyline
 305    out of them */
 306 static list<Building>
 307 non_overlapping_skyline (list<Building> *const buildings)
 308 {
 309   list<Building> result;
 310   Real last_end = -infinity_f;
 311   Building last_building (-infinity_f, -infinity_f, -infinity_f, infinity_f);
 312   list<Building>::iterator i = buildings->begin ();
 313   while (i != buildings->end ())
 314     {
 315       Real x1 = i->start_;
 316       Real y1 = i->height (i->start_);
 317       Real x2 = i->end_;
 318       Real y2 = i->height (i->end_);
 319
 320       // Drop buildings that will obviously have no effect.
 321       if (last_building.height (x1) >= y1
 322           && last_building.end_ >= x2
 323           && last_building.height (x2) >= y2)
 324         {
 325           list<Building>::iterator j = i++;
 326           buildings->erase (j);
 327           continue;
 328         }
 329
 330       if (x1 < last_end)
 331         {
 332           i++;
 333           continue;
 334         }
 335
 336       // Insert empty Buildings into any gaps. (TODO: is this needed? -KOH)
 337       if (x1 > last_end)
 338         result.push_back (Building (last_end, -infinity_f, -infinity_f, x1));
 339
 340       result.push_back (*i);
 341       last_building = *i;
 342       last_end = i->end_;
 343
 344       list<Building>::iterator j = i++;
 345       buildings->erase (j);
 346     }
 347
 348   if (last_end < infinity_f)
 349     result.push_back (Building (last_end, -infinity_f, -infinity_f, infinity_f));
 350   return result;
 351 }
 352
 353 class LessThanBuilding
 354 {
 355 public:
 356   bool operator () (Building const &b1, Building const &b2)
 357   {
 358     return b1.start_ < b2.start_
 359            || (b1.start_ == b2.start_ && b1.height (b1.start_) > b2.height (b1.start_));
 360   }
 361 };
 362
 363 /**
 364    BUILDINGS is a list of buildings, but they could be overlapping
 365    and in any order.  The returned list of buildings is ordered and non-overlapping.
 366 */
 367 list<Building>
 368 Skyline::internal_build_skyline (list<Building> *buildings) const
 369 {
 370   vsize size = buildings->size ();
 371
 372   if (size == 0)
 373     {
 374       list<Building> result;
 375       empty_skyline (&result);
 376       return result;
 377     }
 378   else if (size == 1)
 379     {
 380       list<Building> result;
 381       single_skyline (buildings->front (), &result);
 382       return result;
 383     }
 384
 385   deque<list<Building> > partials;
 386   buildings->sort (LessThanBuilding ());
 387   while (!buildings->empty ())
 388     partials.push_back (non_overlapping_skyline (buildings));
 389
 390   /* we'd like to say while (partials->size () > 1) but that's O (n).
 391      Instead, we exit in the middle of the loop */
 392   while (!partials.empty ())
 393     {
 394       list<Building> merged;
 395       list<Building> one = partials.front ();
 396       partials.pop_front ();
 397       if (partials.empty ())
 398         return one;
 399
 400       list<Building> two = partials.front ();
 401       partials.pop_front ();
 402       internal_merge_skyline (&one, &two, &merged);
 403       partials.push_back (merged);
 404     }
 405   assert (0);
 406   return list<Building> ();
 407 }
 408
 409 Skyline::Skyline ()
 410 {
 411   sky_ = UP;
 412   empty_skyline (&buildings_);
 413 }
 414
 415 Skyline::Skyline (Direction sky)
 416 {
 417   sky_ = sky;
 418   empty_skyline (&buildings_);
 419 }
 420
 421 /*
 422   Build skyline from a set of boxes.
 423
 424   Boxes should be non-empty on both axes.  Otherwise, they will be ignored
 425  */
 426 Skyline::Skyline (vector<Box> const &boxes, Axis horizon_axis, Direction sky)
 427 {
 428   list<Building> buildings;
 429   sky_ = sky;
 430
 431   for (vsize i = 0; i < boxes.size (); i++)
 432     if (!boxes[i].is_empty (X_AXIS)
 433         && !boxes[i].is_empty (Y_AXIS))
 434       buildings.push_front (Building (boxes[i], horizon_axis, sky));
 435
 436   buildings_ = internal_build_skyline (&buildings);
 437   normalize ();
 438 }
 439
 440 /*
 441   build skyline from a set of line segments.
 442
 443   Segments can be articulated from left to right or right to left.
 444   In the case of the latter, they will be stored internally as left to right.
 445  */
 446 Skyline::Skyline (vector<Drul_array<Offset> > const &segments, Axis horizon_axis, Direction sky)
 447 {
 448   list<Building> buildings;
 449   sky_ = sky;
 450
 451   for (vsize i = 0; i < segments.size (); i++)
 452     {
 453       Drul_array<Offset> const &seg = segments[i];
 454       Offset left = seg[LEFT];
 455       Offset right = seg[RIGHT];
 456       if (left[horizon_axis] > right[horizon_axis])
 457         swap (left, right);
 458
 459       Real x1 = left[horizon_axis];
 460       Real x2 = right[horizon_axis];
 461       Real y1 = left[other_axis (horizon_axis)] * sky;
 462       Real y2 = right[other_axis (horizon_axis)] * sky;
 463
 464       if (x1 <= x2)
 465         buildings.push_back (Building (x1, y1, y2, x2));
 466     }
 467
 468   buildings_ = internal_build_skyline (&buildings);
 469   normalize ();
 470 }
 471
 472 Skyline::Skyline (vector<Skyline_pair> const &skypairs, Direction sky)
 473 {
 474   sky_ = sky;
 475
 476   deque<Skyline> partials;
 477   for (vsize i = 0; i < skypairs.size (); i++)
 478     partials.push_back (Skyline ((skypairs[i])[sky]));
 479
 480   while (partials.size () > 1)
 481     {
 482       Skyline one = partials.front ();
 483       partials.pop_front ();
 484       Skyline two = partials.front ();
 485       partials.pop_front ();
 486
 487       one.merge (two);
 488       partials.push_back (one);
 489     }
 490
 491   if (partials.size ())
 492     buildings_.swap (partials.front ().buildings_);
 493   else
 494     buildings_.clear ();
 495 }
 496
 497 Skyline::Skyline (Box const &b, Axis horizon_axis, Direction sky)
 498 {
 499   sky_ = sky;
 500   if (!b.is_empty (X_AXIS) && !b.is_empty (Y_AXIS))
 501     {
 502       Building front (b, horizon_axis, sky);
 503       single_skyline (front, &buildings_);
 504       normalize ();
 505     }
 506 }
 507
 508 void
 509 Skyline::merge (Skyline const &other)
 510 {
 511   assert (sky_ == other.sky_);
 512
 513   if (other.is_empty ())
 514     return;
 515
 516   if (is_empty ())
 517     {
 518       buildings_ = other.buildings_;
 519       return;
 520     }
 521
 522   list<Building> other_bld (other.buildings_);
 523   list<Building> my_bld;
 524   my_bld.splice (my_bld.begin (), buildings_);
 525   internal_merge_skyline (&other_bld, &my_bld, &buildings_);
 526   normalize ();
 527 }
 528
 529 void
 530 Skyline::insert (Box const &b, Axis a)
 531 {
 532   list<Building> other_bld;
 533   list<Building> my_bld;
 534
 535   if (isnan (b[other_axis (a)][LEFT])
 536       || isnan (b[other_axis (a)][RIGHT]))
 537     {
 538       programming_error ("insane box for skyline");
 539       return;
 540     }
 541
 542   /* do the same filtering as in Skyline (vector<Box> const&, etc.) */
 543   if (b.is_empty (X_AXIS) || b.is_empty (Y_AXIS))
 544     return;
 545
 546   my_bld.splice (my_bld.begin (), buildings_);
 547   single_skyline (Building (b, a, sky_), &other_bld);
 548   internal_merge_skyline (&other_bld, &my_bld, &buildings_);
 549   normalize ();
 550 }
 551
 552 void
 553 Skyline::raise (Real r)
 554 {
 555   list<Building>::iterator end = buildings_.end ();
 556   for (list<Building>::iterator i = buildings_.begin (); i != end; i++)
 557     i->y_intercept_ += sky_ * r;
 558 }
 559
 560 void
 561 Skyline::shift (Real s)
 562 {
 563   list<Building>::iterator end = buildings_.end ();
 564   for (list<Building>::iterator i = buildings_.begin (); i != end; i++)
 565     {
 566       i->start_ += s;
 567       i->end_ += s;
 568       i->y_intercept_ -= s * i->slope_;
 569     }
 570 }
 571
 572 Real
 573 Skyline::distance (Skyline const &other, Real horizon_padding) const
 574 {
 575   Real dummy;
 576   return internal_distance (other, horizon_padding, &dummy);
 577 }
 578
 579 Real
 580 Skyline::touching_point (Skyline const &other, Real horizon_padding) const
 581 {
 582   Real touch;
 583   internal_distance (other, horizon_padding, &touch);
 584   return touch;
 585 }
 586
 587 Real
 588 Skyline::internal_distance (Skyline const &other, Real horizon_padding, Real *touch_point) const
 589 {
 590   if (horizon_padding == 0.0)
 591     return internal_distance (other, touch_point);
 592
 593   // Note that it is not necessary to build a padded version of other,
 594   // because the same effect can be achieved just by doubling horizon_padding.
 595   Skyline padded_this = padded (horizon_padding);
 596   return padded_this.internal_distance (other, touch_point);
 597 }
 598
 599 Skyline
 600 Skyline::padded (Real horizon_padding) const
 601 {
 602   if (horizon_padding < 0.0)
 603     warning ("Cannot have negative horizon padding.  Junking.");
 604
 605   if (horizon_padding <= 0.0)
 606     return *this;
 607
 608   list<Building> pad_buildings;
 609   for (list<Building>::const_iterator i = buildings_.begin (); i != buildings_.end (); ++i)
 610     {
 611       if (i->start_ > -infinity_f)
 612         {
 613           Real height = i->height (i->start_);
 614           if (height > -infinity_f)
 615             {
 616               // Add the sloped building that pads the left side of the current building.
 617               Real start = i->start_ - 2 * horizon_padding;
 618               Real end = i->start_ - horizon_padding;
 619               pad_buildings.push_back (Building (start, height - horizon_padding, height, end));
 620
 621               // Add the flat building that pads the left side of the current building.
 622               start = i->start_ - horizon_padding;
 623               end = i->start_;
 624               pad_buildings.push_back (Building (start, height, height, end));
 625             }
 626         }
 627
 628       if (i->end_ < infinity_f)
 629         {
 630           Real height = i->height (i->end_);
 631           if (height > -infinity_f)
 632             {
 633               // Add the flat building that pads the right side of the current building.
 634               Real start = i->end_;
 635               Real end = start + horizon_padding;
 636               pad_buildings.push_back (Building (start, height, height, end));
 637
 638               // Add the sloped building that pads the right side of the current building.
 639               start = end;
 640               end += horizon_padding;
 641               pad_buildings.push_back (Building (start, height, height - horizon_padding, end));
 642             }
 643         }
 644     }
 645
 646   // The buildings may be overlapping, so resolve that.
 647   list<Building> pad_skyline = internal_build_skyline (&pad_buildings);
 648
 649   // Merge the padding with the original, to make a new skyline.
 650   Skyline padded (sky_);
 651   list<Building> my_buildings = buildings_;
 652   padded.buildings_.clear ();
 653   internal_merge_skyline (&pad_skyline, &my_buildings, &padded.buildings_);
 654   padded.normalize ();
 655
 656   return padded;
 657 }
 658
 659 Real
 660 Skyline::internal_distance (Skyline const &other, Real *touch_point) const
 661 {
 662   assert (sky_ == -other.sky_);
 663
 664   list<Building>::const_iterator i = buildings_.begin ();
 665   list<Building>::const_iterator j = other.buildings_.begin ();
 666
 667   Real dist = -infinity_f;
 668   Real start = -infinity_f;
 669   Real touch = -infinity_f;
 670   while (i != buildings_.end () && j != other.buildings_.end ())
 671     {
 672       Real end = min (i->end_, j->end_);
 673       Real start_dist = i->height (start) + j->height (start);
 674       Real end_dist = i->height (end) + j->height (end);
 675       dist = max (dist, max (start_dist, end_dist));
 676
 677       if (end_dist == dist)
 678         touch = end;
 679       else if (start_dist == dist)
 680         touch = start;
 681
 682       if (i->end_ <= j->end_)
 683         i++;
 684       else
 685         j++;
 686       start = end;
 687     }
 688
 689   *touch_point = touch;
 690   return dist;
 691 }
 692
 693 Real
 694 Skyline::height (Real airplane) const
 695 {
 696   assert (!isinf (airplane));
 697
 698   list<Building>::const_iterator i;
 699   for (i = buildings_.begin (); i != buildings_.end (); i++)
 700     {
 701       if (i->end_ >= airplane)
 702         return sky_ * i->height (airplane);
 703     }
 704
 705   assert (0);
 706   return 0;
 707 }
 708
 709 Real
 710 Skyline::max_height () const
 711 {
 712   Real ret = -infinity_f;
 713
 714   list<Building>::const_iterator i;
 715   for (i = buildings_.begin (); i != buildings_.end (); ++i)
 716     {
 717       ret = max (ret, i->height (i->start_));
 718       ret = max (ret, i->height (i->end_));
 719     }
 720
 721   return sky_ * ret;
 722 }
 723
 724 Direction
 725 Skyline::direction () const
 726 {
 727   return sky_;
 728 }
 729
 730 Real
 731 Skyline::left () const
 732 {
 733   for (list<Building>::const_iterator i (buildings_.begin ());
 734        i != buildings_.end (); i++)
 735     if (i->y_intercept_ > -infinity_f)
 736       return i->start_;
 737
 738   return infinity_f;
 739 }
 740
 741 Real
 742 Skyline::right () const
 743 {
 744   for (list<Building>::const_reverse_iterator i (buildings_.rbegin ());
 745        i != buildings_.rend (); ++i)
 746     if (i->y_intercept_ > -infinity_f)
 747       return i->end_;
 748
 749   return -infinity_f;
 750 }
 751
 752 Real
 753 Skyline::max_height_position () const
 754 {
 755   Skyline s (-sky_);
 756   s.set_minimum_height (0);
 757   return touching_point (s);
 758 }
 759
 760 void
 761 Skyline::set_minimum_height (Real h)
 762 {
 763   Skyline s (sky_);
 764   s.buildings_.front ().y_intercept_ = h * sky_;
 765   merge (s);
 766 }
 767
 768 vector<Offset>
 769 Skyline::to_points (Axis horizon_axis) const
 770 {
 771   vector<Offset> out;
 772
 773   Real start = -infinity_f;
 774   for (list<Building>::const_iterator i (buildings_.begin ());
 775        i != buildings_.end (); i++)
 776     {
 777       out.push_back (Offset (start, sky_ * i->height (start)));
 778       out.push_back (Offset (i->end_, sky_ * i->height (i->end_)));
 779       start = i->end_;
 780     }
 781
 782   if (horizon_axis == Y_AXIS)
 783     for (vsize i = 0; i < out.size (); i++)
 784       out[i] = out[i].swapped ();
 785
 786   return out;
 787 }
 788
 789 bool
 790 Skyline::is_empty () const
 791 {
 792   if (!buildings_.size ())
 793     return true;
 794   Building b = buildings_.front ();
 795   return b.end_ == infinity_f && b.y_intercept_ == -infinity_f;
 796 }
 797
 798 void
 799 Skyline::clear ()
 800 {
 801   buildings_.clear ();
 802   empty_skyline (&buildings_);
 803 }
 804
 805 /****************************************************************/
 806
 807 const char Skyline::type_p_name_[] = "ly:skyline?";
 808
 809 MAKE_SCHEME_CALLBACK_WITH_OPTARGS (Skyline, get_touching_point, 3, 1, "")
 810 SCM
 811 Skyline::get_touching_point (SCM skyline_scm, SCM other_skyline_scm, SCM horizon_padding_scm)
 812 {
 813   LY_ASSERT_SMOB (Skyline, other_skyline_scm, 1);
 814
 815   Real horizon_padding = 0;
 816   if (!SCM_UNBNDP (horizon_padding_scm))
 817     {
 818       LY_ASSERT_TYPE (scm_is_number, horizon_padding_scm, 3);
 819       horizon_padding = scm_to_double (horizon_padding_scm);
 820     }
 821
 822   Skyline *skyline = Skyline::unsmob (skyline_scm);
 823   Skyline *other_skyline = Skyline::unsmob (other_skyline_scm);
 824   return scm_from_double (skyline->touching_point (*other_skyline, horizon_padding));
 825 }
 826
 827 MAKE_SCHEME_CALLBACK_WITH_OPTARGS (Skyline, get_distance, 3, 1, "")
 828 SCM
 829 Skyline::get_distance (SCM skyline_scm, SCM other_skyline_scm, SCM horizon_padding_scm)
 830 {
 831   LY_ASSERT_SMOB (Skyline, other_skyline_scm, 1);
 832
 833   Real horizon_padding = 0;
 834   if (!SCM_UNBNDP (horizon_padding_scm))
 835     {
 836       LY_ASSERT_TYPE (scm_is_number, horizon_padding_scm, 3);
 837       horizon_padding = scm_to_double (horizon_padding_scm);
 838     }
 839
 840   Skyline *skyline = Skyline::unsmob (skyline_scm);
 841   Skyline *other_skyline = Skyline::unsmob (other_skyline_scm);
 842   return scm_from_double (skyline->distance (*other_skyline, horizon_padding));
 843 }
 844
 845 MAKE_SCHEME_CALLBACK (Skyline, get_max_height, 1)
 846 SCM
 847 Skyline::get_max_height (SCM skyline_scm)
 848 {
 849   return scm_from_double (Skyline::unsmob (skyline_scm)->max_height ());
 850 }
 851
 852 MAKE_SCHEME_CALLBACK (Skyline, get_max_height_position, 1)
 853 SCM
 854 Skyline::get_max_height_position (SCM skyline_scm)
 855 {
 856   return scm_from_double (Skyline::unsmob (skyline_scm)->max_height_position ());
 857 }
 858
 859 MAKE_SCHEME_CALLBACK (Skyline, get_height, 2)
 860 SCM
 861 Skyline::get_height (SCM skyline_scm, SCM x_scm)
 862 {
 863   Real x = robust_scm2double (x_scm, 0.0);
 864   return scm_from_double (Skyline::unsmob (skyline_scm)->height (x));
 865 }
 866
 867 LY_DEFINE (ly_skyline_empty_p, "ly:skyline-empty?",
 868            1, 0, 0, (SCM sky),
 869            "Return whether @var{sky} is empty.")
 870 {
 871   Skyline *s = Skyline::unsmob (sky);
 872   LY_ASSERT_SMOB (Skyline, sky, 1);
 873   return scm_from_bool (s->is_empty ());
 874 }