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