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