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