lily/skyline.cc

   1 /*
   2   skyline.cc -- implement Skyline_entry and funcs.
   3
   4   source file of the GNU LilyPond music typesetter
   5
   6   (c) 2002--2006 Han-Wen Nienhuys <hanwen@xs4all.nl>
   7 */
   8
   9 #include "skyline.hh"
  10
  11 /*
  12   A skyline is a shape of the form:
  13
  14
  15   *                  ----
  16   *                  |  |
  17   *         ---------|  |
  18   *         |           |
  19   *         |           |
  20   *         |           |______
  21   * --------|                 |___
  22   *
  23
  24   This file deals with building such skyline structure, and computing
  25   the minimum distance between two opposing skylines.
  26
  27   Invariants for a skyline:
  28
  29   skyline[...].width_ forms a partition of the real interval, where
  30   the segments are adjacent, and ascending. Hence we have
  31
  32   skyline.back ().width_[RIGHT] = inf
  33   skyline[0].width_[LEFT] = -inf
  34 */
  35
  36 const Real EPS = 1e-12;
  37
  38 /*
  39   TODO: avoid unnecessary fragmentation.
  40
  41   This is O (n^2), searching and insertion.  Could be O (n log n) with
  42   binsearch.
  43 */
  44 void
  45 insert_extent_into_skyline (vector<Skyline_entry> *line, Box b, Axis line_axis,
  46                             Direction d)
  47 {
  48   Interval extent = b[line_axis];
  49   if (extent.is_empty ())
  50     return;
  51
  52   Real stick_out = b[other_axis (line_axis)][d];
  53
  54   /*
  55     Intersect each segment of LINE with EXTENT, and if non-empty, insert relevant segments.
  56   */
  57   for (vsize i = line->size (); i--;)
  58     {
  59       Interval w = line->at (i).width_;
  60       w.intersect (extent);
  61
  62       if (extent[LEFT] >= w[RIGHT])
  63         break;
  64
  65       Real my_height = line->at (i).height_;
  66
  67       if (!w.is_empty ()
  68           && w.length () > EPS
  69           && d * (my_height - stick_out) < 0)
  70         {
  71           Interval e1 (line->at (i).width_[LEFT], extent[LEFT]);
  72           Interval e3 (extent[RIGHT], line->at (i).width_[RIGHT]);
  73
  74           if (!e3.is_empty () && e3.length () > EPS)
  75             line->insert (line->begin () + i + 1, Skyline_entry (e3, my_height));
  76
  77           line->at (i).height_ = stick_out;
  78           line->at (i).width_ = w;
  79           if (!e1.is_empty () && e1.length () > EPS)
  80             line->insert (line->begin () + i, Skyline_entry (e1, my_height));
  81         }
  82     }
  83 }
  84
  85 void
  86 merge_skyline (vector<Skyline_entry> *a1,
  87                vector<Skyline_entry> const &a2,
  88                Direction dir)
  89 {
  90   for (vsize i = 0; i < a2.size (); i++)
  91     {
  92       Box b;
  93       b[X_AXIS] = a2[i].width_;
  94       b[Y_AXIS][dir] = a2[i].height_;
  95       b[Y_AXIS][-dir] = dir * infinity_f;
  96
  97       insert_extent_into_skyline (a1, b, X_AXIS, dir);
  98     }
  99 }
 100
 101 vector<Skyline_entry>
 102 empty_skyline (Direction d)
 103 {
 104   vector<Skyline_entry> skyline;
 105
 106   Interval i;
 107   i.set_empty ();
 108   i.swap ();
 109   Skyline_entry e;
 110   e.width_ = i;
 111   e.height_ = -d * infinity_f;
 112   skyline.push_back (e);
 113   return skyline;
 114 }
 115
 116 vector<Skyline_entry>
 117 extents_to_skyline (vector<Box> const &extents, Axis a, Direction d)
 118 {
 119
 120   vector<Skyline_entry> skyline = empty_skyline (d);
 121
 122   /*
 123     This makes a cubic algorithm (array  insertion is O (n),
 124     searching the array dumbly is O (n), and for n items, we get O (n^3).)
 125
 126     We could do a lot better (n log (n), using a balanced tree) but
 127     that seems overkill for now.
 128   */
 129   for (vsize j = extents.size (); j--;)
 130     insert_extent_into_skyline (&skyline, extents[j], a, d);
 131
 132   return skyline;
 133 }
 134
 135 /*
 136   minimum distance that can be achieved between baselines. "Clouds" is
 137   a skyline pointing down.
 138
 139   This is an O (n) algorithm.
 140 */
 141 Real
 142 skyline_meshing_distance (vector<Skyline_entry> const &buildings,
 143                           vector<Skyline_entry> const &clouds)
 144 {
 145   int i = buildings.size () -1;
 146   int j = clouds.size () -1;
 147
 148   Real distance = -infinity_f;
 149
 150   while (i > 0 || j > 0)
 151     {
 152       Interval w = buildings[i].width_;
 153       w.intersect (clouds[j].width_);
 154
 155       if (!w.is_empty ())
 156         distance = max (distance, (buildings[i].height_ - clouds[j].height_));
 157
 158       if (i > 0 && buildings[i].width_[LEFT] >= clouds[j].width_[LEFT])
 159         i--;
 160       else if (j > 0 && buildings[i].width_[LEFT] <= clouds[j].width_[LEFT])
 161         j--;
 162     }
 163
 164   return distance;
 165 }
 166
 167 Skyline_entry::Skyline_entry ()
 168 {
 169   height_ = 0.0;
 170 }
 171
 172 Skyline_entry::Skyline_entry (Interval i, Real r)
 173 {
 174   width_ = i;
 175   height_ = r;
 176 }
 177
 178 void
 179 heighten_skyline (vector<Skyline_entry> *buildings, Real ground)
 180 {
 181   for (vsize i = 0; i < buildings->size (); i++)
 182     buildings->at (i).height_ += ground;
 183 }
 184
 185 Real
 186 skyline_height (vector<Skyline_entry> const &buildings,
 187                 Real airplane,
 188                 Direction sky_dir)
 189 {
 190   Real h = - sky_dir * infinity_f;
 191
 192   /*
 193     Ugh! linear, should be O(log n).
 194    */
 195   for (vsize i = 0; i < buildings.size (); i++)
 196     if (buildings[i].width_.contains (airplane))
 197       h = sky_dir * max (sky_dir * h,
 198                          sky_dir * buildings[i].height_);
 199
 200   return h;
 201 }
 202