lily/skyline.cc

   1 /*
   2   This file is part of LilyPond, the GNU music typesetter.
   3
   4   Copyright (C) 2006--2015 Joe Neeman <joeneeman@gmail.com>
   5
   6   LilyPond is free software: you can redistribute it and/or modify
   7   it under the terms of the GNU General Public License as published by
   8   the Free Software Foundation, either version 3 of the License, or
   9   (at your option) any later version.
  10
  11   LilyPond is distributed in the hope that it will be useful,
  12   but WITHOUT ANY WARRANTY; without even the implied warranty of
  13   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14   GNU General Public License for more details.
  15
  16   You should have received a copy of the GNU General Public License
  17   along with LilyPond.  If not, see <http://www.gnu.org/licenses/>.
  18 */
  19
  20 #include "skyline.hh"
  21 #include "skyline-pair.hh"
  22 #include <deque>
  23 #include <cstdio>
  24
  25 /* 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 // Returns a shift s such that (x + s, y) intersects the roof of
 156 // this building.  If no such shift exists, returns infinity_f.
 157 Real
 158 Building::shift_to_intersect (Real x, Real y) const
 159 {
 160   // Solve for s: y = (x + s)*m + b
 161   Real ret = (y - y_intercept_ - slope_ * x) / slope_;
 162
 163   if (ret >= start_ && ret <= end_ && !isinf (ret))
 164     return ret;
 165   return infinity_f;
 166 }
 167
 168 bool
 169 Building::above (Building const &other, Real x) const
 170 {
 171   return (isinf (y_intercept_) || isinf (other.y_intercept_) || isinf (x))
 172          ? y_intercept_ > other.y_intercept_
 173          : (slope_ - other.slope_) * x + y_intercept_ > other.y_intercept_;
 174 }
 175
 176 // Remove redundant empty buildings from the skyline.
 177 // If there are two adjacent empty buildings, they can be
 178 // turned into one.
 179 void
 180 Skyline::normalize ()
 181 {
 182   bool last_empty = false;
 183   list<Building>::iterator i;
 184
 185   for (i = buildings_.begin (); i != buildings_.end (); i++)
 186     {
 187       if (last_empty && i->y_intercept_ == -infinity_f)
 188         {
 189           list<Building>::iterator last = i;
 190           last--;
 191           last->end_ = i->end_;
 192           buildings_.erase (i);
 193           i = last;
 194         }
 195       last_empty = (i->y_intercept_ == -infinity_f);
 196     }
 197
 198   assert (buildings_.front ().start_ == -infinity_f);
 199   assert (buildings_.back ().end_ == infinity_f);
 200 }
 201
 202 void
 203 Skyline::internal_merge_skyline (list<Building> *sb, list<Building> *sc,
 204                                  list<Building> *const result) const
 205 {
 206   if (sb->empty () || sc->empty ())
 207     {
 208       programming_error ("tried to merge an empty skyline");
 209       return;
 210     }
 211
 212   Building b = sb->front ();
 213   for (; !sc->empty (); sc->pop_front ())
 214     {
 215       /* Building b is continuing from the previous pass through the loop.
 216          Building c is newly-considered, and starts no earlier than b started.
 217          The comments draw b as if its roof had zero slope ----.
 218          with dashes where b lies above c.
 219          The roof of c could rise / or fall \ through the roof of b,
 220          or the vertical sides | of c could intersect the roof of b.  */
 221       Building c = sc->front ();
 222       if (b.end_ < c.end_) /* finish with b */
 223         {
 224           if (b.end_ <= b.start_) /* we are already finished with b */
 225             ;
 226           else if (c.above (b, c.start_)) /* -|   . | */
 227             {
 228               Building m (b);
 229               m.end_ = c.start_;
 230               if (m.end_ > m.start_)
 231                 result->push_back (m);
 232               if (b.above (c, b.end_))    /* -|\--.   */
 233                 {
 234                   Building n (c);
 235                   n.end_ = b.start_ = b.intersection_x (c);
 236                   result->push_back (n);
 237                   result->push_back (b);
 238                 }
 239             }
 240           else
 241             {
 242               if (c.above (b, b.end_))    /* ---/ . | */
 243                 b.end_ = b.intersection_x (c);
 244               else                        /* -----.   */
 245                 c.start_ = b.end_;
 246               result->push_back (b);
 247             }
 248           /* 'c' continues further, so move it into 'b' for the next pass. */
 249           b = c;
 250           swap (sb, sc);
 251         }
 252       else /* b.end_ > c.end_ so finish with c */
 253         {
 254           if (c.above (b, c.start_))    /* -| |---. */
 255             {
 256               Building m (b);
 257               m.end_ = c.start_;
 258               if (m.end_ > m.start_)
 259                 result->push_back (m);
 260               if (b.above (c, c.end_))  /* -| \---. */
 261                 c.end_ = b.intersection_x (c);
 262             }
 263           else if (c.above (b, c.end_)) /* ---/|--. */
 264             {
 265               Building m (b);
 266               c.start_ = m.end_ = b.intersection_x (c);
 267               result->push_back (m);
 268             }
 269           else  /* c is completely hidden by b */
 270             continue;
 271           result->push_back (c);
 272           b.start_ = c.end_;
 273         }
 274     }
 275   if (b.end_ > b.start_)
 276     result->push_back (b);
 277 }
 278
 279 static void
 280 empty_skyline (list<Building> *const ret)
 281 {
 282   ret->push_front (Building (-infinity_f, -infinity_f, -infinity_f, infinity_f));
 283 }
 284
 285 /*
 286   Given Building 'b', build a skyline containing only that building.
 287 */
 288 static void
 289 single_skyline (Building b, list<Building> *const ret)
 290 {
 291   assert (b.end_ >= b.start_);
 292
 293   if (b.start_ != -infinity_f)
 294     ret->push_back (Building (-infinity_f, -infinity_f,
 295                               -infinity_f, b.start_));
 296   ret->push_back (b);
 297   if (b.end_ != infinity_f)
 298     ret->push_back (Building (b.end_, -infinity_f,
 299                               -infinity_f, infinity_f));
 300 }
 301
 302 /* remove a non-overlapping set of boxes from BOXES and build a skyline
 303    out of them */
 304 static list<Building>
 305 non_overlapping_skyline (list<Building> *const buildings)
 306 {
 307   list<Building> result;
 308   Real last_end = -infinity_f;
 309   Building last_building (-infinity_f, -infinity_f, -infinity_f, infinity_f);
 310   list<Building>::iterator i = buildings->begin ();
 311   while (i != buildings->end ())
 312     {
 313       Real x1 = i->start_;
 314       Real y1 = i->height (i->start_);
 315       Real x2 = i->end_;
 316       Real y2 = i->height (i->end_);
 317
 318       // Drop buildings that will obviously have no effect.
 319       if (last_building.height (x1) >= y1
 320           && last_building.end_ >= x2
 321           && last_building.height (x2) >= y2)
 322         {
 323           list<Building>::iterator j = i++;
 324           buildings->erase (j);
 325           continue;
 326         }
 327
 328       if (x1 < last_end)
 329         {
 330           i++;
 331           continue;
 332         }
 333
 334       // Insert empty Buildings into any gaps. (TODO: is this needed? -KOH)
 335       if (x1 > last_end)
 336         result.push_back (Building (last_end, -infinity_f, -infinity_f, x1));
 337
 338       result.push_back (*i);
 339       last_building = *i;
 340       last_end = i->end_;
 341
 342       list<Building>::iterator j = i++;
 343       buildings->erase (j);
 344     }
 345
 346   if (last_end < infinity_f)
 347     result.push_back (Building (last_end, -infinity_f, -infinity_f, infinity_f));
 348   return result;
 349 }
 350
 351 class LessThanBuilding
 352 {
 353 public:
 354   bool operator () (Building const &b1, Building const &b2)
 355   {
 356     return b1.start_ < b2.start_
 357            || (b1.start_ == b2.start_ && b1.height (b1.start_) > b2.height (b1.start_));
 358   }
 359 };
 360
 361 /**
 362    BUILDINGS is a list of buildings, but they could be overlapping
 363    and in any order.  The returned list of buildings is ordered and non-overlapping.
 364 */
 365 list<Building>
 366 Skyline::internal_build_skyline (list<Building> *buildings) const
 367 {
 368   vsize size = buildings->size ();
 369
 370   if (size == 0)
 371     {
 372       list<Building> result;
 373       empty_skyline (&result);
 374       return result;
 375     }
 376   else if (size == 1)
 377     {
 378       list<Building> result;
 379       single_skyline (buildings->front (), &result);
 380       return result;
 381     }
 382
 383   deque<list<Building> > partials;
 384   buildings->sort (LessThanBuilding ());
 385   while (!buildings->empty ())
 386     partials.push_back (non_overlapping_skyline (buildings));
 387
 388   /* we'd like to say while (partials->size () > 1) but that's O (n).
 389      Instead, we exit in the middle of the loop */
 390   while (!partials.empty ())
 391     {
 392       list<Building> merged;
 393       list<Building> one = partials.front ();
 394       partials.pop_front ();
 395       if (partials.empty ())
 396         return one;
 397
 398       list<Building> two = partials.front ();
 399       partials.pop_front ();
 400       internal_merge_skyline (&one, &two, &merged);
 401       partials.push_back (merged);
 402     }
 403   assert (0);
 404   return list<Building> ();
 405 }
 406
 407 Skyline::Skyline ()
 408 {
 409   sky_ = UP;
 410   empty_skyline (&buildings_);
 411 }
 412
 413 Skyline::Skyline (Direction sky)
 414 {
 415   sky_ = sky;
 416   empty_skyline (&buildings_);
 417 }
 418
 419 /*
 420   Build skyline from a set of boxes.
 421
 422   Boxes should be non-empty on both axes.  Otherwise, they will be ignored
 423  */
 424 Skyline::Skyline (vector<Box> const &boxes, Axis horizon_axis, Direction sky)
 425 {
 426   list<Building> buildings;
 427   sky_ = sky;
 428
 429   for (vsize i = 0; i < boxes.size (); i++)
 430     if (!boxes[i].is_empty (X_AXIS)
 431         && !boxes[i].is_empty (Y_AXIS))
 432       buildings.push_front (Building (boxes[i], horizon_axis, sky));
 433
 434   buildings_ = internal_build_skyline (&buildings);
 435   normalize ();
 436 }
 437
 438 /*
 439   build skyline from a set of line segments.
 440
 441   Segments can be articulated from left to right or right to left.
 442   In the case of the latter, they will be stored internally as left to right.
 443  */
 444 Skyline::Skyline (vector<Drul_array<Offset> > const &segments, Axis horizon_axis, Direction sky)
 445 {
 446   list<Building> buildings;
 447   sky_ = sky;
 448
 449   for (vsize i = 0; i < segments.size (); i++)
 450     {
 451       Drul_array<Offset> const &seg = segments[i];
 452       Offset left = seg[LEFT];
 453       Offset right = seg[RIGHT];
 454       if (left[horizon_axis] > right[horizon_axis])
 455         swap (left, right);
 456
 457       Real x1 = left[horizon_axis];
 458       Real x2 = right[horizon_axis];
 459       Real y1 = left[other_axis (horizon_axis)] * sky;
 460       Real y2 = right[other_axis (horizon_axis)] * sky;
 461
 462       if (x1 <= x2)
 463         buildings.push_back (Building (x1, y1, y2, x2));
 464     }
 465
 466   buildings_ = internal_build_skyline (&buildings);
 467   normalize ();
 468 }
 469
 470 Skyline::Skyline (vector<Skyline_pair> const &skypairs, Direction sky)
 471 {
 472   sky_ = sky;
 473
 474   deque<Skyline> partials;
 475   for (vsize i = 0; i < skypairs.size (); i++)
 476     partials.push_back (Skyline ((skypairs[i])[sky]));
 477
 478   while (partials.size () > 1)
 479     {
 480       Skyline one = partials.front ();
 481       partials.pop_front ();
 482       Skyline two = partials.front ();
 483       partials.pop_front ();
 484
 485       one.merge (two);
 486       partials.push_back (one);
 487     }
 488
 489   if (partials.size ())
 490     buildings_.swap (partials.front ().buildings_);
 491   else
 492     buildings_.clear ();
 493 }
 494
 495 Skyline::Skyline (Box const &b, Axis horizon_axis, Direction sky)
 496 {
 497   sky_ = sky;
 498   if (!b.is_empty (X_AXIS) && !b.is_empty (Y_AXIS))
 499     {
 500       Building front (b, horizon_axis, sky);
 501       single_skyline (front, &buildings_);
 502       normalize ();
 503     }
 504 }
 505
 506 void
 507 Skyline::merge (Skyline const &other)
 508 {
 509   assert (sky_ == other.sky_);
 510
 511   if (other.is_empty ())
 512     return;
 513
 514   if (is_empty ())
 515     {
 516       buildings_ = other.buildings_;
 517       return;
 518     }
 519
 520   list<Building> other_bld (other.buildings_);
 521   list<Building> my_bld;
 522   my_bld.splice (my_bld.begin (), buildings_);
 523   internal_merge_skyline (&other_bld, &my_bld, &buildings_);
 524   normalize ();
 525 }
 526
 527 void
 528 Skyline::insert (Box const &b, Axis a)
 529 {
 530   list<Building> other_bld;
 531   list<Building> my_bld;
 532
 533   if (isnan (b[other_axis (a)][LEFT])
 534       || isnan (b[other_axis (a)][RIGHT]))
 535     {
 536       programming_error ("insane box for skyline");
 537       return;
 538     }
 539
 540   /* do the same filtering as in Skyline (vector<Box> const&, etc.) */
 541   if (b.is_empty (X_AXIS) || b.is_empty (Y_AXIS))
 542     return;
 543
 544   my_bld.splice (my_bld.begin (), buildings_);
 545   single_skyline (Building (b, a, sky_), &other_bld);
 546   internal_merge_skyline (&other_bld, &my_bld, &buildings_);
 547   normalize ();
 548 }
 549
 550 void
 551 Skyline::raise (Real r)
 552 {
 553   list<Building>::iterator end = buildings_.end ();
 554   for (list<Building>::iterator i = buildings_.begin (); i != end; i++)
 555     i->y_intercept_ += sky_ * r;
 556 }
 557
 558 void
 559 Skyline::shift (Real s)
 560 {
 561   list<Building>::iterator end = buildings_.end ();
 562   for (list<Building>::iterator i = buildings_.begin (); i != end; i++)
 563     {
 564       i->start_ += s;
 565       i->end_ += s;
 566       i->y_intercept_ -= s * i->slope_;
 567     }
 568 }
 569
 570 Real
 571 Skyline::distance (Skyline const &other, Real horizon_padding) const
 572 {
 573   Real dummy;
 574   return internal_distance (other, horizon_padding, &dummy);
 575 }
 576
 577 Real
 578 Skyline::touching_point (Skyline const &other, Real horizon_padding) const
 579 {
 580   Real touch;
 581   internal_distance (other, horizon_padding, &touch);
 582   return touch;
 583 }
 584
 585 Real
 586 Skyline::internal_distance (Skyline const &other, Real horizon_padding, Real *touch_point) const
 587 {
 588   if (horizon_padding == 0.0)
 589     return internal_distance (other, touch_point);
 590
 591   // Note that it is not necessary to build a padded version of other,
 592   // because the same effect can be achieved just by doubling horizon_padding.
 593   Skyline padded_this = padded (horizon_padding);
 594   return padded_this.internal_distance (other, touch_point);
 595 }
 596
 597 Skyline
 598 Skyline::padded (Real horizon_padding) const
 599 {
 600   if (horizon_padding < 0.0)
 601     warning ("Cannot have negative horizon padding.  Junking.");
 602
 603   if (horizon_padding <= 0.0)
 604     return *this;
 605
 606   list<Building> pad_buildings;
 607   for (list<Building>::const_iterator i = buildings_.begin (); i != buildings_.end (); ++i)
 608     {
 609       if (i->start_ > -infinity_f)
 610         {
 611           Real height = i->height (i->start_);
 612           if (height > -infinity_f)
 613             {
 614               // Add the sloped building that pads the left side of the current building.
 615               Real start = i->start_ - 2 * horizon_padding;
 616               Real end = i->start_ - horizon_padding;
 617               pad_buildings.push_back (Building (start, height - horizon_padding, height, end));
 618
 619               // Add the flat building that pads the left side of the current building.
 620               start = i->start_ - horizon_padding;
 621               end = i->start_;
 622               pad_buildings.push_back (Building (start, height, height, end));
 623             }
 624         }
 625
 626       if (i->end_ < infinity_f)
 627         {
 628           Real height = i->height (i->end_);
 629           if (height > -infinity_f)
 630             {
 631               // Add the flat building that pads the right side of the current building.
 632               Real start = i->end_;
 633               Real end = start + horizon_padding;
 634               pad_buildings.push_back (Building (start, height, height, end));
 635
 636               // Add the sloped building that pads the right side of the current building.
 637               start = end;
 638               end += horizon_padding;
 639               pad_buildings.push_back (Building (start, height, height - horizon_padding, end));
 640             }
 641         }
 642     }
 643
 644   // The buildings may be overlapping, so resolve that.
 645   list<Building> pad_skyline = internal_build_skyline (&pad_buildings);
 646
 647   // Merge the padding with the original, to make a new skyline.
 648   Skyline padded (sky_);
 649   list<Building> my_buildings = buildings_;
 650   padded.buildings_.clear ();
 651   internal_merge_skyline (&pad_skyline, &my_buildings, &padded.buildings_);
 652   padded.normalize ();
 653
 654   return padded;
 655 }
 656
 657 Real
 658 Skyline::internal_distance (Skyline const &other, Real *touch_point) const
 659 {
 660   assert (sky_ == -other.sky_);
 661
 662   list<Building>::const_iterator i = buildings_.begin ();
 663   list<Building>::const_iterator j = other.buildings_.begin ();
 664
 665   Real dist = -infinity_f;
 666   Real start = -infinity_f;
 667   Real touch = -infinity_f;
 668   while (i != buildings_.end () && j != other.buildings_.end ())
 669     {
 670       Real end = min (i->end_, j->end_);
 671       Real start_dist = i->height (start) + j->height (start);
 672       Real end_dist = i->height (end) + j->height (end);
 673       dist = max (dist, max (start_dist, end_dist));
 674
 675       if (end_dist == dist)
 676         touch = end;
 677       else if (start_dist == dist)
 678         touch = start;
 679
 680       if (i->end_ <= j->end_)
 681         i++;
 682       else
 683         j++;
 684       start = end;
 685     }
 686
 687   *touch_point = touch;
 688   return dist;
 689 }
 690
 691 Real
 692 Skyline::height (Real airplane) const
 693 {
 694   assert (!isinf (airplane));
 695
 696   list<Building>::const_iterator i;
 697   for (i = buildings_.begin (); i != buildings_.end (); i++)
 698     {
 699       if (i->end_ >= airplane)
 700         return sky_ * i->height (airplane);
 701     }
 702
 703   assert (0);
 704   return 0;
 705 }
 706
 707 Real
 708 Skyline::max_height () const
 709 {
 710   Real ret = -infinity_f;
 711
 712   list<Building>::const_iterator i;
 713   for (i = buildings_.begin (); i != buildings_.end (); ++i)
 714     {
 715       ret = max (ret, i->height (i->start_));
 716       ret = max (ret, i->height (i->end_));
 717     }
 718
 719   return sky_ * ret;
 720 }
 721
 722 Direction
 723 Skyline::direction () const
 724 {
 725   return sky_;
 726 }
 727
 728 Real
 729 Skyline::left () const
 730 {
 731   for (list<Building>::const_iterator i (buildings_.begin ());
 732        i != buildings_.end (); i++)
 733     if (i->y_intercept_ > -infinity_f)
 734       return i->start_;
 735
 736   return infinity_f;
 737 }
 738
 739 Real
 740 Skyline::right () const
 741 {
 742   for (list<Building>::const_reverse_iterator i (buildings_.rbegin ());
 743        i != buildings_.rend (); ++i)
 744     if (i->y_intercept_ > -infinity_f)
 745       return i->end_;
 746
 747   return -infinity_f;
 748 }
 749
 750 Real
 751 Skyline::max_height_position () const
 752 {
 753   Skyline s (-sky_);
 754   s.set_minimum_height (0);
 755   return touching_point (s);
 756 }
 757
 758 void
 759 Skyline::set_minimum_height (Real h)
 760 {
 761   Skyline s (sky_);
 762   s.buildings_.front ().y_intercept_ = h * sky_;
 763   merge (s);
 764 }
 765
 766 vector<Offset>
 767 Skyline::to_points (Axis horizon_axis) const
 768 {
 769   vector<Offset> out;
 770
 771   Real start = -infinity_f;
 772   for (list<Building>::const_iterator i (buildings_.begin ());
 773        i != buildings_.end (); i++)
 774     {
 775       out.push_back (Offset (start, sky_ * i->height (start)));
 776       out.push_back (Offset (i->end_, sky_ * i->height (i->end_)));
 777       start = i->end_;
 778     }
 779
 780   if (horizon_axis == Y_AXIS)
 781     for (vsize i = 0; i < out.size (); i++)
 782       out[i] = out[i].swapped ();
 783
 784   return out;
 785 }
 786
 787 bool
 788 Skyline::is_empty () const
 789 {
 790   if (!buildings_.size ())
 791     return true;
 792   Building b = buildings_.front ();
 793   return b.end_ == infinity_f && b.y_intercept_ == -infinity_f;
 794 }
 795
 796 void
 797 Skyline::clear ()
 798 {
 799   buildings_.clear ();
 800   empty_skyline (&buildings_);
 801 }
 802
 803 /****************************************************************/
 804
 805 const char Skyline::type_p_name_[] = "ly:skyline?";
 806
 807 MAKE_SCHEME_CALLBACK_WITH_OPTARGS (Skyline, get_touching_point, 3, 1, "")
 808 SCM
 809 Skyline::get_touching_point (SCM skyline_scm, SCM other_skyline_scm, SCM horizon_padding_scm)
 810 {
 811   LY_ASSERT_SMOB (Skyline, other_skyline_scm, 1);
 812
 813   Real horizon_padding = 0;
 814   if (!SCM_UNBNDP (horizon_padding_scm))
 815     {
 816       LY_ASSERT_TYPE (scm_is_number, horizon_padding_scm, 3);
 817       horizon_padding = scm_to_double (horizon_padding_scm);
 818     }
 819
 820   Skyline *skyline = unsmob<Skyline> (skyline_scm);
 821   Skyline *other_skyline = unsmob<Skyline> (other_skyline_scm);
 822   return scm_from_double (skyline->touching_point (*other_skyline, horizon_padding));
 823 }
 824
 825 MAKE_SCHEME_CALLBACK_WITH_OPTARGS (Skyline, get_distance, 3, 1, "")
 826 SCM
 827 Skyline::get_distance (SCM skyline_scm, SCM other_skyline_scm, SCM horizon_padding_scm)
 828 {
 829   LY_ASSERT_SMOB (Skyline, other_skyline_scm, 1);
 830
 831   Real horizon_padding = 0;
 832   if (!SCM_UNBNDP (horizon_padding_scm))
 833     {
 834       LY_ASSERT_TYPE (scm_is_number, horizon_padding_scm, 3);
 835       horizon_padding = scm_to_double (horizon_padding_scm);
 836     }
 837
 838   Skyline *skyline = unsmob<Skyline> (skyline_scm);
 839   Skyline *other_skyline = unsmob<Skyline> (other_skyline_scm);
 840   return scm_from_double (skyline->distance (*other_skyline, horizon_padding));
 841 }
 842
 843 MAKE_SCHEME_CALLBACK (Skyline, get_max_height, 1)
 844 SCM
 845 Skyline::get_max_height (SCM skyline_scm)
 846 {
 847   return scm_from_double (unsmob<Skyline> (skyline_scm)->max_height ());
 848 }
 849
 850 MAKE_SCHEME_CALLBACK (Skyline, get_max_height_position, 1)
 851 SCM
 852 Skyline::get_max_height_position (SCM skyline_scm)
 853 {
 854   return scm_from_double (unsmob<Skyline> (skyline_scm)->max_height_position ());
 855 }
 856
 857 MAKE_SCHEME_CALLBACK (Skyline, get_height, 2)
 858 SCM
 859 Skyline::get_height (SCM skyline_scm, SCM x_scm)
 860 {
 861   Real x = robust_scm2double (x_scm, 0.0);
 862   return scm_from_double (unsmob<Skyline> (skyline_scm)->height (x));
 863 }
 864
 865 LY_DEFINE (ly_skyline_empty_p, "ly:skyline-empty?",
 866            1, 0, 0, (SCM sky),
 867            "Return whether @var{sky} is empty.")
 868 {
 869   Skyline *s = unsmob<Skyline> (sky);
 870   LY_ASSERT_SMOB (Skyline, sky, 1);
 871   return scm_from_bool (s->is_empty ());
 872 }