lily/skyline.cc

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