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